163 ve 185 sayılarını böldüğümüzde sırası ile 3 ve 5 kalanını veren en küçük sayı kaçtır?
Çözüm:
Verilen:
- Bir sayıyı 163 sayısına böldüğünde kalan 3’tür.
- Aynı sayıyı 185 sayısına böldüğünde kalan 5’tir.
Bize bu koşulları sağlayan en küçük pozitif sayı soruluyor.
Adım 1: Denklem Kurmak
Bir sayıyı x olarak alalım.
Buna göre:
Adım 2: İki Denklemden Denklem Sistemi Kurmak
İki eşitlik birbirine eşit olduğundan:
Bunu düzenleyelim:
Yani,
Adım 3: Bu Diophantine denklemini çözmek
Amacımız k ve m tamsayılarını bulmak. Bu tür denklemleri çözmek için genel yöntemi uygulayalım.
Önce,
denklemine bakalım. Burada bilinmeyenler k ve m.
Adım 4: Ortak Bölen Kontrolü
Bu Sağ taraftaki sayı (2), 163 ve 185 sayılarının EBOB (GCD)'si ile bölünebilmelidir.
Önce:
EBOB hesabı:
- 185 - 163 = 22
- 163 mod 22:
- 22 mod 9:
- 9 mod 4:
- 4 mod 1:
Son kalan 1 olduğundan,
EBOB 1 ise denklemin tüm tam sayı çözümleri vardır.
Adım 5: Denklemin çözümünü bulalım
Denklik:
veya
Burada amaç k tamsayısını bulmak için m'yi uyan bir değerde bulmak.
Adım 6: Yöntem: Mod alma
Denklik üzerine mod 185 alalım:
Adım 7: Mod tersini bulma
163k \equiv 2 \pmod{185} olduğundan, önce 163’ün 185 modundaki tersini bulmalıyız.
Yani, 163 \times k \equiv 1 \pmod{185} olan k sayısını bulalım. Bu ters sayı ile 2 çarparak k'yi bulacağız.
Adım 8: 163’ün 185 modundaki tersini bulmak (gelişmiş Öklid algoritması)
Uygulayalım:
Öklid algoritması ile
Şimdi ters bulmak için geriye doğru gidelim (Extended Euclidean Algorithm):
- 1 = 9 - 4 \times 2
- 4 = 22 - 9 \times 2
1 = 9 - (22 - 9 \times 2) \times 2 = 9 \times 5 - 22 \times 2
- 9 = 163 - 22 \times 7
1 = (163 - 22 \times 7) \times 5 - 22 \times 2 = 163 \times 5 - 22 \times 35 - 22 \times 2 = 163 \times 5 - 22 \times 37
- 22 = 185 - 163
1 = 163 \times 5 - (185 - 163) \times 37 = 163 \times (5 + 37) - 185 \times 37 = 163 \times 42 - 185 \times 37
Elde edilen:
Bu durumda,
163’ün 185 modundaki tersi 42’dir.
(Bu, 163 \times 42 \equiv 1 \pmod{185} demektir.)
Adım 9: k'yi hesapla
163k \equiv 2 \pmod{185} olduğundan,
Yani,
Adım 10: x değerini bulalım
Hatırlayın,
İlk k değerini alalım: k = 84
Böylece,
Adım 11: Son kontrol yapalım
- 13695 \mod 163 = ?
13695 \div 163 \approx 84 (asıl k değerimizin doğruluğu)
163 \times 84 = 13692
Kalan:
Doğru.
- 13695 \mod 185 = ?
13695 \div 185 \approx 74
185 \times 74 = 13690
Kalan:
Doğru.
Sonuç:
163 ve 185 sayılarına bölündüğünde sırasıyla 3 ve 5 kalanını veren en küçük sayı 13695'tir.
Özet Tablosu
| Adım | İşlem | Sonuç |
|---|---|---|
| 1. Tanımlama | x = 163k + 3 = 185m + 5 | Denklem kuruldu |
| 2. Denklem kurma | 163k - 185m = 2 | Diophantine den. |
| 3. EBOB kontrolü | \gcd(163,185) = 1 | Çözüm mümkün |
| 4. Mod alma | 163k \equiv 2 \pmod{185} | Kümeye düşürme |
| 5. Ters eleman bulma | 163 \times 42 \equiv 1 \pmod{185} | Ters: 42 |
| 6. k'yi hesaplma | k \equiv 2 \times 42 = 84 \pmod{185} | k=84 |
| 7. Sayı x hesaplama | x = 163 \times 84 + 3 = 13695 | Sonuç |
| 8. Kontrol | Kalanlar doğru | 3 ve 5 |
