Kongrüanslar Teorisi

dralekhine

April 2020

Teoremler (İspatsız)

Önerme 1.

$f(x,y)=0$ Diyofant denkleminin bir çözümü varsa $m\in \mathbb{N}$ için $f(x,y)\equiv 0(modm)$’dir

Önerme 2.

$a\equiv 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\equiv a_1(modm)$ ve $b\equiv b_1(modm)$ ise o zaman, $a+b\equiv a_1+b_1(modm)$’dir.

Önerme 4.

Eğer $a\equiv a_1(modm)$ ve $b\equiv b_1(modm)$ ise o zaman, $ab\equiv a_1{b}_1(modm)$’dir.

Önerme 5.

${\mathbb{Z}}_m$’de $\oplus$ işleminin aşağıdaki özellikleri vardır:

Her $\overline{a},\overline{b},\overline{c}\in {\mathbb{Z}}_m$ için,

(i) $\overline{a}\oplus \overline{b}=\overline{b}\oplus \overline{a}$’dir.

(ii) $\overline{a}\oplus (\overline{b}\oplus \overline{c})=(\overline{a}\oplus \overline{b})\oplus \overline{c}$’dir.

(iii) $\overline{a}\oplus \overline{0}=\overline{a}$’dir.

(iv) $\overline{a}\oplus \overline{x}=\overline{0}$ olacak biçimde $\exists \overline{x}\in {\mathbb{Z}}_m$ bulunabilir.

Önerme 6.

${\mathbb{Z}}_m$’de $\odot$ işleminin aşağıdaki özellikleri vardır:

Her $\overline{a},\overline{b},\overline{c}\in {\mathbb{Z}}_m$ için,

(i) $\overline{a}\odot (\overline{b}\odot \overline{c})=(\overline{a}\odot \overline{b})\odot \overline{c}$’dir.

(ii) $\overline{a}\odot \overline{b}=\overline{b}\odot \overline{a}$’dir.

(iii) $\overline{a}\odot \overline{1}=\overline{a}$’dir.

(iv) $\overline{a}\odot \overline{0}=\overline{0}$’dir.

Önerme 7.

Her $\overline{a},\overline{b},\overline{c}\in {\mathbb{Z}}_m$ için,

$$\overline{a}\odot (\overline{b}\oplus \overline{c})=(\overline{a}\odot \overline{b})\oplus (\overline{a}\odot \overline{c})$$

dir.

Önerme 8.

$a\equiv b(modm)\Rightarrow (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.

${\mathbb{Z}}_m$’deki $\overline{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.

${\mathbb{Z}}_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\in \mathbb{Z}$ olsun. $(a,m)=1$ koşulunu sağlayan her $a\in \mathbb{Z}$ için,

$$a^{\varphi (m)}\equiv 1(modm)$$

dir.

Sonuç 12.1 (Fermat).

Eğer $p$ asal tamsayı ise o zaman,

$$\forall a\in \mathbb{Z},p\nmid a$$

için, $a^{p-1}\equiv 1(modp)$ veya her $a\in \mathbb{Z}$ için $a^p\equiv a(modp)$’dir.

Önerme 13.

Eğer $ax\equiv b(modm)$’nin bir çözümü $x_0\in \mathbb{Z}$ ise o zaman, ${\overline{x}}_0\in {\mathbb{Z}}_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\equiv b(modm)$’nin bir çözümü olması için gerek ve yeter koşul $(a,m)|b$ olmasıdır.

Sonuç 15.1.

$ax\equiv 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 $(x_0,y_0)$ bir çözüm ise her $k\in \mathbb{Z}$ için,

$$x=x_0+\frac{b}{d}k\text{ ve }y=y_0-\frac{a}{d}k$$

de bir çözümdür.

Teorem 16.

$m,n\in \mathbb{Z}$ ve $d=(m,n)$ olsun.

	$x\equiv a(modm)$
	$x\equiv b(modn)$

denklik sisteminin çözümünün bulunabilmesi için gerek ve yeter koşul $a\equiv 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\equiv a(modm)$
	$x\equiv b(modn)$

denklik sisteminin çözümü var ve bu çözüm, $modmn$ tektir.

Önerme 17.

Eğer $(m,n)=1$ ise o zaman, $\varphi (mn)=\varphi (m)\varphi (n)$’dir.

Önerme 18.

$p$ bir asal sayı olmak üzere,

(i) $\varphi (p)=p-1=p(1-\frac{1}{p})$,

(ii) Her $a\in \mathbb{N}$ için $\varphi (p^a)=p^a-p^{a-1}=p^a(1-\frac{1}{p})$ ve

(iii) $m\in \mathbb{N}$’nin asal çarpanlara ayrılışı $m=p_1^{a_1}\mathrm{\dots }{p}_r^{a_r}$ ise,

$$\varphi (m)=\varphi (p_1^{a_1})\mathrm{\dots }\varphi (p_r^{a_r})=m(1-\frac{1}{p_1})\mathrm{\dots }(1-\frac{1}{p_r})$$

dir.

Teorem 19 (Wilson).

Her $p$ asal tam sayı için, $(p-1)!\equiv -1(modp)$’dir.

Teorem 20 (Çin Kalan Teoremi).

$m_1,\mathrm{\dots },m_r$ pozitif tam sayıları ikişer ikişer aralarında asal ve $b_1,\mathrm{\dots },b_r$ de keyfi tam sayılar olsun. Bu takdirde,

	$x\equiv b_1(mod{m}_1)$
	$x\equiv b_2(mod{m}_2)$
	$\mathrm{\dots }$
	$x\equiv b_r(mod{m}_r)$

kongrüans sisteminin bir çözümü var ve bu çözüm modülo $m_1,\mathrm{\dots },m_r$ tektir.

Teorem 21.

$m_1,\mathrm{\dots },m_r$ ikişer ikişer aralarında asal ve $m=m_1\mathrm{\dots }{m}_r$ olsun. $f(x)\equiv 0(modm)$ kongrüansının çözümünün olması için gerek ve yeter koşul her $i=1,\mathrm{\dots },r$ için, $f(x)\equiv 0(mod{m}_i)$’nin bir çözümü olmasıdır. Bu takdirde,

$$f(x)\equiv 0(mod{m}_i)$$

nin çözüm sayısı $N(m_i)$ ise,

$$f(x)\equiv 0(modm)$$

kongrüansının çözüm sayısı da $N(m)=N(m_1)\mathrm{\dots }N(m_r)$ olur.

Önerme 22.

$f(x)$ derecesi $n$ olan herhangi bir polinom olsun. O zaman,

(i)

$$f(x+y)=f(x)+\frac{f^{\prime }(x)}{1!}y+\mathrm{\dots }+\frac{f^n(x)}{n!}{y}^n$$

dir.

(ii) Eğer $f\in \mathbb{Z}[x]$ ise,

$$\frac{f^i(x)}{i!}$$

polinomlarının da katsayıları tam sayılardır.

Önerme 23.

$p$ asal ve $p\nmid a$ olsun. O zaman,

(i) ${\mathrm{ord}}_{p}a|p-1$

(ii) $a^k\equiv 1(modp)\iff {\mathrm{ord}}_{p}a|k$

(ii)

$${\mathrm{ord}}_p(a^k)=\frac{{\mathrm{ord}}_{p}a}{(k,{\mathrm{ord}}_{p}a)}$$

dir.

Önerme 24.

$g$ modülo $p$ bir primitif kök olsun. O zaman,aşağıdaki önermeler denktir:

(i) $g^r\equiv g^s(modp)$

(ii) $g^{-r}\equiv g^{-s}(modp)$

(iii) ${\mathrm{ord}}_{p}g=p-1|r-s$

Önerme 25.

$p$ asal tam sayı ve $p\nmid a$ olsun. Eğer $g$, modülo $p$ bir primitif kök ve $a\equiv g^b(modp)$ ise bu durumda, $x^n\equiv 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\nmid a$ ve $n>0$ olsun.Bu takdirde $x^n\equiv a(modp)$’nin bir çözümü olması için gerek ve yeter koşul,

$$(n,p-1)=s\text{ iken }{a}^{(p-1)/s}\equiv 1$$

olmasıdır.

İNDİR

Generated on Wed Apr 15 09:12:43 2020 by LaTeXML