Sayılar Teorisi Soru Çözümü

Öklid Algoritması adımlarını kontrol edelim:
$252 = 198 \cdot 1 + 54$ → $252 \div 198 = 1$ kalan $54$, doğru.
$198 = 54 \cdot 3 + 36$ → $198 \div 54 = 3$ kalan $36$, doğru.
$54 = 36 \cdot 1 + 18$ → $54 \div 36 = 1$ kalan $18$, doğru.
$36 = 18 \cdot 2 + 0$ → $36 \div 18 = 2$ kalan $0$, doğru.

Kalan sıfır olduğunda, son sıfır olmayan kalan 18'dir, yani $\gcd(252, 198) = 18$. Bu nedenle, adımlar doğru ve EBOB 18'dir.

Diğer seçenekler ya yanlış adımları gösterir ya da yanlış EBOB değerini verir.

Modüler aritmetikle bir sayının asal olmadığını göstermek için, sayının bir asal sayıya bölündüğünü (yani mod 0 verdiğini) bulmak gerekir. 111 sayısının rakamları toplamı $1+1+1=3$ olduğundan, 3'e bölünebilme kuralına göre:

$$111 \mod 3 = 0$$

Bu nedenle 111, 3'e bölünür ve asal değildir. Diğer sayılar (101, 103, 107, 109) küçük asallarla test edildiğinde bölünmezler ve asal oldukları bilinir (ancak bu soruda sadece 111 için basit mod hesaplaması yapılabilir).

$2$ ve $9$ aralarında asal olduğu için Euler teoremine göre $2^{\phi(9)} \equiv 1 \pmod{9}$, burada $\phi(9)=6$. $30 \div 6 = 5$ kalan $0$, yani $30 \equiv 0 \pmod{6}$, dolayısıyla $2^{30} \equiv 1 \pmod{9}$. $4$ ve $9$ da aralarında asaldır; $4$'ün mod $9$'daki periyodunu bulalım: $4^1 \equiv 4 \pmod{9}$, $4^2 \equiv 16 \equiv 7 \pmod{9}$, $4^3 \equiv 28 \equiv 1 \pmod{9}$, periyot $3$. $20 \div 3 = 6$ kalan $2$, yani $20 \equiv 2 \pmod{3}$, dolayısıyla $4^{20} \equiv 4^2 = 16 \equiv 7 \pmod{9}$. Sonuç: $1 < 7$, yani $2^{30} \mod 9 < 4^{20} \mod 9$.