Page 16 - ULUSAL ANTALYA MATEMATİK OLİMPİYATI 1. AŞAMA SORULARI VE ÇÖZÜMLERİ

Ön Bilgiler 15

I Öklid Algoritması ile OBEB’in Bulunması
Bölme algoritmasının art arda uygulanmasıyla
 =  1 +  1 0 ≤  1 

 =  1  2 +  2 0 ≤  2  1
 1 =  2  3 +  3 0 ≤  3  2
. . .

 −2 =  −1  −1 +   0 ≤    −1
 −1 =    +1 +0 +1 =0
elde edilecektir. Bu algoritmaya Öklid algoritması denilir. Burada kalanlar görüldü˘ gü
gibi 1  2      0 olmaktadır. 0 kalanından önce elde edilen son kalan   sayısı
ve  sayılarının OBEB’ini verir.
I Herhangi  ve  tamsayıları için ( )= (  + ) e¸sitli˘ gi sa˘ glanır.
I   pozitif tamsayılar ve  ∈ Z olsun +  =  denkleminin   tamsayı
çözümlerinin olması için
( )=  | 

olmalıdır. Bu durumda çözümler ( 0  0 ) bir özel çözüm olmak üzere
µ ¶
 
( )=  0 +   0 − 
 
formunda olur.
I Denklik
 pozitif bir tamsayı olmak üzere −  sayısı  sayısına tam bölünebiliyor ise
ve  sayıları modül ’ye göre denktirler denir ve  ≡  (mod ) ¸seklinde yazılır.
 ≡  (mod ) ifadesine denklik ya da kongruans adı verilir.
Ohalde ≡  (mod ) ⇔  |  −  ⇔  =  +  ( ∈ Z) sa˘ glanır.
 ≡  (mod ) ve  ≡  (mod ) ise  ±  ≡  ±  (mod ) ve her  ∈ N için,
 ≡  (mod ) olur.


I Fermat Teoremi
 birasalsayıolmak üzere ile  aralarında asal ise −1 ≡ 1(mod )’dir.
Bu teorem, bir tamsayının bir pozitif tamsayı kuvvetinin bir asal sayı ile bölünmesin­
den elde edilen kalanın bulunmasında sonuca daha kısa yoldan ula¸smamızı sa˘ glar.
Örne˘ gin 10 12 ≡ 1 (mod 13) 27 30 ≡ 1 (mod 31) 
¡ 30 ¢ 4 4
120
27 = 27 ≡ 1 ≡ 1 (mod 31)’dir.