Теорема Эйлера

Теоре́ма Э́йлера в теории чисел гласит: Если a и m взаимно просты, то  , где φ(m) — функция Эйлера

Основные свойства натуральных чисел

Основна́я теоре́ма арифме́тики утверждает:

Каждое натуральное число n > 1 представляется в виде  , где   — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей

Единицу можно также считать произведением нулевого количества простых чисел, «пустым произведением».

Как следствие, каждое натуральное число n единственным образом представимо в виде

 где   — простые числа, и   — некоторые натуральные числа.

Такое представление числа n называется его каноническим разложением на простые сомножители.

Если простое число p делит без остатка произведение двух целых чисел  , то p делит x или y например 5*6=30,допустим р=3, если 30/3=10- без остатка, то 6 тоже делится на 3 или

Коммутативность сложения. 

1. Коммутативность умножения. 

2. Ассоциативность сложения. 

3. Ассоциативность умножения. 

4. Дистрибутивность умножения относительно сложения. 

Алгоритм Евклида для целых чисел

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое r_k — это остаток от деления предыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq₀ + r₁

b = r₁q₁ + r₂

r₁ = r₂q₂ + r₃

r_{k − 2} = r_{k − 1}q_{k − 1} + r_k

r_{n − 1} = r_nq_n

Тогда НОД(a,b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности.

Существование таких r₁,r₂,..., то есть возможность деления с остатком m на n для любого целого m и целого  , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

• Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).

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

• НОД(0,r) = r для любого ненулевого r (т.к. 0 делится на любое целое число, кроме нуля).

Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Пример

Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим знаменатель меньше чем 462. Мы должны дважды отнять 462, (q₀ = 2), оставаясь с остатком 147

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q₁ = 3), оставаясь с остатком 21.

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q₂ = 7), оставаясь без остатка.

147 = 7 × 21 + 0.

Таким образом последовательность a>b>R1>R2>R3>R4>...>Rn в данном конкретном случае будет выглядеть так:

1071>462>147>21

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.

В табличной форме, шаги были следующие

Шаг k	Равенство	Частное и остаток
0	1071 = q0 462 + r0	q0 = 2 и r0 = 147
1	462 = q1 147 + r1	q1 = 3 и r1 = 21
2	147 = q2 21 + r2	q2 = 7 и r2 = 0; алгоритм заканчивается

Расширенный алгоритм Евклида

a = bq₀ + r₁