пользователей: 21209
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


НОД. Свойства НОД. Алгоритм Евклида

Опр. Общий делитель нескольких целых чисел – это такое целое число, которое является делителем каждого из данных чисел, d|a1, d|a2,...d|an . НОД такой положит общий делитель чисел a1, a2,...an, который делится на любой другой общий делитель этих чисел. - наиб. из их общих делителей. Если хотя бы 1 из чисел a1, a2,...aотлично от 0, то НОД существуеи и есдинственно. Обозн: (a,b) (a1, a2, ...an)

Св-ва: 1. Если b|a, то (a,b)=b;    2.Если a,b € Z;  c,f € Z и a=bc+f, то (a,b)=(b,f)
3. (a,b)=d, m€ N =>(ma,mb)=md   4.(a,b)=d, c|a, c|b => c|d -верно и обратно

Алгоритм Евклида.  Получим последоват. целых неотриц чисел, строго убывающую. Последний неравный нулю остаток и есть НОД чисел. (a,b)=(b,r1)=(r1,r2)=(r2,r3)=(rk-1, rk)=rk.   Расширенный алгоритм Евклида позволяет  получить линейное представление НОД. (a,b)=d; x0,y0 € Z, ax0+by0=d-линейное представление.


11.01.2016; 03:12
хиты: 44
рейтинг:0
Точные науки
математика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь