Основы теории делимости. Основная теорема теории чисел. Алгоритм Евклида и цепные дроби. Разложение числа в цепную дробь, страница 4

{0,1,2,…,m-1} – наименьшая положительная система вычетов.

{0,-1,-2,…,-m+1} – наименьшая отрицательная система вычетов.

"аÎZ  {a,a+1,a+2,a+3,…a+(m-1)}

Функция Эйлера и ее свойства.

Определение: j(m) mÎN она определяется для всех натуральных чисел.

j(1)=1, j(m), m>1

j(m) – это число чисел меньших m и взаимно простых с m.

j(3)=2 (1,2)

j(5)=4 (1,2,3,4)

Теорема: 15

m=pⁿ – степень простого числа, тогда

j( pⁿ)=pⁿ(1-1/p)

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

Выпишем все делители pⁿ - p,2p,3p…, pⁿ-p.

Всего этих чисел - p^n-1-1

Всего чисел в интервале (1, pⁿ) - pⁿ-1

Чтобы найти все взаимнопростые числа надо из pⁿ-1 вычесть p^n-1-1= pⁿ-p^n-1= pⁿ(1-1/p).

Теорема: 16

Имеется 2 взаимно простых числа D(a,b)=1

x- пробегает полную систему вычетов по модулю a.

y- пробегает полную систему вычетов по модулю b.

Тогда.

1) Z=ay+bx=1 пробегает полную систему вычетов по модулю ab.

2) и D(Z,ab)=1 тогда и только тогда, когда D(a,x)=1 и D(b,y)=1

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

X – может принимать a значений, y – может принимать b значений

Тогда их комбинация ay+bx принимает ab значений

Покажем, что каждое значение Z не сравнимо друг с другом по модулю ab, т.е. что все значения Z образуют систему вычетов по модулю ab.

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

1)  Z₁=ay₁+bx₁ покажем, что они не сравнимы с Z₂=ay₂+bx₂

Пусть аy₁+bx₁=ay₂+bx₂(ab), тогда

аy₁+bx₁=ay₂+bx₂(a)

аy₁+bx₁=ay₂+bx₂(b) =>

a(y₁-y₂)=0 => bx₁=bx₂(a)

b(x₁-x₂)=0 => ax₁=ax₂(b), но по условию теоремы D(a,b)=1

По следствию 2 теоремы 13 x пробегает полную систему вычетов по mod а, т.е. x₁=x₂, y₁=y₂ – т.к. из разных классов по 1 элементу, а они не сравнимы).

т.е. Z₁=Z₂ т.е. Z- несравнимо друг с другом по модулю ab, т.е. Z – пробегает полную систему вычетов по модулю ab.

2)  D(Z,ab)=1, тогда  D(a,x)=1 D(y,b)=1

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

Z=ay+bx

D(ay+bx,ab)=1 => D(ay+bx,a)=1 и D(ay+bx,b)=1

Т.к. D(a,b)=1, то D(bx,a)=1 т.к. если D(bx,a)¹1 то D(ay+bx,a)¹1

D(ay,b)=1 т.к. D(a,b)=1

D(x,a)=1 и D(y,b)=1

Следствие к теореме 16

Если D(a,b)=1, тогда j(ab)=j(a) j(b)

Доказательство: по теореме 16.

x- пробегает полную систему вычетов по модулю a. =>

{0,1,2,…(a-1)}

j(a): D(x,a)=1.

y- пробегает полную систему вычетов по модулю b. =>

{0,1,2,…(b-1)}

j(b): D(y,b)=1.

Если Z- пробегает полную систему вычетов по модулю ab. =>

Z=ay+bx

j(ab): D(z,ab)=1.

j(a) j(b) условие D(x,a)=1 и D(y,b)=1 по теореме 16 (2) D(z,ab)=1 => j(ab)=j(a) j(b).

Если есть попарно взаимные числа D(a,b)=1 D(a,c)=1 D(c,b)=1, тогда j(abс)=j(a) j(b) j(с). Справедливо для любого числа сомножителей.

Следствие: 2 Формула Эйлера для любого числа mÎZ и запишем его в каноническое разложение – m=p^aq^br^c…

j(m)=j(p^a) j(q^b) j(r^c) по следствию 1.

По теореме 15 j(m)=p^a(1-1/p) q^b(1-1/q) r^c(1-1/r)…= m(1-1/p)(1-1/q)(1-1/r) – формула Эйлера для любого целого числа.

Пример:

j(17)=16

m=60=2^2.3^.5

j(m)=60(1-1/2)(1-1/3)(1-1/5)=16

Теорема: 17

Формула Гаусса.

Возьмем m.

Сумма всех функций Эйлера по всем делителям числа m – есть само число m.

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

m=p^aq^br^c…

Заметим, что любой делитель m-d=p^aq^br^c…

Где 0<=a₁<=a

0<=b₁<=b

0<=c₁<=c

[1+j(p)+j(p²)+…+j(p^a)]x[1+j(q)+j(q²)+…+j(q^b)]x[1+j(r)+j(r²)+…+j(r^c)]x…

Sj(p)j(q)j(r)…= Sj(p^aq^br^c)…=S_dj(d)  (По свойству мультиплекативности)

0<=a₁<=a

0<=b₁<=b

0<=c₁<=c

[1+p-1+p²-p+…+pⁿ-p^n-1](pⁿ)=pⁿ(1-1/p)

Из первой скобки получим p^a из второй q^b из третьей r^c и.т.д.

p^aq^br^c…=m

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

(Малая теорема Ферма)

Есть 2 числа D(a,m)=1 тогда утверждается

a^j(m)=1(mod m)

Ферма доказал сначала для m-простое число.

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

j(m)=m     m – любое число

m - классов вычетов

Возьмем из каждого класса m  представителей.

a₁, a₂, a₃… a_m, | D(a_i,m)=1

aa₁, aa₂, aa₃… aa_m, | D(aa_i,m)=1   каждый из этих чисел попадает в класс

Докажем,что ни один элемент не попадает в один и тот же класс.

Пусть aa_i=aa_j(m) => a_i=a_j(m) т.к. D(a,m)=1, но a_i¹a_j(m) т.к. мы определили их из разных классов вычетов.

Т.е. aa₁, aa₂, aa₃… aa_m - попадает в класс 1 раз.

a_n и aa_m – попадают в один и тот же класс.