Modüler Aritmetik

 

Modüler Aritmetik

 

\( x, y, m \in \mathbb{Z} \) ve \( m > 1 \) olmak üzere,

\[
\beta = \{ (x, y) : m \mid (x – y) \}
\]

\[
\beta = \{ (x,y) : x – y \text{ farkı } m \text{ ile tam bölünür} \}
\]

şeklinde tanımlanan bağıntı, denklik bağıntısıdır.

\(\beta\) bağıntısında \( x – y \), \( m \) ile tam bölündüğüne göre \( k \in \mathbb{Z} \) olmak üzere,

\[
x – y = m \cdot k \Rightarrow x = mk + y
\]

veya

\[  x \div  m = k + y \]

olur. Burada \( (x, y) \in \beta \) ve \( \beta \) denklik bağıntısı olduğundan \( x \), \( y \) ye denktir.

O halde \( \forall x \in \mathbb{Z} \) için \( x \) sayısı, \( x \) in \( m \) ye bölünmesinden elde edilen \( y \) kalanına denktir.
Bu denklik,

\[
x \equiv y \pmod{m}
\]

şeklinde yazılır. \( m \) modülüne göre \( x \) sayısı \( y \) ye denktir diye okunur.

 

Uyarı:

\[
x \equiv y \pmod{m} \iff x = mk + y \iff \frac{x – y}{m} = k, \quad k \in \mathbb{Z}
\]

 

Örnek:

\( 120 \equiv x \pmod{7} \) olduğuna göre \( x \) i bulalım.

\[
120 \equiv x \pmod{7} \Rightarrow 120 \div 7
\]

\[
120= 17 \cdot  7  + 1 , \quad \text{bölüm: } 17, \quad \text{kalan: } 1
\]

\[
\Rightarrow x = 1
\]

\[
\text{olup } 120 \equiv 1 \pmod{7}
\]

\[
x = 1 + 7k, \quad k \in \mathbb{Z}
\]

\[
x \in \{ \dots, -6, 1, 8, \dots \} \quad  \text{olarak bulunur.}
\]

 

Örnekler:

\(
\bullet
\)

\[
\begin{array}{r|l}
48 & 5 \\
45 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 9 \\
3 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 3 \pmod{5}
\]

 

\(
\bullet
\)

\[
\begin{array}{r|l}
48 & 5 \\
35 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 7 \\
13 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 13 \pmod{5}
\]

\(
\bullet
\)

\[
\begin{array}{r|l}
48 & 5 \\
50 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 10 \\
-2 &
\end{array}
\quad \Rightarrow \quad 48 \equiv -2 \pmod{5}
\]

 

 

Örnekler:

\(
\bullet \quad 25 \equiv 4 \pmod{7} \quad \Rightarrow \quad \frac{25 – 4}{7} = 3, \quad 3 \in \mathbb{Z}
\)

 

\(
\bullet \quad 25 \equiv 39 \pmod{7} \quad \Rightarrow \quad \frac{25 – 39}{7} = -2, \quad -2 \in \mathbb{Z}
\)

 

\(
\bullet \quad 25 \equiv 11 \pmod{7} \quad \Rightarrow \quad \frac{25 – 11}{7} = 2, \quad 2 \in \mathbb{Z}
\)

olarak yazılabilir.

 

Örnek:

\[
7x + 19 \equiv x – 2 \pmod{x}
\]

olduğuna göre, \( x \) in alabileceği değerleri bulalım.

\[
\frac{7x + 19 – (x – 2)}{x} = k \quad \Rightarrow \quad \frac{6x + 21}{x} = k
\]

\[
\Rightarrow 6 + \frac{21}{x} = k
\]

\( x > 1 \), \( x \in \mathbb{Z} \) ve \( k \in \mathbb{Z} \) olduğundan, \( x \) in alabileceği değerlerin kümesi
\[
\{ 3, 7, 21 \}
\]
dir.

 

SORU 1

\[
x^2 + 7x \equiv 15 \pmod{x}
\]

olduğuna göre, \( x \) in alabileceği kaç değer vardır?

\[
\text{A) 1} \quad \text{B) 2} \quad \text{C) 3} \quad \text{D) 4} \quad \text{E) 5}
\]

Çözüm:

\[
x^2 + 7x \equiv 15 \pmod{x} \Rightarrow \frac{x^2 + 7x – 15}{x} = k
\]

\[
\Rightarrow x + 7 – \frac{15}{x} = k
\]

\( x > 1 \), \( x \in \mathbb{Z} \) ve \( k \in \mathbb{Z} \) olduğundan, \( x \) in alabileceği değerler kümesi:

\[
\{ 3, 5, 15 \}
\]

\(\textbf{Cevab: C} \)

 

SORU 2

\( x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)} \) olduğuna göre, \( x \) in alabileceği değerlerin toplamı kaçtır?

\[
\text{A) 3} \quad \text{B) 4} \quad \text{C) 5} \quad \text{D) 6} \quad \text{E) 7}
\]

Çözüm:

\[
x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)}
\]

\[
\Rightarrow \frac{x^3 + x – (2x^2 + 2)}{x^3 + x} = k
\]

\[
\Rightarrow \frac{(x^2 + 1)(x – 2)}{x (x^2 + 1)} = k
\]

\[
\Rightarrow \frac{x – 2}{x} = k \Rightarrow 1 – \frac{2}{x} = k
\]

\( x^3 + x > 1 \), \( x \in \mathbb{Z} \) ve \( k \in \mathbb{Z} \) olduğundan, \( x \) in alabileceği değerler \( x_1 = 1, x_2 = 2 \) dir.

\[
\Rightarrow x_1 + x_2 = 3
\]

\(\textbf{Cevab: A} \)

 

Kalan Sınıfları:

 

Tam sayılar kümesinde tanımlanan

\[
\beta = \{ (x, y) \mid x – y \text{ farkı } m \text{ ile tam bölünür} \}
\]

denkliğin, tam sayılar kümesini denklik sınıflarına ayırdığını biliyoruz. Denklik sınıfları,

\[
\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1}
\]

Bu denklik sınıflarının kümesine \( m \) nin kalan sınıflarının kümesi denir ve \( \mathbb{Z}/m \) şeklinde gösterilir. Buna göre,

\[
\mathbb{Z} / m = \{ \overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1} \} \quad  \text{olur.}
\]

Örnek:

\( m = 5 \) için \( \beta = \{ (x, y) : 5 \mid (x – y) \} \) denklik bağıntısının, denklik sınıflarını bulalım.

Denklik sınıflarının kümesi,

\[
Z / 5 = \{ \overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4} \}
\]

tür.

Denklik sınıfları,

\[
\overline{0} = \{ \dots, -15, -10, -5, 0, 5, 10, 15, \dots \}
\]

\[
\overline{1} = \{ \dots, -14, -9, -4, 1, 6, 11, 16, \dots \}
\]

\[
\overline{2} = \{ \dots, -13, -8, -3, 2, 7, 12, 17, \dots \}
\]

\[
\overline{3} = \{ \dots, -12, -7, -2, 3, 8, 13, 18, \dots \}
\]

\[
\overline{4} = \{ \dots, -11, -6, -1, 4, 9, 14, 19, \dots \}
\]

olur.

\( Z / 5 \) te bir denklik sınıfındaki tüm elemanlar 5 modülüne göre birbirine denktir.

\( -11, 9 \in \overline{4} \) için,

\[
5 \mid (-11 – 9) \Rightarrow 5 \mid (-20) \Rightarrow -11 \equiv 9 \pmod{5}
\]

tir.

Ayrıca bir denklik sınıfındaki tüm sayıların 5 ile bölünmesinden bulunan kalanlar, o denklik sınıfını temsil eden sayıdır.

\( -11, 14, 19 \in \overline{4} \) için,

\[
\begin{array}{r|l}
-11 & 5 \\
-15 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & -3 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
14& 5 \\
10& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 2 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
19& 5 \\
15& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 3 \\
4 &
\end{array}
\]

Uyarı:

\( Z / m \) de denklik sınıflarını temsil eden sayılar \( 0, 1, 2, 3, \dots, m – 1 \) dir.

 

Özellikler:

 

\( x, y, a, b, m \in Z \) ve \( m > 1 \) için,

1)  \( x \equiv y \pmod{m} \) ve \( a \equiv b \pmod{m} \) olsun.

Aynı modüldeki denkliklerin iki yanı taraf tarafa toplanabilir, çıkarılabilir veya çarpılabilir. Fakat bölünemez.

\[
\begin{aligned}
x + a &\equiv y + b \pmod{m} \\
x – a &\equiv y – b \pmod{m} \\
x \cdot a &\equiv y \cdot b \pmod{m}
\end{aligned}
\]

Örnekler:

\( 7 \equiv 19 \pmod{6} \) ve \( 20 \equiv 2 \pmod{6} \) veriliyor.

\( \bullet \quad 7 + 20 \equiv 19 + 2  \pmod{6} \Rightarrow 27 \equiv 21 \pmod{6} \)

\( \bullet \quad 7 – 20 \equiv 19 – 2 \pmod{6} \Rightarrow -13 \equiv 17 \pmod{6} \)

\( \bullet \quad 7 \cdot 20 \equiv 19 \cdot 2 \pmod{6} \Rightarrow 140 \equiv 38 \pmod{6} \)

Sonuç:

\( \bar{p}, \bar{q} \in \mathbb{Z}/m \) için,

\[ \bar{p} + \bar{q} = \overline { p \;+ \; q } \]

\[ \bar{p} \cdot \bar{q} = \overline{p \;\cdot\; q} \]

 

Örnekler:

\( \mathbb{Z}/5 \) te,
\[
\bar{3} + \bar{4} \equiv \overline{3 + 4 } \equiv 2
\]
\[
\bar{3} \cdot \bar{4} \equiv \overline{3 \cdot   4 } \equiv 2
\]
\[
\bar{1} +\bar{ 2 }+ \bar{3 } \equiv \overline{ 1 + 2 + 3 } \equiv 1
\]

 

2) Bir denkleğin iki yanına \( c \in \mathbb{Z} \) sayısı eklenebilir veya çıkarılabilir.

\[
x \equiv y \pmod{m} \Rightarrow x + c \equiv y + c \pmod{m}
\]

\[
\Rightarrow x – c \equiv y – c \pmod{m}
\]

Örnekler:

\( \bullet \quad   27 \equiv 3 \pmod{8} \Rightarrow 27 + 5 \equiv 3 + 5 \pmod{8} \Rightarrow  \Rightarrow 32 \equiv 8 \pmod{8}
\)

\( \bullet \quad   27 \equiv 3 \pmod{8} \Rightarrow 27 – 3 \equiv 3 – 3 \pmod{8} \Rightarrow 24 \equiv 0 \pmod{8} \)

 

3) Bir denkleğin iki yanı \( c \in \mathbb{Z} \) sayısı ile çarpılabilir.

\[
x \equiv y \pmod{m} \Rightarrow x \cdot c \equiv y \cdot c \pmod{m}
\]

Örnek:

\( \bullet \quad 25 \equiv 1 \pmod{4} \Rightarrow 25 \cdot 3 \equiv 1 \cdot 3 \pmod{4} \Rightarrow 75 \equiv 3 \pmod{4} \)

4) Bir denkleğin iki yanının \( c \in \mathbb{Z} \) sayısı ile bölünmesi:

a) \( x \) ile \( m \) ve \( y \) ile \( m \) aralarında asal sayılar olmak üzere, denkliğin iki yanı \( c \in \mathbb{Z} \) sayısına bölünebilir.

\[x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{\frac{m}{c}} \]

 

Örnekler:

\( \bullet \quad   \) \[\Rightarrow  66 \equiv 3 \pmod{7} \Rightarrow \frac{66}{-3} \equiv \frac{3}{-3} \pmod{7} \Rightarrow -22 \equiv -1 \pmod{7} \]

\( \bullet \quad   \) \[
\Rightarrow  58 \equiv 22 \pmod{9} \Rightarrow \frac{58}{2} \equiv \frac{22}{2} \pmod{9} \Rightarrow 29 \equiv 11 \pmod{9}
\]

\(  \bullet \quad 40 \equiv 10 \pmod{6} \) denkliğinde 40 ile 6 ve 10 ile 6 aralarında asal sayılar olmadığından
40 ile 10 sadeleştirilemez. Yani,

\[
\frac{40}{10} \not\equiv \frac{10}{10} \pmod{6}
\]

\[
\Rightarrow 4 \not\equiv 1 \pmod{6}
\]

b) \( x, y \) ve \( m \) sayıların ortak bölenlerinin en büyüğü \( c \) olmak üzere,

\[
x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{\frac{m}{c}}
\]

Örnek:

\( \bullet \quad 40 \equiv 10 \pmod{6} \Rightarrow \frac{40}{2} \equiv \frac{10}{2} \pmod{\frac{6}{2}} \Rightarrow 20 \equiv 5 \pmod{3}
\)

Burada 20 ile 3 ve 5 ile 3 aralarında asal sayılar olduğundan,

\[
\frac{20}{5} \equiv \frac{5}{5} \pmod{3}
\]

\[
\Rightarrow 4 \equiv 1 \pmod{3}
\]

5) \( n \in \mathbb{Z}^+ \) olmak üzere, bir denkleğin iki yanının \( n \) inci kuvveti alınabilir.

\[
x \equiv y \pmod{m} \Rightarrow x^n \equiv y^n \pmod{m}
\]

 

Örnek:

\[
96 \equiv 5 \pmod{7} \Rightarrow (96)^{10} \equiv 5^{10} \pmod{7}
\]

Uyarı:

\( k \in \mathbb{Z} \) ve \( a \) üs olmamak üzere,

\( \mathbb{Z}/m \) de yapılan matematiksel işlemlerde \( a \) sayısı yerine \( a + mk \) yazılabilir. Yani \( a \) ya, \( a \) nın tam katları eklenebilir veya çıkarılabilir.

Örnekler:

\( Z / 5 \) te,

\( \bullet \quad 3 \cdot 4 + 3^4 + 4^3 \cdot 3 = 2 + 1 + 4 \cdot 3 = 2 + 1 + 2 = 0 \)

\( \bullet \quad (2x + 3) \cdot (x + 4) = 2x^2 + 2 \cdot 4x + 3x + 3 \cdot 4 = 2x^2 + (3 + 3)x + 2\)

\[
\quad = 2x^2 + x + 2
\]

\( \bullet \quad f(x) = 3x + 4 \Rightarrow (fof(x)) = f(f(x)) \)

\[
\quad = 3 \cdot (3x + 4) + 4 = 3 \cdot 3x + 3 \cdot 4 + 4
\]

\[
\quad = 4x + 2 + 4
\]

\[
\quad = 4x + 1 \quad \text{dir.}
\]

Örnek:

\( Z / 7 \) de 3 sayısının, toplama ve çarpmaya göre tersini bulalım.

3 sayısının toplamaya göre tersi \( x \), çarpmaya göre tersi \( y \) olsun.

\[
3 + x = 0
\]

\[
\Rightarrow 3 + 4 + x = 0 + 4
\]

\[
\Rightarrow x = 4 \text{ tür.}
\]

\[
3 \cdot y = 1 \Rightarrow 5 \cdot 3y = 5 \cdot 1
\]

\[
\Rightarrow 1 \cdot y = 5
\]

\[
\Rightarrow y = 5 \text{ tir.}
\]

Uyarı:

\( Z/m \) de herhangi bir \( x \) elemanının toplama işlemine göre tersini \( -x \), çarpma işlemine göre tersini, eğer varsa, \( x^{-1} = \frac{1}{x} \) şeklinde gösterelim. Buna göre herhangi iki \( x, y \) elemanı için

\[
\frac{y}{x} = y \cdot \frac{1}{x} \quad \text{ olarak alalım.}
\]

Örnek:

\( Z / 5 \) te,

\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]

işleminin sonucunu bulalım.

\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]

\[
= (3 \cdot 2^{-1})^3 + (3^{-1})^5 + (-4)^{100}
\]

burada,

\( \bullet \quad   2^{-1} = x \) olsun. \( x, 2 \) nin çarpmaya göre tersidir.

\( \bullet \quad   3^{-1} = y \) olsun.  \(y, 3  \)  ün çarpmaya göre tersidir.

\( \bullet \quad   -4 = z \)  olsun.  \(z, 4 \)  ün toplamaya göre tersidir.

O halde,

\[
2x = 1 \Rightarrow 3 \cdot 2x = 3 \cdot 1
\]

\[
\Rightarrow x = 3 \text{ olur.}
\]

\[
3y = 1 \Rightarrow 2 \cdot 3y = 2 \cdot 1 \Rightarrow y = 2 \text{ olur.}
\]

\[
4 + z = 0 \Rightarrow z = 1 \text{ olur.}
\]

\[
A = (3 \cdot 3)^3 + 2^5 + 1^{100}
\]

\[
= 4^3 + 2 + 1
\]

\[
= 4 + 2 + 1 = 2 \text{ dir.}
\]

Örnek:

Yukarıdaki örnekte verilen işlemi ikinci bir yolla yapalım. \( Z / 5 \) te işlemler yaparken; işlem yapılan sayılara 5 in katlarını ekleyebilir veya çıkarabiliriz.

\[
Z / 5 \text{ te,}
\]

\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]

\[
= \left( \frac{3 + 5}{2} \right)^3 + \left( \frac{1 + 5}{3} \right)^5 + (-4 + 5)^{100}
\]

\[
= 4^3 + 2^5 + 1^{100}
\]

\[
= 4 + 2 + 1 = 2 \text{ dir.}
\]

Örnek:

\[
Z / 7 \text{ de,}
\]

\[
(-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4 \text{ işleminin sonucunu bulalım.}
\]

\[
(-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4
\]

\[
= (-5 + 7)^5 + \left( \frac{1}{5} \right)^3 + \left( \frac{1+7}{2} \right)^4
\]

\[
= 2^5 + \left( \frac{1 + 7 + 7}{5} \right)^3 + 4^4
\]

\[
= 4 + 3^3 + 4
\]

\[
= 4 + 6 + 4 = 0 \text{ dır.}
\]

Uyarı:

\( Z/m \) de \( x^n = a \) olan denklemin çözümünü

\[
x = \sqrt[n]{a}
\]

şeklinde gösterelim.

Örnek:

\[
Z / 7 \text{ de,}
\]

\[  \quad   \sqrt{2}, \quad \sqrt{1} \quad \text{ve } \quad    \sqrt[3]{6} \quad \] işlemlerini yapalım.

\( \bullet \quad \sqrt{2} = \sqrt{2 + 7} = 3, \quad \sqrt{2} = \sqrt{2 + 2 \cdot 7} = 4 \} \)

\( \bullet \quad \sqrt{1} = 1, \quad \sqrt{1} = \sqrt{1 + 5 \cdot 7} = 6 \)

\( \bullet \quad \sqrt[3]{6} = \sqrt[3]{6 + 3 \cdot 7} = 3, \quad \sqrt[3]{6} = \sqrt[3]{6 – 7} = -1 = 6 \)

\[ \sqrt[3]{6} = \sqrt[3]{6 – 2 \cdot 7} = \sqrt[3]{-8} = -2 = 5 \quad \text{tir.} \]

 

Veya \( \sqrt{1} \) ile \( \sqrt{2} \) yi \( Z / 7 \) de çarpma işleminin tablosundan görmek mümkündür. Tabloda köşegen üzerindeki elemanların karekökleri vardır.

\[
\begin{array}{c|ccccccc}
\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & \fbox{1} & 2 & 3 & 4 & 5 & 6 \\
2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\
3 & 0 & 3 & 6 & \fbox{2} & 5 & 1 & 4 \\
4 & 0 & 4 & 1 & 5 & \fbox{2} & 6 & 3 \\
5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\
6 & 0 & 6 & 5 & 4 & 3 & 2 & \fbox{1} \\
\end{array}
\]

\[
\sqrt{2} = \sqrt{3 \cdot  3} = 3
\]

\[
\sqrt{2} = \sqrt{4 \cdot 4 } = 4
\]

\[
\sqrt{1} = \sqrt{1\cdot 1 }  = 1
\]

\[
\sqrt{1} = \sqrt{6\cdot 6 } = 6
\]

Örnek:

\[
Z / 6 \text{ da,}
\]

\[
f(x) = 5x + 4 \text{ veriliyor. } f^{-1}(x) \text{ i bulalım.}
\]

\[
y = f(x) = 5x + 4 \Rightarrow y + 2 = 5x + 4 + 2
\]

\[
\Rightarrow y + 2 = 5x
\]

\[
\Rightarrow 5(y + 2) = 5 \cdot 5x
\]

\[ 5y + 5 \cdot  2= x \Rightarrow 5y + 4 = x= f^{-1}(y)     \]

\[ f^{-1}(x)= 5x+4 \quad  \text{olarak bulunur. }     \]

Uyarı:

\( Z/m \) de \( ax + b = 0 \) denklemi verilsin.

\[
d = OBEB(m, a)\quad   \text{ olmak üzere } \quad   \frac{b}{d} = k \quad  \text{ olsun. }  \quad  k \in \mathbb{Z}
\] ise denklemin çözüm kümesi boş kümeden farklıdır.  Çözüm kümesinin eleman sayısı ise \( d \) dir.

Örnek:

\( Z / 7 \) de,

\[
5x + 4 = 0 \text{ denkleminin çözümünü yapalım.}
\]

\[
5x + 4 = 0 \Rightarrow 5x + 4 + 3 = 0 + 3
\]

\[
\Rightarrow 5x = 3 \Rightarrow 3 \cdot 5x = 3 \cdot 3 \Rightarrow x = 2
\]

Örnek:

\[ Z / 6 \quad  \text{da}  \]

\[
2x = 2 \text{ denklemini sağlayan en küçük pozitif iki sayıyı bulalım.}
\]

\[
2x = 2 \pmod{6} \Rightarrow \frac{2x}{2} = \frac{2}{2} \pmod{\frac{6}{2}}
\]

\[
\Rightarrow x \equiv 1 \pmod{3}
\]

O halde,

\[
Z / 6 \text{ da } 2x = 2 \Rightarrow Z / 3 \text{ te } x = 1
\]

olacağından,

\[
x_1 = 1 \quad \text{ve} \quad x_2 = 1 + 3 = 4 \text{ tür.}
\]

Örnek:

\[ Z / 5 \quad  \text{te,} \]

\[
x^2 + 4x = 2 \text{ denkleminin çözüm kümesini bulalım.}
\]

\[
x^2 + 4x = 2 \Rightarrow x^2 + 4x + 3 = 2 + 3
\]

\[
\Rightarrow x^2 + 4x + 3 = 0
\]

\[
\Rightarrow (x + 1)(x + 3) = 0
\]

\[
\Rightarrow x + 1 = 0 \quad \text{veya} \quad x + 3 = 0
\]

\[
\Rightarrow x = 4 \quad \text{veya} \quad x = 2
\]

olduğundan,

\[
Ç = \{2, 4\}
\]

Örnek:

\[
(Z / 7)^2 \text{ de,}
\]

\[
\begin{cases}
x + 2y = 1 \\
2x + 3y = 6
\end{cases}
\]

denklem sistemini sağlayan y nin değerini bulalım.

\[
x + 2y = 1 \Rightarrow 5(x + 2y) = 5 \cdot 1
\]

\[
\Rightarrow 5x + 3y = 5
\]

\[
\begin{array}{rcl}
5x + 3y & = & 5 \\
+ \quad 2x + 3y & = & 6 \\
\hline
6y & = & 4
\end{array}
\]

\[
\Rightarrow 6 \cdot 6y = 6 \cdot 4
\]

\[
\Rightarrow y = 3 \text{ olarak bulunur.}
\]

Örnek:

\[
3^{27} \equiv x \pmod{5} \text{ ise } x \text{ i bulalım.}
\]

\[
3^1 \equiv 3 \pmod{5}
\]

\[
3^2 \equiv 4 \pmod{5}
\]

\[
3^3 \equiv 2 \pmod{5}
\]

\[
3^4 \equiv 1 \pmod{5} \Rightarrow (3^4)^6 \equiv 1^6 \pmod{5}
\]

\[
\Rightarrow 3^3 \cdot 3^{24} \equiv 3^3 \cdot 1 \pmod{5}
\]

\[
3^3 \equiv 2 \pmod{5} \text{ olduğundan,}
\]

\[
\Rightarrow 3^{27} \equiv 2 \pmod{5}
\]

\[
\text{O halde } x = 2 \text{ olarak bulunur.}
\]

Örnek:

\((1997)^{28} \)  sayısının 7 ile bölümünden kalan  \( x\)  in değerini bulalım.

\[

(1997)^{28} \equiv x \pmod{7} \text{ denklemi}
\]

\[
1997 \equiv 2 \pmod{7} \text{ olduğundan,}
\]

\[
(1997)^{28} \equiv 2^{28} \pmod{7} \Rightarrow 2^{28} \equiv x \pmod{7}
\]

\[
2^1 \equiv 2 \pmod{7}
\]

\[
2^2 \equiv 4 \pmod{7}
\]

\[
2^3 \equiv 1 \pmod{7}
\]

\[
(2^3)^9 \equiv 1^9 \pmod{7}
\]

\[
2 \cdot 2^{27} \equiv 2 \cdot 1 \pmod{7}
\]

\[
2^{28} \equiv 2 \pmod{7}
\]

\[
\text{O halde } x = 2 \text{ olarak bulunur.}
\]

SORU 3

\( (1994)^{1996} \equiv x \pmod{5}\) ise \( x\) kaçtır?

\[
\text{A) 0} \quad \text{B) 1} \quad \text{C) 2} \quad \text{D) 3} \quad \text{E) 4}
\]

Çözüm:

\[
1994 \equiv -1 \pmod{5} \Rightarrow (1994)^{1996} \equiv (-1)^{1996} \pmod{5}
\]

\[
\Rightarrow (1994)^{1996} \equiv 1 \pmod{5}
\]

\[
\text{O halde } x = 1 \text{ dir.}
\]

\(\textbf{Cevab: B} \)

 

SORU 4

\[
(20)^{90} \equiv x \pmod{9} \text{ ise } x \text{ kaçtır?}
\]

\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]

Çözüm:

\[
20 \equiv 2 \pmod{9} \Rightarrow (20)^{90} \equiv 2^{90} \pmod{9}
\]

\[
2^1 \equiv 2 \pmod{9}
\]

\[
2^2 \equiv 4 \pmod{9}
\]

\[
2^3 \equiv -1 \pmod{9}
\]

\[
(2^3)^{30} \equiv (-1)^{30} \pmod{9}
\]

\[
2^{90} \equiv 1 \pmod{9}
\]

\[
\text{O halde } x = 1 \text{ dir.}
\]

\(\textbf{Cevab: B} \)

SORU 5

\[
6^{25} \cdot 7^{13} \text{ çarpımının 5 ile bölümünden kalan kaçtır?}
\]

\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]

Çözüm:

\[
6^{25} \cdot 7^{13} \equiv x \pmod{5} \text{ denkliğinde } x \text{ i bulacağız.}
\]

\[
6 \equiv 1 \pmod{5} \Rightarrow 6^{25} \equiv 1^{25} \pmod{5}
\]

\[
\Rightarrow 6^{25} \equiv 1 \pmod{5}
\]

\[
7 \equiv 2 \pmod{5} \Rightarrow 7^4 \equiv 2^4 \pmod{5}
\]

\[
\Rightarrow (7^4)^3 \equiv 1^3 \pmod{5}
\]

\[
\Rightarrow 7 \cdot 7^{12} \equiv 7 \cdot 1 \pmod{5}
\]

\[
\Rightarrow 7^{13} \equiv 2 \pmod{5}
\]

\[
\text{O halde, } 6^{25} \equiv 1 \pmod{5} \text{ ve } 7^{13} \equiv 2 \pmod{5} \text{ olduğundan,}
\]

\[
6^{25} \cdot 7^{13} \equiv 1 \cdot 2 \pmod{5}
\]

\[
\Rightarrow x = 2
\]

\(\textbf{Cevab: C} \)

Uyarı:

\( x \)  ile  \( m \) aralarında asal sayılar ve  \( m \) de asal sayı olmak üzere,

\[
x^{m-1} \equiv 1 \pmod{m} \text{ dir.}
\]

Ancak \( m – 1 \) den daha küçük bir kuvvette de denklemin sağ yanında \( 1 \) sayısı elde edilebilir.

Örnekler:

\[
2^{10} \equiv 1 \pmod{11}
\]

\[
6^{22} \equiv 1 \pmod{23}
\]

SORU 6

\[
7^{61} \equiv x \pmod{11} \text{ ise } x \text{ kaçtır?}
\]

\[
\text{A) } 4 \quad \text{B) } 5 \quad \text{C) } 6 \quad \text{D) } 7 \quad \text{E) } 8
\]

Çözüm:

\[
m = 11 \Rightarrow m – 1 = 10 \text{ olduğundan,}
\]

\[
7^{10} \equiv 1 \pmod{11}
\]

\[
(7^{10})^6 \equiv 1^6 \pmod{11}
\]

\[
7^{60} \equiv 1 \pmod{11}
\]

\[
7 \cdot 7^{60} \equiv 7 \cdot 1 \pmod{11}
\]

\[
7^{61} \equiv 7 \pmod{11} \text{ olup } x = 7 \text{ dir.}
\]

\(\textbf{Cevab: D} \)

SORU 7

\[
5^{120} \equiv x \pmod{13} \text{ ise } x \text{ kaçtır?}
\]

\[
\text{A) } 1 \quad \text{B) } 5 \quad \text{C) } 7 \quad \text{D) } 9 \quad \text{E) } 11
\]

Çözüm:

\[
m = 13 \Rightarrow m – 1 = 12 \text{ olduğundan,}
\]

\[
5^{12} \equiv 1 \pmod{13}
\]

\[
(5^{12})^{10} \equiv 1^{10} \pmod{13}
\]

\[
5^{120} \equiv 1 \pmod{13} \text{ olup } x = 1 \text{ dir.}
\]

\(\textbf{Cevab: A} \)

Uyarı:

\( x^n \equiv y \pmod{m} \)  denkliğinde  \( m  \) ile  \( x \) aralarında asal sayılar değilse denkliğin sağ tarafında \( 1 \)  sayısı elde edilemez. Buna karşılık denklemin sağ tarafında \( 0 \) (sıfır) veya tekrarlanan bir sayı dizisi elde edilir.

Örnek:

\[
(18)^{100} \equiv 0 \pmod{64}
\]

SORU 8

\[
2^{100} \text{ sayısının 6 ile bölümünden elde edilen kalan kaçtır?}
\]

\[
\text{A) } 1 \quad \text{B) } 2 \quad \text{C) } 3 \quad \text{D) } 4 \quad \text{E) } 5
\]

Çözüm:

\[
2^{100} \equiv x \pmod{6} \text{ denkliğinde } x \text{ i bulacağız.}
\]

\[
2^1 \equiv 2 \pmod{6}
\]

\[
2^2 \equiv 4 \pmod{6}
\]

\[
2^3 \equiv 2 \pmod{6}
\]

\[
2^4 \equiv 4 \pmod{6}
\]

\[
\vdots
\]

\[
2^{99} \equiv 2 \pmod{6}
\]

\[
2^{100} \equiv 4 \pmod{6} \text{ olduğundan } x = 4 \text{ tür.}
\]

\(\textbf{Cevab: D} \)

 

Uyarı:

\(x^n \equiv y \pmod{m} \) denkliğinde \( x \)  ile \( m \)  aralarında asal sayılar olmak üzere,  \(m \) nin asal çarpanlarına ayrılmış şekli,

\[
m = a^p \cdot b^r \cdot c^s \cdots \text{ olsun.}
\]

\[
z = m \cdot \left( 1 – \frac{1}{a} \right) \cdot \left( 1 – \frac{1}{b} \right) \cdot \left( 1 – \frac{1}{c} \right) \cdots \text{ ise}
\]

\[
x^z \equiv 1 \pmod{m} \text{ olur.}
\]

 

SORU 9

\( (1997)^{62}  \)  sayısının birler basamağındaki rakam kaçtır?

\[
\text{A) } 5 \quad \text{B) } 6 \quad \text{C) } 7 \quad \text{D) } 8 \quad \text{E) } 9
\]

Çözüm:

Bir sayının birler basamağındaki rakam bu sayının 10 ile bölümünden kalan sayıdır.

\[
(1997)^{62} \equiv x \pmod{10} \text{ denkliğinde } x \text{ i bulacağız.}
\]

\[
1997 \equiv 7 \pmod{10} \text{ olduğundan,}
\]

\[
(1997)^{62} \equiv 7^{62} \pmod{10} \Rightarrow 7^{62} \equiv x \pmod{10}
\]

\[
m = 10 = 2 \cdot 5 \Rightarrow z = 10 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 4
\]

O halde,

\[
7^4 \equiv 1 \pmod{10}
\]

\[
(7^4)^{15} \equiv 1^{15} \pmod{10}
\]

\[
7^2 \cdot 7^{60} \equiv 7^2 \cdot 1 \pmod{10}
\]

\[
7^2 \equiv 9 \pmod{10} \text{ olduğundan,}
\]

\[
\Rightarrow 7^{62} \equiv 9 \pmod{10}
\]

buradan \( x = 9 \) dur.

\(\textbf{Cevab: E} \)

 

SORU 10

\[
(21)^{202} \text{ sayısının son iki basamağındaki iki rakamın meydana getirdiği sayı kaçtır?}
\]

\[
\text{A) } 01 \quad \text{B) } 21 \quad \text{C) } 41 \quad \text{D) } 61 \quad \text{E) } 81
\]

Çözüm:

\[
(21)^{202} \equiv x \pmod{100} \text{ denkliğinde } x \text{ soruluyor.}
\]

\[
m = 100 = 2^2 \cdot 5^2
\]

\[
\Rightarrow z = 100 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 40
\]

\[
(21)^{40} \equiv 1 \pmod{100}
\]

\[
((21)^{40})^5 \equiv 1^5 \pmod{100}
\]

\[
(21)^2 \cdot (21)^{200} \equiv (21)^2 \cdot 1 \pmod{100}
\]

\[
(21)^{202} \equiv 441 \pmod{100}
\]

burada \( 441 \equiv 41 \pmod{100} \) olduğundan

\[
(21)^{202} \equiv 41 \pmod{100}
\]

olup \( x = 41 \) dir.

\(\textbf{Cevab: C} \)

 

SORU 11

\[
3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5} \text{ ise } x \text{ kaçtır?}
\]

\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]

Çözüm:

\[
3 \equiv -2 \pmod{5}, \quad 6 \equiv 1 \pmod{5}
\]

\[
4 \equiv -1 \pmod{5}, \quad 12 \equiv 2 \pmod{5} \text{ olduğundan,}
\]

\[
3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5}
\]

\[
\Rightarrow (-2)^{27} + (-1)^{27} + 1^{27} + 2^{27} \equiv x \pmod{5}
\]

\[
\Rightarrow 0 \equiv x \pmod{5}
\]

buradan \( x = 0 \) dır.

\(\textbf{Cevab: A} \)