Modüler aritmetik

1) 12²⁰⁰² sayısının son iki basamağı nedir?

2) 2³⁴⁵ sayısının son iki basamağı nedir?

3) 173³³²¹sayısının son iki basamağı nedir?

4) 98! sayısının 103 ile bölümünden kalan nedir?

5) 3x≡5(mod10) 6x≡9(mod21) denkliklerini sağlayan tüm x'leri bulunuz.

gereksiyorumcu'nun çözümleri

5.
3x=5 (mod10) da x=5+10t
6x=9 (mod21) <=> 2x=3 (mod7) → x=5+7k ifadeleri bulunmuş , buradan x=5+70m olduğu görülebilir

1.
son iki basamak için 25 modunda inceleyelim sonra 100 moduna atlarız (12 de 4 e bölünüyor o bakımdan)
phi(25)=5.4=20 olduğundan 12²⁰=1 (mod25) olacaktır
yani 12²⁰⁰²=1.12²=144=19 (mod25)
25 modunda 19 a denk olan ve 4 e bölünen 100 den küçük sayı arıyoruz cevap 44 olurdu. (istenilen elde edilene kadar sırayla 25 ler eklenebilir)

2.
bir önceki soru gibi 25 modunda bakarsak 2²⁰=1 (mod25)
3 ün kuvvetleri de 20 modunda incelenirse 3⁴=81=1 (mod20)
yani bu sayı 2^20k+1 şekilli bu da 25 modunda 2¹=2 ye denk
sırayla 25 ler ekleyip 4 e bölünen sayı bulmaya çalışırsak 52 sonucuna ulaşılır

3.
phi(100)=phi(4).phi(25)=2.1.5.4=40 olduğundan
73⁴⁰=1 (mod100)
3³²¹ 40 modunda incelenirse 3 e denk olduğu görülür (3⁴=1 mod40)
73³ ün son 2 basamağını arıyoruz
27.27.73=729.73=29.73=2190-73=17 mod100

4.
103 asal wilsondan 101!=1 (mod103)
98!.99.100.101=1 (mod103)
98!.79=1 (mod103)
98!=x dersek
79x-103k=1 denklemini çözeceğiz
buna benzer sorular çözülmüştü
103-79=24 , 79-3.24=7 , 24-3.7=3 , 7-2.3=1
7-2.3=1 ,
7-2.(24-3.7)=1 → 7-2.24+6.7=1 → 7.7-2.24=1 ,
7.(79-3.24)-2.24=1 → 7.79-21.24-2.24=1 → 7.79-23.24=1 ,
7.79-23.(103-79)=1 → 7.79-23.103+23.79=1 → 30.79-23.103=1
buradan x=30 bulunur

4. soruya aerturk39 hocamın çözümü

kısa bir çözüm şöyle olabilirdi
102!=-1(mod103) olacak buradan
98!.99.100.101.102=-1(mod103)
98!.-4.-3.-2.-1=102(mod103)
98!.24=102(mod103)
98!.12=51(mod103)
98!.12=154(mod103)
98!.6=77(mod103)
98!.6=180(mod103)
98!=30(mod103)

Hatta daha da kısaltmak mümkün gibi...

98!.99.100.101.102≡-1≡102 (103)
98!.99.100.101≡1 (103)
98!.-4.-3.-2≡1 (103)
98!.6.-4.-26≡-26 (103)
98!.6.-17≡-26.-17 (103)
98!≡30 (103) gibi...

Çözümlü Modüler Aritmetik Soruları Modüler Aritmetik Sorular ve Çözümleri
Tüm Etiketler