Kongrüanslar Teorisi
April 2020
Teoremler (İspatsız)
Önerme 1.
f(x,y)=0 Diyofant denkleminin bir çözümü varsa m∈ℕ için f(x,y)≡0(modm)’dir
Önerme 2.
a≡b(modm) olması için gerek ve yeter koşul a ve b’nin m ile bölümlerinden kalanların aynı olmasıdır.
Önerme 3.
Eğer a≡a1(modm) ve b≡b1(modm) ise o zaman, a+b≡a1+b1(modm)’dir.
Önerme 4.
Eğer a≡a1(modm) ve b≡b1(modm) ise o zaman, ab≡a1b1(modm)’dir.
Önerme 5.
ℤm’de ⊕ işleminin aşağıdaki özellikleri vardır:
Her ˉa,ˉb,ˉc∈ℤm için,
(i) ˉa⊕ˉb=ˉb⊕ˉa’dir.
(ii) ˉa⊕(ˉb⊕ˉc)=(ˉa⊕ˉb)⊕ˉc’dir.
(iii) ˉa⊕ˉ0=ˉa’dir.
(iv) ˉa⊕ˉx=ˉ0 olacak biçimde ∃ˉx∈ℤm bulunabilir.
Önerme 6.
ℤm’de ⊙ işleminin aşağıdaki özellikleri vardır:
Her ˉa,ˉb,ˉc∈ℤm için,
(i) ˉa⊙(ˉb⊙ˉc)=(ˉa⊙ˉb)⊙ˉc’dir.
(ii) ˉa⊙ˉb=ˉb⊙ˉa’dir.
(iii) ˉa⊙ˉ1=ˉa’dir.
(iv) ˉa⊙ˉ0=ˉ0’dir.
Önerme 7.
Her ˉa,ˉb,ˉc∈ℤm için,
ˉa⊙(ˉb⊕ˉc)=(ˉa⊙ˉb)⊕(ˉa⊙ˉc) |
dir.
Önerme 8.
a≡b(modm)⇒(a,m)=(b,m)
Önerme 9.
İki asal kalan sınıfının çarpımı da bir asal kalan sınıfıdır.
Önerme 10.
ℤm’deki ˉ0’dan farklı bir kalan sınıfının sıfır bölen olması için gerek ve yeter koşul asal kalan sınıfı olmamasıdır.
Önerme 11.
ℤm’deki bir kalan sınıfının tersinin olması için gerek ve yeter koşul bir asal kalan sınıfı olmasıdır.
Teorem 12 (Euler).
m∈ℤ olsun. (a,m)=1 koşulunu sağlayan her a∈ℤ için,
aϕ(m)≡1(modm) |
dir.
Sonuç 12.1 (Fermat).
Eğer p asal tamsayı ise o zaman,
∀a∈ℤ,p∤a |
için, ap-1≡1(modp) veya her a∈ℤ için ap≡a(modp)’dir.
Önerme 13.
Eğer ax≡b(modm)’nin bir çözümü x0∈ℤ ise o zaman, ˉx0∈ℤm sınıfındaki tüm sayılar da çözümdür.
Önerme 14.
Eğer (a,m)=1 ise o zaman, ax=b(modm)’nin bir çözümü var ve modm tek bir sınıftır.
Önerme 15.
ax≡b(modm)’nin bir çözümü olması için gerek ve yeter koşul (a,m)|b olmasıdır.
Sonuç 15.1.
ax≡b(modm) kongrüansı verilsin. Eğer d=(a,m)|b ise o zaman, bu kongrüansın çözümleri modm d tane sınıftır.
Sonuç 15.2.
ax+by=c Diyofant denkleminin bir çözümü olması için gerek ve yeter koşul (a,b)=d|c olmasıdır. Bu takdirde sonsuz çözüm olup (x0,y0) bir çözüm ise her k∈ℤ için,
x=x0+bdk ve y=y0-adk |
de bir çözümdür.
Teorem 16.
m,n∈ℤ ve d=(m,n) olsun.
x≡a(modm) | ||
x≡b(modn) |
denklik sisteminin çözümünün bulunabilmesi için gerek ve yeter koşul a≡b(modd) olmasıdır. Bu takdirde çözüm, mod[m,n] tek bir sınıftır.
Sonuç 16.1.
Eğer (m,n)=1 ise o zaman,
x≡a(modm) | ||
x≡b(modn) |
denklik sisteminin çözümü var ve bu çözüm, modmn tektir.
Önerme 17.
Eğer (m,n)=1 ise o zaman, ϕ(mn)=ϕ(m)ϕ(n)’dir.
Önerme 18.
p bir asal sayı olmak üzere,
(i) ϕ(p)=p-1=p(1-1p),
(ii) Her a∈ℕ için ϕ(pa)=pa-pa-1=pa(1-1p) ve
(iii) m∈ℕ’nin asal çarpanlara ayrılışı m=pa11…parr ise,
ϕ(m)=ϕ(pa11)…ϕ(parr)=m(1-1p1)…(1-1pr) |
dir.
Teorem 19 (Wilson).
Her p asal tam sayı için, (p-1)!≡-1(modp)’dir.
Teorem 20 (Çin Kalan Teoremi).
m1,…,mr pozitif tam sayıları ikişer ikişer aralarında asal ve b1,…,br de keyfi tam sayılar olsun. Bu takdirde,
x≡b1(modm1) | ||
x≡b2(modm2) | ||
… | ||
x≡br(modmr) |
kongrüans sisteminin bir çözümü var ve bu çözüm modülo m1,…,mr tektir.
Teorem 21.
m1,…,mr ikişer ikişer aralarında asal ve m=m1…mr olsun. f(x)≡0(modm) kongrüansının çözümünün olması için gerek ve yeter koşul her i=1,…,r için, f(x)≡0(modmi)’nin bir çözümü olmasıdır. Bu takdirde,
f(x)≡0(modmi) |
nin çözüm sayısı N(mi) ise,
f(x)≡0(modm) |
kongrüansının çözüm sayısı da N(m)=N(m1)…N(mr) olur.
Önerme 22.
f(x) derecesi n olan herhangi bir polinom olsun. O zaman,
(i)
f(x+y)=f(x)+f′(x)1!y+…+fn(x)n!yn |
dir.
(ii) Eğer f∈ℤ[x] ise,
fi(x)i! |
polinomlarının da katsayıları tam sayılardır.
Önerme 23.
p asal ve p∤a olsun. O zaman,
(i) ordpa|p-1
(ii) ak≡1(modp)⇔ordpa|k
(ii)
ordp(ak)=ordpa(k,ordpa) |
dir.
Önerme 24.
g modülo p bir primitif kök olsun. O zaman,aşağıdaki önermeler denktir:
(i) gr≡gs(modp)
(ii) g-r≡g-s(modp)
(iii) ordpg=p-1|r-s
Önerme 25.
p asal tam sayı ve p∤a olsun. Eğer g, modülo p bir primitif kök ve a≡gb(modp) ise bu durumda, xn≡a(modp)’nin bir çözümü olması için gerek ve yeter koşul (n,p-1)|b olmasıdır.
Teorem 26 (Euler Kriteri).
p asal tam sayı, p∤a ve n>0 olsun.Bu takdirde xn≡a(modp)’nin bir çözümü olması için gerek ve yeter koşul,
(n,p-1)=s iken a(p-1)/s≡1 |
olmasıdır.
Hiç yorum yok:
Yorum Gönder