a) Jakojäännös, kun $37^{85}$ jaetaan luvulla 147

Tarkastellaan jakojäännöstä $37^{85} \mod 147$. Hajotetaan $147 = 3 \times 7^2$ ja lasketaan erikseen modulo $3$ ja modulo $49$, minkä jälkeen käytämme kiinalaista jäännöslausetta.

1. Modulo 3
   $37 \equiv 1 \pmod{3}$ $37^{85} \equiv 1^{85} \equiv 1 \pmod{3}$

2. Modulo 49
   Käytetään Eulerin lausetta. Koska $\varphi(49) = 49 \cdot (1 - \frac{1}{7}) = 42$, saamme: $37^{42} \equiv 1 \pmod{49}$ Koska $85 \equiv 1 \pmod{42}$, niin: $37^{85} \equiv 37^1 \equiv 37 \pmod{49}$

3. Ratkaisu kiinalaisella jäännöslauseella
   Etsimme $x$, joka toteuttaa: $x \equiv 1 \pmod{3}$ $x \equiv 37 \pmod{49}$ Ratkaistaan yhtälö $x = 49k + 37$ ja sijoitetaan ehto $x \equiv 1 \pmod{3}$: $49k + 37 \equiv 1 \pmod{3}$ Koska $49 \equiv 1 \pmod{3}$, niin yhtälö sievenee: $k + 37 \equiv 1 \pmod{3}$ $k \equiv -36 \equiv 0 \pmod{3}$ Valitaan $k = 3m$, jolloin: $x = 49(3m) + 37 = 147m + 37$ Siis jakojäännös on 37.

---

b) Luvun $51^{82}$ kaksi viimeistä numeroa

Etsimme $51^{82} \mod 100$.

1. Eulerin lause
   $\varphi(100) = 100(1 - \frac{1}{2})(1 - \frac{1}{5}) = 40$ $51^{40} \equiv 1 \pmod{100}$ Koska $82 \equiv 2 \pmod{40}$, saamme: $51^{82} \equiv 51^2 \pmod{100}$

2. Lasketaan $51^2 \mod 100$
   $51^2 = 2601$ $2601 \mod 100 = 01$ Siis kaksi viimeistä numeroa ovat 01.

---

c) Jakojäännös, kun $3^{64} \cdot 49^{73}$ jaetaan luvulla 50

Etsitään $(3^{64} \cdot 49^{73}) \mod 50$.

1. Modulo 50
   Eulerin lauseella $\varphi(50) = 20$, joten: $3^{20} \equiv 1 \pmod{50}$ Koska $64 \equiv 4 \pmod{20}$, saadaan: $3^{64} \equiv 3^4 \equiv 81 \equiv 31 \pmod{50}$

   Toisaalta $49 \equiv -1 \pmod{50}$, joten: $49^{73} \equiv (-1)^{73} \equiv -1 \pmod{50}$

2. Lasketaan tulos
   $3^{64} \cdot 49^{73} \equiv 31 \cdot (-1) \equiv -31 \equiv 19 \pmod{50}$ Siis jakojäännös on 19.

---

Haluatko lisätietoja tai tarkempia selityksiä?

5 lisätehtävää harjoitteluun:

1. Mikä on jakojäännös, kun $2^{100}$ jaetaan luvulla 25?
2. Määrää luvun $47^{53}$ kaksi viimeistä numeroa.
3. Laske $5^{100} \mod 101$ käyttämällä Fermat'n lausetta.
4. Mikä on $123^{456} \mod 7$?
5. Etsi $7^{200} \mod 100$.

Vinkki:

Eulerin lause toimii tehokkaasti, kun moduuli sisältää useita alkutekijöitä. Kiinalainen jäännöslause auttaa yhdistämään tuloksia eri moduloille. 🚀