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

Основы теории делимости

Пусть есть a,bÎZ

N,Z,Q,R,C – множества чисел

Теорема: о делимости целых чисел

Для любых a,bÎZ существуют единственные q, r такие, что 0<=r<|b| a=bq+r

q=[a/b] r={a/b}

Если r=0, то a||b (a кратно b)

Теорема 1: Свойства деления

1)  a||b, b||c => a||c  (транзитивность)

2)  a₁,a₂, … ,a_k | =>  "l₁,l₂, … , l_k

a_i||c             |

S^k_i=1a_il_i||c

Если любое а кратно с, то линейная комбинация тоже кратно с

Существует max(a,b)<=M(a,b)<=ab

Определение:

Существует a,b a||d, b||d  D(a,b) – НОД

1<=D(a,b)<=min(a,b)

Определение:

a,b называются взаимно простыми, если M(a,b)=1

Теорема 2: Свойства НОД и НОК

1) a₁,a₂, … ,a_k

m||a₁, m||a₂, … , m||a_k      m||M(a₁,a₂, … ,a_k)      НОД||НОК

Доказательство: Пусть m=M(a₁,a₂, … ,a_k)q+r  0<r<M(a₁,a₂, … ,a_k)

r=m-M(a₁,a₂, … ,a_k)q  => r||a₁,a₂, … ,a_k  (т.к. m||a₁,a₂, … ,a_k) =>наше предположение неверно r=0

2) a₁,a₂, … ,a_k   d₁,d₂, … ,d_k

D(a₁,a₂, … ,a_k)=M(d₁,d₂, … ,d_n)

Доказательство: a_i||d₁, a_i||d₂, … , a_i||d_n т.е. а_i – кратное

a_i||M(d₁,d₂, … ,d_n), M(d₁,d₂, … ,d_n)||d_j

3)  ab=D(a,b)×M(a,b)

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

Пусть есть a₁,a₂, … ,a_k

Как найти D(a₁,a₂, … ,a_k)?

Пусть D(a_i,a_j) известно, тогда

d₁=D(a₁,a₂); d₂=D(d₁,a₃); d_k-1=D(d_k-2,a_k)

Утверждение:

ab||c  и  (a,c)=1 =>  b||c

Определение:

а называется простым если а||a или a||1 и у него нет других делителей.

Теорема: 3 Свойства простых чисел.

1)  a,p (p – простое) a||p или a||b  (b,p)=1

2)  ab||p => a||p или b||p

3)  a¹1, существует простой делитель

p=min{d₁,d₂, … ,d_k} – простое

Основная теорема теории чисел

Теорема: 4

a=p₁p₂…p_k=p^aq^br^c  (p,q,r – простые числа)

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

1)  a=a₁p₁, если а₁>1, то a₁=a₂p₂

2)  Существует единственная комбинация разложения числа на простые сомножители, a=p₁p₂…p_k=q₁q₂…q_k  (p,q – простые)

По теореме 3 – p_i||q₁, p_j||q₂

Нахождение простых чисел в интервале от 1 до N

Алгоритм:

S1 p₁=2, k=1

k+1  P_k

P_k>N остановка, числа можно просматривать до ÖN или до [ÖN]+1

Теорема: 5 Евклида

Множество простых чисел бесконечно

Доказательство: Пусть множество конечно {p₁,p₂…p_k}

Следующее простое число это произведение предыдущих плюс 1, т.е.

p_k+1=p₁p₂…p_k+1

Дано: aÎZ a=p^aq^br^c…

{p₁,p₂…p_k}

2=p₁<p₂<…<p_k

k,i Step0 k=1, i=1

Step1 a=1 => stop

a=p_kq+r        if r=0 => Step3

Step2 r=0 d_i=p_k, i=i+1 => Step1

Step3 r¹0 k=k+1 => Step1

Алгоритм Ферма

a=xy, a=u²-v²=(u-v)(u+v)

R(u,v)=u²-v²-a  остановка при R(u,v)=0

R(u,v)<0  V=V+1

R(u,v)>0  U=U+1

R(u+1,v)=(u+1)²-v²-a=u²-v²-a+(2u+1)=R(u,v)+2u+1

R(u,v+1)=u²-(v+1)²-a=u²-v²-a-(2v+1)=R(u,v)-2u-1

Алгоритм Евклида и цепные дроби.

D(a,b) - ?

D(a,b)=D(a-bq,b) a-bq+r

a=bq₀+r₀   D(b,r₀)

b=r₀q₁+r₁   D(r₀,r₁)

r₀=r₁q₂+r₂   D(r₁,r₂)

…   …           …

r_k-2=r_k-1q_k+r_k   D(r_k-1,r_k)

r_k-1=r_kq_k+1

Бинарный алгоритм

a)  a,b – четные => D(a,b)=2D(a/2,b/2)

b)  a – четное, b – нечетное => D(a,b)=D(a/2,b)

c)  D(a,b)=D(a-b,b)

d)  a,b – нечетные => a-b – четное

e)  |a-b|<max{a,b} a,b>0

S₁ k=0

k=k+1, a=a/2, b=b/2 (пока a,b четные)

S₂ a – нечетное => tmp=-b  goto S₄

а – четное => tmp=a

S₃ tmp=tmp/2

S_4a if (tmp – четно) => goto S₃

S₄  if (tmp>0) then a=tmp

Else b=-tmp

S₅ tmp=a-b

Tmp=0 stop

D(a,b)=2^ka

Goto S₃

Пример:

a                      b                   tmp

76501              29719            -29719

76501              29719            40782  23391

23391              29719            -6328  -3164  -1522  -791

23391              791                22600  11300  5650  2825

2825                791                2034  1017

1017                791                226  113

113                  791                –678  -229

113                  339                -226  -113

113  113

Разложение числа в цепную дробь

a>b

. . .

a<b

a/b<0

Теорема: 6

Любое рациональное число можно разложить в цепную дробь, одним и только одним способом, где все q_i>0, i>=1, a последнее q_k>1

(Если q_k не >1 то 2 разл: (q₀,q₁,…,q_k-1,1)

ZÎR имитируем алгоритм Евклида для вещественного числа

Z=q₀+b₁ q₀=[Z] – выделим целую часть числа

b₁Î(0,1), Z₁>1

Z=q₀+1/Z₁    (разложение числа в цепную дробь)

Z₁=q₁+b₂   q₁=[Z₁]

b₂Î(0,1)

Z₁=q₁+1/Z₂, Z₂>1

Z₂=q₂+b₃

….

=q₀,q₁…q_k+1

Пример:

(5,(3,2,10)) т.е. цепная периодическая дробь

a=bq₀+r₀

b=r₀q₁+r₁  

r₀=r₁q₂+r₂  

…   …

r_k-2=r_k-1q_k+r_k 

r_k-1=r_kq_k+1

D(a,b)=r_k=r_k-2 -r_k-1q_k=r_k-2-(r_k-3-r_k-2q_k-1)q_k=…=ax+by

(1)  y₀=0, y₁=1, y_i+1=y_i-1-q_k+1-i

D(a,b)=ax_k+2+by_k+2

X_i+1=y_i

Рекуррентная последовательность

d=ax+by

76501=29719 2+17063

29719=17063 1+12056

17069=12056 1+4407

12056=4407 2+3842

4407=3842 1+565

3842=565 6+452

565=452 1+113

453=113 4

76501x+29719y=113

по формуле 1 находим y

d       1 6  1  2      1   1     2

y  1 –1 7 –8 23 –31 54 –139

y=-139 x=54

 обрываем процесс на 1 шаге, 2 и т.д.

d₀=q₀

d₁=q₀+1/q_1…

d₂=q₀+1/q₁+1/q_2… подходящие дроби

Вычисление подходящих дробей

d_k=-P_k/Q_k – подходящая дробь