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