Опр. Общий делитель нескольких целых чисел – это такое целое число, которое является делителем каждого из данных чисел, d|a1, d|a2,...d|an . НОД такой положит общий делитель чисел a1, a2,...an, который делится на любой другой общий делитель этих чисел. - наиб. из их общих делителей. Если хотя бы 1 из чисел a1, a2,...an отлично от 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-линейное представление.
