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. 

Reklamlar

The URI to TrackBack this entry is: https://aritmetik.wordpress.com/2011/05/10/teoremler-%e2%80%93-kanitlar/trackback/

RSS feed for comments on this post.

2 YorumYorum bırakın

  1. Ben İzmir çağdaş koleji 9 fen sınıfından yılmaz. Bu sayfayı çok begendim , matematiği farklı bir şekilde gösteriyor. İnşallah devam eder. Bir sorum okucaktı: Bir okuldan mısınız?
    Bir okuldansanız hangi okuldansınız? Teşekkür eder, iyi günler dileriz..

    • Merhaba Yılmaz. Ben Mühendisim. Matematik bölümünde okumadım, bu konulara ilgi duyan biri olarak matematiksel yetenekleri olabilecek kişilere faydalı olması amacı ile bu blogu açtım. Beğenmene sevindim.


Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

w

Connecting to %s

%d blogcu bunu beğendi: