Fermat’ın İki Kare Teoreminin Farklı İspatları

Teorem: Fermatın iki kare teoremi der ki ; 2 den farklı bir asal sayı iki kare toplamı olarak yazılabiliyorsa bu asal sayı 4k+1 şeklindedir. Diğer bir deyişle 4k+1 formundaki her asal iki kare toplamı olarak ve tek bir şekilde gösterilebilir.

P=x2 + y2 ancak ve ancak P ≡ 1 (mod4)

Fermat bunu söyledi ancak ispatını vermedi. İlk defa Euler 40 yaşında iken 1747 de bunun ispatını 5 adımda vermiştir. Daha sonra farklı ispatlar da bulunmuştur.

 

Euler’in Sürekli Serilere Dayalı İspatı

1.iki kare toplamı olarak yazılabilen iki sayının çarpımı da iki kare toplamı olarak gösterilebilir. Bu brahmagupta-Fibonacci özdeşliğidir.

(a2 + b2)(c2 + d2)=(ac-bd)2 + (ad + bc)2=(ac + bd)2 + (ad – bc)2

Örneğin : 5×13=65=12 + 82, 5=1 + 4 , 13= 4 + 9

2. İki kare toplamı olarak yazılabilen bir sayı iki kare toplamı olarak yazılabilen bir asal ile tam bölünebiliyorsa bölüm iki kare toplamı olarak gösterilebilir.

 Gerçekten de  , mesela (a2 + b2) sayısı (p2 + q2 )ile bölünebilsin. O halde (p2 + q2 ) ,

(pb − aq)(pb + aq) = p2b2 − a2q2 = p2(a2 + b2) − a2(p2 + q2) yi böler. (p2 + q2 ) asal olunca ,faktörlerden birini böler. Diyelim ki (pb − aq) yı bölsün

(a2 + b2)(p2 + q2)=(ap + bq)2 + (aq-bq)2 olduğundan beri bunu takiben p2 + q2 ,

(ap + bq)2yi bölmelidir.Bu nedenle eşitlik p2 + q2 tarafından bölünür.(p2 + q2)2 ile bölününce [(a2 + b2)/(p2 + q2)]=[(ap + bq)/(p2 + q2)] + [(aq- bp)/(p2 + q2)]2 çıkar.Bu iki kare toplamı olarak ifade edilebilmesi demektir.Eğer p2 + q2 , pb + aq yu bölerse yine benzer bir argüman  brahmagupta-fibonacci ilkesi

(a2 + b2)(p2 + q2)=(ap + bq)2 + (aq-bq)2 ,   kullanılarak ortaya çıkar.

3. Eğer İki kare toplamı olarak ifade edilebilen bir sayı iki kare toplamı olarak ifade edilemeyen bir sayı tarafından bölünebiliyorsa o halde sonucun faktörlerinden biri  iki kare toplamı olarak ifade edilemez.

   Farzedelim ki x , a2 + b2  yi böler. Bu durumda sonuç asal çarpanlarına ayrılırsa p1.p2….pn

o halde a2 + b2 = x.p1.p2….pn , eğer tüm asal faktörler iki kare toplamı ise o halde a2 + b2 p1.p2.. pn ile bölünebilir. Bir önceki adımı uygulayarak her sonucun iki kare toplamı olduğu sonucuna ulaşırız.Bu durumda eğer x iki kare toplamı olarak gösterilemiyorsa o halde asal çarpanlardan biri de iki kare toplamı olarak gösterilemez.

4. Eğer a ile b aralarında asal ise, o halde a2 + b2 nin tüm faktörleri iki kare toplamı olarak gösterilebilir.

  Bu sonsuz serileri kullanan bir adımdır. Diyelim ki x, a2 + b2 nin bir çarpanı, şunu yazabiliriz;

 

a = mx ± c , b = nx ± d , bu durumda

 

a2 + b2 = m2x2 ± 2mxc + c2 + n2x2 ± 2nxd + d2 = ax + (c2 + d2)

Bununla birlikte c2 + d2,  x ile bölünebilmelidir. c2 + d2 = yx olsun. Eğer c ile d aralarında asal değil ise o halde en büyük ortak bölenleri x ‘i bölemez(eğer bölseydi a ile b’yi de bölerdi ki aralarında asal olmalarıyla çelişirdi). Böylece en büyük ortak bölenlerinin karesi y’yi böler    (c2 + d2 ‘yi böldüğü gibi).Bu da bize şu eşitliği verir ki e ile f aralarında asal olmak üzere

e2 +f2= zx , (z , x/2 den büyük olmamak üzere).

 

zx = e2 + f2 ≤c2 + d2≤ (x/2)2 + (x/2)2 =x2/2 olduğundan beri ,

 

eğer c ile d aralarında asal ise onları e ile f  ile değiştirmeden doğrudan kullanabiliriz.

Eğer x iki kare toplamı değil ise , 3.adımdan , z’ nin iki kare toplamı olmayan bir çarpanı olmalıdır. Bu çarpana w diyelim. Bu x’den w’ye sonsuz bir seri verir. İkisi de iki kare toplamı değil ancak bir, iki kare toplamını bölen sayılar. Bu şekilde bir sonsuz seri mümkün olmadığından x’in iki kare toplamı olması gerektiği sonucuna erişiriz.

 

5. 4n+1 formundaki her asal iki kare toplamıdır.

 

Eğer p=4n+1 ise ,o halde fermat’ın küçük teoreminden ,1, 24n, 34n,…(4n)4n sayılarının her biri mod p’ye denktir. 24n -1 , 34n – 24n, …, (4n)4n – (4n-1)4n farklarının hepsi p ile bölünebilir.

Bu farkların hepsi şu şekilde gösterilebilir ;

 

a4n – b4n = (a2n + b2n)(a2n – b2n)

 

p asal olduğundan bu iki faktörden birini bölmelidir. 4n-1 ‘li lerden herhangi biri ilk faktörü bölüyorsa bir önceki adımdan görüldüğü gibi, p’nin kendisinin iki kare toplamı olduğu sonucuna ulaşırız(a ve b nin farkı 1 ,aralarında asal iken) . Bu yüzden bu p’nin ikinci faktörü her zaman bölemeyeceğini göstermek için yeterlidir. Eğer tüm 4n-1 farklarını bölerse

 22n – 1, 32n-22n ,…. , (4n)2n – (4n-1)2n o halde ardışık terimlerin tüm 4n-2 farklarını bölerdi ve farklarının tüm 4n-3 farklarınını da olduğu gibi..

1k, 2k, 3k … serisinin k’ncısı  k! ‘e eşit olduğundan beri ,2n’inci farkların hepsi sabit ve kesinlikle  p ile bölünemeyen  (2n)!’e eşit olurdu. Bununla beraber p , p’nin iki kare toplamı olduğunu kanıtlayan tüm ikinci faktörlerin hepsini bölemez .

 

Lagrange’nin Kuadratik Formlara Dayalı İspatı

Lagrange 1770’de kendisinin integral kuadratik formların genel teorisine dayalı bir ispat verdi.Aşağıdaki bu ispatın basite indirgenmiş halidir.

ax2 + 2bxy + cy2   ,a,b,c tamsayı olmak üzere bir kuadratik form alınacak olursa ,

 n = ax2 + 2bxy + cy2 ,olacak şekilde x,y var ve aynı kuadratik formda n vardır. O halde Fermat’ın iki kare teoremi x2 + y2 formunda bir p asalı vardır ki p≡1 (mod4) . Kuadratik formun diskriminantı b2 –ac olarak tanımlanır. X2 + y2 ‘nin diskriminantı ise -1 dir.

ax2 + 2bxy + cy2 ve  rx’2 + 2sx’y’ + ty’2 formları yalnızca ve yalnızca tamsayı katsayılı

x = αx’ + βy’

y = γx’ + δy’ 

 

 (αδ – βγ = ±1 olacak şekilde)

 

sayıları olduğunda eşittir. Eşit formların aynı diskriminanta sahip olduğu kolaylıkla görülebilir. Dahası eşit formlar aynı tamsayıları temsil edecektir.

Lagrange kanıtlamıştır ki diskriminantı −1  olan ve │b│≤ a ≤ c koşullarını sağlayan tüm formlar eşittir. Böylece Fermat’ın iki kare teoremini kanıtlamak için p’yi temsil eden ve diskriminantı -1 olan herhangi bir indirgenmiş form bulmak yeterlidir. Bunu yapmak için p , m2 + 1’i bölebilecek şekilde bir m sayısı bulmak yeterlidir. Böyle bir tamsayı bulmak için diskriminantı -1 olan şu formu gözönünde bulundurabiliriz;

 

Px2 + 2mxy + [ (m2 + 1)/p].y2

 

x=1 ve y=0 değerleri için p’ye eşittir.

Diyelim ki p=4n + 1 olsun . Şimdi Fermat’ın küçük teoremine başvuruyoruz. P ile aralarında asal olan herhangi bir z için , biliyoruz ki p, zp-1 -1 = z4n -1 = (z2n – 1)(z2n + 1)’i böler.Dahası , Lagrange’nin bir teoreminden , z2n – 1 ≡ 0 (mod p) kongrüansının 1,2,.., p-1=4n sayıları içinden en fazla 2n tane çözümü vardır. Bu nedenle p’deb daha küçük öyle z pozitif tamsayıları vardır ki p, z2n – 1 ‘i bölmez.Ancak p, z4n -1 = (z2n – 1)(z2n + 1)’yi bölmektedir. O halde p, z2n + 1’i bölmelidir. O halde m = zn  yazmak kanıtı tamamlar.

Erdös’ün Bertrand Postulatı Kanıtı

 

Erdös’ün Bertrand Postulatı  Kanıtı

 

Bertrand Postulatı : n > 1tamsayıları için,  n < p < 2n olacak şekilde her zaman  bir p asal sayısı vardır.

 

Bertrand postulatının ispatı, teta fonksiyonunun bazı basit özelliklerini içermektedir.

 teta(x), x  ≥  0 için belirtilir ki ,

 teta(x) = toplam (log p : p asal ve 0 < p ≤ x) .

  teta(x) < 2x log(2) olduğunu gösterelim.

 ( log(x),  x in doğal log’u olarak betimlenmiştir..)

 Bunu x tamsayı iken göstermek yeterlidir. Bunu tümeverımla kanıtlayacağız.

 Buradaki iş C(2m+1, m)’ in binom katsayılarındadır.

 C(2m+1, m) = (2m+1)! / m! . (m+1)!

 Bunun sonucuna  kısaca M diyelim.

 

p asalı m+1 < p ≤ 2m+1 aralığındaki bir asal olsun. O halde p , M ‘nin payını böler ancak paydasını bölemez. Bu yüzden p,  M’yi böler. O halde bu şekildeki tüm asallar M yi böler ve,

 toplam(log p: m+1 < p ≤ 2m+1) < log M

 ya da teta(x) fonksiyonunun ifadesiyle

 teta(2m+1) – teta(m+1) < log M.

 Diğer taraftan, (1 + 1) (2m+1) ‘ in binom açılımının M’ ye eşit iki tane terimi vardır. Bu yüzden

 2M < 2 (2m+1)

 M < 2 2m

 log M < 2m.log(2)

 Bu nedenle

teta(2m+1) – teta(m+1) < 2m.log(2)

 Bu formülü ispatımızdaki şu tümevarım adımında kullanacağız ;

 teta(x) < 2x log(2)

 x = 1 için,

 teta(1) = 0 < 2 log(2)

 ve x = 2 için ,

 teta(2) = log 2 < 4 log(2)

 Varsayın ki eşitsizlik x < n için doğru .x = n için bunu kanıtlayalım.

 Eğer n çift ve n> 2 ise , o halde kesinlikle bir asal değildir, bu yüzden

 teta(n) = teta(n-1) < 2(n-1) log(2) < 2n log(2).

 Eğer n tek ise n = 2m + 1 olsun. O halde yukarıda kanıtladığımız gibi,

 teta(2m+1) – teta(m+1) < 2m log(2)

teta(2m+1) < theta(m+1) + 2m log(2)< 2(m+1) log(2) + 2m log(2)

 = (3m + 1) log(2) < (4m + 2) log(2) = 2n log(2).

 

Bu, ispatı şu şekilde tamamlar,

 teta(x) < 2x log(2).

 Şimdi soluklanalım.

 Yapacağımız bir sonraki şey p asal olmak üzere p’ nin n! ‘i bölen en büyük kuvvetine bakmaktır. Buna j(n, p) diyoruz.

  [x] işaretini x ‘den küçük olan en büyük tamsayıyı belirtmek için kullanalım  [x] ≤ x.

 

p’ den sonraki her p’ inci sayı p’ nin bir katıdır. Bu yüzden n! sayısında [n / p] tane p çarpanı vardır. Ancak her p2 ‘ inci sayı da sadece p’ nin değil, p’ nin karelerinin de bir çarpanıdır.

,ve  [n / p] ‘ye bunlar dahil değildir. Bu nedenle [n / p2 ] ‘yi de eklememiz gerekir. Benzer şekilde her p3’ üncü sayı da p3 ‘lerin bir çarpanıdır. Bunları da eklemedik. Bu yüzden n! sayısını bölen p asalının en büyük kuvveti

 

 m ≥ 1 için  tüm  [n / pm]  sayılarının toplamıdır.

 

Tabi ki [n / pm] = 0 ,  pm > n olduğu sürece :  ,

 

m > log(n) / log(p) için.

 

Şimdi bertrand postulatının yanlış olduğunu varsayalım. ve, o halde n< p < 2n olan bir p asalı yoktur.

Şimdi bir başka binom açılımına bakacağız.

 

 C(2n , n) = (2n!) /( n!)2

 

Buna kısaca  N diyeceğiz.

Varsayımımızdan, N ‘i bölen ilgili asallar n’ den küçüktür. Şimdi

 

   N = (2n)! / (n!)2 =

 

       sonuç(p^j(2n, p): p ≤ 2n)

       —————————-

       sonuç(p^2j(n, p): p ≤ n)

 

ancak varsayımımıza göre  n ile 2n arasında hiç asal yoktur. Bu nedenle, paydaki  

“p ≤ 2n”  ile “p ≤ n” yer değiştirebilir. Sonuçta ,

 N = sonuç(p^(j(2n, p) – 2j(n, p)): p ≤ n).

 

j(2n, p) – 2j(n, p) ye kısaca  k(p)  diyelim. İki tarafın log’unu aldığımızda elimizde ;

 

   log N = toplam(k(p) log(p): p ≤ n) kalır.

 

k(p) nin , [2x] – 2[x] formunun toplamı olduğuna dikkat edin..

[2x] – 2[x] her zaman ya 0 ya da 1 ‘dir. Eğer [2x] çift sayı ise, [2x] – 2[x] 0’dır

; aksi halde 1’dir.

 

Öncelikle p > 2n / 3 için , k(p) = 0 olduğunu gösterelim. 

 

   2n/3 < p ≤ n

 Ya da   2 ≤ 2n/p < 3

 ve [2n / p] = 2, bu yüzden  [2n/p] – 2[n/p] = 0.

 n > 4 olduğu sürece,  p2 > (4 / 9)n2 > 2n  ‘dir.

 

Ve kesinlikle n>4 olduğunu , n ile 2n arasında asal olmadığını varsaydığımızdan beri varsayabilir, mesela 5, 4 ile 8 arasındadır.

 Bu nedenle p’nin daha büyük kuvvetlerini içeren terimler yoktur.

Şimdi  ,k(p) ≥ 2 olan terimlerin çok fazla katkıda bulunmadığını gösterelim.

 

Böyle bir terimin olması için p2 < 2n ya da p < (2n) olmalı, bu yüzden, bu tür terimlerin sayısı en fazla (2n)’dir.Diğer taraftan  k(p),  pm > 2n ise 0 , ya da m > log(2n) / log(p) olan

[2n / pm] – 2[n / pm] terimlerinin toplamıdır. Bu yüzden k(p) en fazla log(2n) / log(p), ve  k(p) log(p) ≤ log(2n) ‘dir. Bu nedenle,

 

  toplam(k(p) log(p) : k(p)≥  2) ≤ (2n) log(2n), bu şekildeki en fazla p asallarının olası sayısı ve herhangi  k(p) log(p) den büyük bir sayı

 

k(p) = 1 olan terimler için ,en fazla  

 toplam(log(p): p ≤ 2n/3) = teta(2n/3) < (4n/3) log(2)

 bunca adım sonrasını birleştirince bize şu sonucu verir

 

   log N < (4n/3) log(2) + (2n) log(2n).

 

N in tanımına bakarak , elimizde olan   

   22n = 2 + C(2n, 1) + C(2n, 2) + … + C(2n, 2n-1)

 

Bu 2n tane terimin bir toplamıdır.  Bu nedenle

 

   22n < 2n.N ‘dir.

 Ya da

 2n log(2) < log(2n) + log(N) ≤ log(2n) + (4n/3) log(2) + (2n) log(2n)

 

Daha önceki adımlarda kanıtlağığımız gibi , Şimdi n nin büyük değerleri için

,sağ tarafta sayılan tek terim 4n / 3 log(2) dir ve 2n.log(2) den küçüktür.

 

 Bu yüzden, yapacağımız şey bu eşitsizliği yanlış çıkarmak için n’ nin ne kadar büyük olabileceğini ortaya çıkarmaktır. Ve sonrasında postulatı n’ nin daha küçük değerleri için doğrudan kanıtlamaktır.

 

n ≥ 29  olsun ve dikkat edin ki  log(2n) = log(210) = 10 log(2). Eşitsizliği log(2) ile bölün. Sonuçta

 

 210 < 10 + 210 (2/3) + (25).10  , Ya da

 

 210 (1 – 2/3) < 10 (25 + 1),

 

   210 (1/3) < 10 (25 + 1),

 

   210 < 30 (25 + 1) < 31 (25 + 1) = (25 – 1) (25 + 1)= 2^10 – 1   , ki bu sonuç yanlıştır!

 

Bu nedenle Bertrand postulatının n ≥ 29 için yanlış olduğu varsayımımız bu sonuçla çelişmiştir. Geride yapılması gereken tek şey n < 29 = 512. Değerleri için postulatın doğru olduğunu göstermektir ki aşağıdaki, her biri bir öncekinin iki katından küçük olan  asal sayılar bunun için yeterlidir.

           2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631

 “An Introduction To Number Theory” /Hardy ,Wright  kitabından çevirilmiştir.

Teoremler – Kanıtlar

Tanım 1 : a, b ϵ Z olsun.

I) d│a ve d│b ise (d, a ile b’yi tam bölüyorsa) d’ye a ile b’nin  bir ortak böleni denir.

İİ) d, a ile b’nin bir ortak böleni ise ve a ile b’nin her ortak böleni ile tam bölünebiliyorsa d’ye a ile b’nin en büyük ortak böleni
denir ve(a,b)=d olarak gösterilir.

Tanım 2 : İki tam sayının en büyük ortak bölenleri 1 ise bu iki sayıya aralarında asal denir.

Önerme 1 : En az biri sıfırdan farklı, her a,b ϵ Z  nin ebob var ve tektir. Ayrıca, d=(a,b) ise d= ax + by olacak şekilde x, y ϵ Z
bulunabilir.

İspat

S={ ax +by : ax + by>0, a,b ϵ Z } diyelim. X=a, y=b için a2 + b2 >0 olduğundan a2+ b2 ϵ S ve S≠0 olur. S nin d gibi en küçük elemanı vardır. d=(a,b) olduğunu gösterelim. a yı d ile kalanlı bölelim. a= qd + r ve 0≤ r< d olacak şekilde q, r ϵ Z bulunabilir. d ϵ S, yani d= xm + yn şeklinde olduğundan, a=(q(xa + yb) +r => r=a(1 – qx) + b(-qy) dir. Bu durumda r≠ 0 ise r ϵ S olur ki , r<d olduğu için d ϵ S nin en küçük olması  ile çelişir. Bu durumda r=0, yani da olmalıdır. a ve b simetrik durumda olabildikleri için yani yer değiştirebildikleri için aynı şekilde db olduğu da gösterilebilir. Böylece d nin a ile b nin bir ortak böleni olduğu anlaşılır. e ϵ Z, ea ve eb olsun. A= eu ve b=ev olacak şekilde, u,v ϵ Z bulunabilir.

d=ax + by =x(eu) + y(ev) =e(xu + yv) olduğundan ed dir. Sonuçta d= (a,b) ve d ϵ S olduğundan x,y ϵ Z için d= ax + by olur.

EBOB
bulma metodu : a ve b pozitif tamsayılar olsun. Ard arda kalanlı bölme ile,

a=q1b + r1 ve
0<r1<a

b=q2r1 + r2
ve 0<r2<r1

r1 =q3r2
+ r3 ve 0<r3<r2

rk-1 =qk+1rk
+ rk+1 ve 0 <rk+1 < r k

r k    = q k+2 .rk+1 +0  ..
…………

Şeklinde kalan o oluncaya kadar devam edilir.

Teorem 1
(Euclid Algoritması) : Yukarıda ard arda yapılan kalanlı bölmeler arasında sıfırdan farklı en son kalan a ile b nin ebob’ dur.

İspat : rk nın a ile b nin bir ortak böleni olduğunu gösterelim. Kalanlı bölmelerdeki son eşitlikten, r k+1r k ve sondan bir önceki eşitlikten,r k+1q k+1rk + r k+1 = r k-1 ve böyle devam edilirse ;

r k+1rk,  r k-1 …,r1,a, b elde edilir. Şimdi e ϵ Z, ea ve eb ise erk+1 olacağını gösterelim.

en ve em => en-q1m=r1,

em ve er1 => em-q2r1=r2,

er1 ve er2 => er1– q3r2 =r3  ,  böyle devam edilirse er k+1 bulunur.

Örnek : 326 ile 111 in ebob unu bulalım.

326=2.111 + 104

111=1.104 + 7

104=14.7 + 6

14=2.6 + 2

2=2.1
, o halde (326, 111)= 1 dir.

Tanım 3: Katsayıları tamsayı olan polinom denkleminin tam sayı çözümlerini bulmaya diophan denklemini çözme denir.Bu
denklemlere diophant denklemleri denir.

Önerme 2 : a,b,c ϵ Z , a veya b sıfırdan farklı olmak üzere ax + by =c diophant denkleminin çözümünün olması için gerek ve yeter koşul d=(a,b) ise dc olmasıdır. Bu durumda sonsuz çözüm var ve bir çözüm (x1,y1) ise herhangi bir çözüm, k ϵ Z olmak üzere ;


x= x1 + (b/d).k ve y= y1 –(a/d).k olarak tek parametreye bağlıdır.

*Önermenin kanıtını düşününüz.

Örnek : 155x + 45y= 7 Diophant denklemi için  (155, 45)= 5 ve (5.7)=1 olduğundan uğraşmaya gerek yok , tamsayılarda çözümü yoktur.

Örnek 2: 155x + 45y= 15 Denklemini çözelim.

155 =3.45 + 20

45=2.20 + 5

20=4.5 + 0  ise (155, 45)= 5 ve

5= 1.45 – 2.20 = 1.45 –
2.(155-3.45)=1.45 – 2.155 +6.45 = (7.45 – 2.155)

5=(7.45 – 2.155) bulunur. Her iki
tarafı 3 ile çarparsak 15=21.45 – 6.155 olur ve

x1= -6, y1 =7  çözümleri bulunur. Buradan genel çözüm x= -6 + (45/5)k,  y= 7 – 155/5)k bir parametreye bağlı olarak bulunur.

Önerme 3 : a ≡ a1 (mod n) ve b ≡b1 (mod n) ise a+b ≡a1 + b1 (mod n) dir.

İspat : a≡a1 (mod n), b≡ b1 (mod n) => n│a-a1 , n│b-b1 => n│(a+b)-(a1+b1)=>a+b≡a1+b1 (mod n) olur.

Önerme 4 : a≡ a1 mod (n) ve b≡ b1 (mod n) ise ab≡ a1b1 (mod n) dir.

İspat : : a≡ a1 mod (n) ve b≡ b1 (mod n) => n│a-a1 ve n│b-b1 =>n│a1(b-b1)+b(a-a1) =>ab≡a1b1 (mod n) olur.

Önerme 5: a≡ b (mod n) => (a, n)=(b, n) dir.

İspat : a≡ b (mod n) => n│a-b => a=b+nk, k ϵ Z vardır.(a, n)=d olsun, d│a ve d│n olduğundan, d│b =a-nk dır. Bu
durumda d, b ile n nin bir ortak bölenidir. Eğer c herhangi bir ortak bölen ise
c│b ve c│n => c│a=b+nk olacağı için c│d = (a, n) elde edilir. Bu durumda d=(b,n) dir.

Tanım 4 : Pozitif n tam sayısı için 1 ≤ a ≤n ve (a, n)=1 olan a tam sayılarının sayısı Ø(n) ile gösterilir ve Euler Fonksiyonu
denir. Mesela Ø(5)=4 dür çünkü (1,5)=1, (2,5)=1, (3,5)=1, (4,5)=1  4 tanedir.  p bir asal ise Ø(p)=p-1 dir.

Teorem 2 [Euler Teoremi] : n ϵ Z , (a,n)=1 olan her a ϵ Z için 

aØ(n) ≡ 1 (mod n) dir.

Örnek : 330 ‘un 5 ile bölümünden kalan nedir?

Ø(5)=4 ve  34 ≡ 1 (mod 5) => (34)7
=328 ≡ 1 (mod 5) olduğundan , 330-28≡32≡ 4 (mod 5) bulunur.

Tanım 5 : ax ≡ b (mod n) şeklindeki bir denkleme bir bilinmeyenli lineer kongrüans denir. Bu denklemi sağlayan x tamsayılarının kümesine ise kongrüansın çözüm kümesi denir.

Önerme 6 : ax ≡ b (mod n ) nin bir çözümü olması için gerek ve yeter koşul (a,n)b olmasıdır.

Teorem 3:[Çin Kalan Teoremi]: m1, m2, .. mr pozitif tam sayılar ikişer ikişer aralarında asal ve b1, b2, …br
keyfi tam sayılar olsun. Bu taktirde

x≡ b1 (mod m1)

x≡ b2 (mod m2)

…………….

x≡ br (mod mr)

kongrüans sisteminin bir çözümü var ve bu çözüm mod m1, m2, .. mr tektir. Yani a ve b iki çözüm ise a≡ b (mod m1m2…mr) dir.

İspat :  m= m1m2m3…mr ve M i = m / mi , i =1, 2,…,r olsun. mi ler ikişer ikişer aralarında asal olduklarından (Mi , mi )=1 olur. Bu durumda Mi.x i ≡ 1 (mod m i ) kongrüansının mod m bir ve yalnız bir çözümü bulunduktan sonra

B= M1x1b1 + M2x2b2 + …+Mr xr br   dersek, b de verilen kongrüans sisteminin bir çözümü olur. Gerçekten de M ix i ≡1 (mod m i ) ve i≠ k  için, m k│M i olduğundan, b ≡ b1 (mod m i ), (i=1,2,..,r) bulunur. Şimdi çözümün, modülo n tekliğini gösterelim. a ve b kongrüans sisteminin iki çözümü olsun. Her i =1,2,…,r için a ≡  b(mod m i ), yani mi│a-b olacağından,

M = m1.m2…m r│a-b ve a≡ b (mod m) elde edilir.

*Polinom kongrüansları çin kalan teoremine göre çözülebilir.

Teorem 4 (Wilson ) : Her p asal tam sayısı için, (p-1)! ≡ -1 (mod p) dir.

İspat : p=2 için iddia doğrudur. p> 2 olsun. x2≡1 (mod p) <=> p(x-1)(x+1) =x2 -1 <=>
p
x-1 veya px+1 <=>x≡ 1 (mod p) veya x≡ -1 (mod p) olduğundan ,Z p de karesi 1‾, yani tersi kendine eşit olan sadece iki sınıf; 1‾ ve -1‾=(p-1)‾ dir. Bu durumda , her sınıfı tersi ile birlikte düşünerek, 2‾.3‾..(p-2)‾=1‾ ve 1‾.2‾..(p-1)‾=1‾.(p-1)‾=-1‾ <=> (p-1)! ≡ -1 (mod p) bulunur.

Bu teoremin tersi de doğrudur. n ϵ N ve (n-1)!≡ -1 (mod n) olsun. n asal olmasaydı 1<p<n ve (n-1)! ≡ 0 (mod p)
ve (n-1)! ≡-1 (mod n) => 0≡-1 (mod p) çelişkisi elde edilirdi. Bu durumda p asaldır. 

Takip Et

Her yeni yazı için posta kutunuza gönderim alın.

Diğer 26 takipçiye katılın