§3. Взаимно простые числа и их свойства.

Определение1. Целые числа а₁ ,а₂,…,a_k называются взаимно-простыми, если (а₁ ,а₂,…,a_k ) =1

Определение 2. Целые числа а₁ ,а₂,…,a_k называются попарно взаимно-простыми, если i,s (i, s = 1, 2, .. , к, is, (а_i, а_s) =1).

Если числа удовлетворяют определению 2, то они удовлетворяют и определению 1. Обратное утверждение в общем случае неверно, например: (15, 21, 19)= 1, но (15, 21) = 3

Теорема (критерий взаимной простоты)

(а, b) = 1 <=>  х, у Z: ах + by = 1

Доказательство:

Докажем необходимость. Пусть (а, b) = 1. Выше мы показали, что если d=(a,b), то  х, y Z : d = ax +by.

Т.к. в этом случае d =1, то будут  х, y Z (определяемые из алгоритма Евклида): 1 = ах + bу.

Достаточность. Пусть (*) ах + by = 1, докажем, что (а, b)=1. Предположим, что (a, b) = d, тогда в левой части равенства (*)

(a /d) & (b /d) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.