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

a)  Бинарное отношение имеет характер равенства т.е. симметрия а R b => b R c

b) Транзитивность а R b => b R c  => a R c

c) a R a

Теорема: 10

Все отношения сравнения по mod(m) делит все множество R на m непересекающихся классов.

1) Все числа одного класса сравнимы друг с другом.

2) Числа из разных классов не сравнимы друг с другом по mod(m)

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

1)  Рассмотрим произвольное aÎR и фиксироманное m

A=lm+z = любое число z можно поделить на m с остатком

0<=z<m   z=r

0,1,2,…,m-1 в любой класс попадают числа которые имеют одинаковый остаток при делении на m (0,1,2,..)

2)  Рассмотрим 2 элемента из одного класса

a=k(m)

b=k(m)

a=lm+k ; b=nm+k  =>  a-b=m(l-n) || m ;  a=b(m)

3)  Элементы из разных классов не сравнимы по mod m

a=k(m)       k=k1  =>  a¹b(m)  (т.к. a-b не сравнимо m)

b=k1(m)

Теорема: 11

Свойства сравнения:

1)  a=b(m)  ;  m||k  => a-b||m  =>  a-b||k

2)  M(k₁,k₂,..k_n)=m a=b(k₁)    =>   a-b||k₁ a=b(k₂)    =>   a-b||k₂      => a=b(m) _……… a=b(k_n)    =>   a-b||k_n

Любое кратное делится на НОК.

a=b(m) <=> a-b||m 

3)  a=b(m) => ca=cb(cm)

Арифметика сравнений

Теорема: 12

1)  Сравнение по 1-му модулю можно по численно складывать и вычитать

2)  Сравнение по 1-му модулю можно по численно перемножать.

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

1. a=b(m)    a-b||m     =>  a-b+a₁-b₁||m

a₁=b₁(m)  a₁-b₁||m 

(a+a₁)-(b+b₁)||m <=>(a-a₁)=(b-b₁)||m

2. a=b(m)    умножается на a₁   (по теоремам 11 и 3)  =>

a₁=b₁(m) умножается на b

aa₁=bb₁(m)

a₁b=b₁b(m)

По транзитивности сравнимо aa₁=bb₁(m) ч.т.д.

Следствие:

Пункты 1,2 теоремы 12 можно можно обобщать на любое конечное число сравнений a=b(m) => aⁿ=bⁿ(m)

Пересекающиеся классы одинаковых остатков называют классами вычетов. Классы можно складывать и умножать между собой.

A+B=C aÎA, bÎB, a+bÎC

A B=D  aÎA, bÎB, abÎD

Классов конечное число, для них легко определить таблицу Кэхи (сложение и умножение классов вычетов)

m=6 – 6 классов  0,1,2,3,4,5

+	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

Левоциркулярная матрица т.е. она образуется циклическим сдвигом на 1 элемент влево.

Классы используются как элементы.

Теорема 13

ac=bc(m) D(c,m)=d => a=b(m/d) m/dÎZ т.к. d – делитель.

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

D(c,d)=c

D(m,d)=m

ac-bc||m => ac-bc=lm, lÎZ

l=(ac-bc)/m=(a-b)c₁/m₁=>(a-b)c₁||m₁ ; D(c₁,m₁)=b₁ =>(a-b)||m₁ => a=b(m₁) =>

=> a=b(m/d)

Следствие:

1)  m||c D(m,c)=C

ac=bc(m) => a=b(m/C)

2)  D(m,c)=1 ac=bc(m)=> a=b(m)

Пример: 24=4(10) =>(1) 12=2(5) =>(2)   6=1(5)

Теорема: 14 Обобщение арифметических операций.

Есть некоторая функция F(a,b,c…) от целых аргументов (полином)

F(a,b,c…)= S_kC_k a^a b^b c^c…  a,b,cÎZ

Пример: a²b³c+2a⁴b+… a,b,cÎZ

Тогда если a=a₁(m), b=b₁(m), c=c₁(m) => F(a,b,c…)=F(a₁,b₁,c₁…) (m)

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

a=a₁(m), a^za=a^za₁(m)

b^zb=b^zb₁(m) => a^za.b^zb=a^za₁(m)b^zb₁(m)

Утверждение: 1 Квадрат всякого нечетного числа сравнения с 1 по mod 8

4k+1 нечетное число.

(4k+1)²=16k²+8k+1=1(8)

Утверждение: 1 Нечетное число в виде 4k+3 нельзя представить в виде суммы двух квадратов.

4k+3=x²+y²

Если x,y – четные или нечетные, то получаем четное число – не подходит.

Т.е. либо x – четное, y – нет, либо наоборот

Пусть х – четное, у – нечетное.

х²=0(4) – x – четное.

y²=1(8) – y – нечетное => y²=1(4)

x²+y²=1(4), а 4k+3=3(4) => несоответствие.

Определение: m – непересекающихся классов.

Если взять из всех классов по 1 представителю, такой набор называется полной системой вычетов по модулю m.