15 Nisan 2020 Çarşamba

Kongrüanslar Teorisi

Kongrüanslar Teorisi

Kongrüanslar Teorisi

dralekhine
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.
ab(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 aa1(modm) ve bb1(modm) ise o zaman, a+ba1+b1(modm)’dir.
Önerme 4.
Eğer aa1(modm) ve bb1(modm) ise o zaman, aba1b1(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.
ab(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,pa
için, ap-11(modp) veya her a için apa(modp)’dir.
Önerme 13.
Eğer axb(modm)’nin bir çözümü x0 ise o zaman, x¯0m 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.
axb(modm)’nin bir çözümü olması için gerek ve yeter koşul (a,m)|b olmasıdır.
Sonuç 15.1.
axb(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.
xa(modm)
xb(modn)
denklik sisteminin çözümünün bulunabilmesi için gerek ve yeter koşul ab(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,
xa(modm)
xb(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=p1a1prar ise,
ϕ(m)=ϕ(p1a1)ϕ(prar)=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,
xb1(modm1)
xb2(modm2)
xbr(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=m1mr 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 pa olsun. O zaman,
(i) ordpa|p-1
(ii) ak1(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) grgs(modp)
(ii) g-rg-s(modp)
(iii) ordpg=p-1|r-s
Önerme 25.
p asal tam sayı ve pa olsun. Eğer g, modülo p bir primitif kök ve agb(modp) ise bu durumda, xna(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ı, pa ve n>0 olsun.Bu takdirde xna(modp)’nin bir çözümü olması için gerek ve yeter koşul,
(n,p-1)=s iken a(p-1)/s1
olmasıdır.

Hiç yorum yok:

Yorum Gönder