Ratkaistaan molemmat kongruenssiyhtälöt ilman Eukleideen algoritmia.

a) Kongruenssi: $3x - 6 \equiv 6x - 5 \pmod{8}$

1. Vähennetään molemmilta puolilta $3x$ ja $6x$: $3x - 6 - 3x \equiv 6x - 5 - 3x \pmod{8}$ Tämä yksinkertaistuu muotoon: $-6 \equiv 3x - 5 \pmod{8}$

2. Lisätään molemmilta puolilta $5$: $-6 + 5 \equiv 3x - 5 + 5 \pmod{8}$ Jolloin saamme: $-1 \equiv 3x \pmod{8}$

3. Koska $-1 \equiv 7 \pmod{8}$, voimme kirjoittaa: $7 \equiv 3x \pmod{8}$

4. Nyt haluamme löytää $x$, joten meidän täytyy ratkaista $3x \equiv 7 \pmod{8}$.

5. Testataan eri $x$-arvoja modulo 8: $3 \times 1 = 3 \quad (\text{ei ole sama kuin } 7)$ $3 \times 2 = 6 \quad (\text{ei ole sama kuin } 7)$ $3 \times 3 = 9 \equiv 1 \pmod{8} \quad (\text{ei ole sama kuin } 7)$ $3 \times 4 = 12 \equiv 4 \pmod{8} \quad (\text{ei ole sama kuin } 7)$ $3 \times 5 = 15 \equiv 7 \pmod{8} \quad (\text{on sama kuin } 7)$

   Näin ollen $x \equiv 5 \pmod{8}$ on ratkaisu.

Vastaus: $x \equiv 5 \pmod{8}$

---

b) Kongruenssi: $746x \equiv 63 \pmod{31}$

1. Lasketaan $746 \mod 31$ ja $63 \mod 31$:

   • $746 \div 31 = 24$ ja $746 - 31 \times 24 = 746 - 744 = 2$, joten $746 \equiv 2 \pmod{31}$.
   • $63 \div 31 = 2$ ja $63 - 31 \times 2 = 63 - 62 = 1$, joten $63 \equiv 1 \pmod{31}$.

   Tällöin alkuperäinen kongruenssi voidaan kirjoittaa muotoon: $2x \equiv 1 \pmod{31}$

2. Nyt haluamme ratkaista kongruenssin $2x \equiv 1 \pmod{31}$. Tässä etsitään $2$-käänteisluku modulo 31. Tämä tarkoittaa, että meidän täytyy löytää $y$, jolle $2y \equiv 1 \pmod{31}$.

3. Testataan $y$-arvoja modulo 31: $2 \times 1 = 2 \quad (\text{ei ole } 1)$ $2 \times 2 = 4 \quad (\text{ei ole } 1)$ $2 \times 3 = 6 \quad (\text{ei ole } 1)$ $2 \times 15 = 30 \equiv -1 \pmod{31} \quad (\text{ei ole } 1)$ $2 \times 16 = 32 \equiv 1 \pmod{31}$ Näin ollen $16$ on käänteisluku $2$:lle modulo 31.

4. Kerrotaan alkuperäinen kongruenssi $2x \equiv 1 \pmod{31}$ luvulla 16: $16 \times 2x \equiv 16 \times 1 \pmod{31}$ Tämä yksinkertaistuu muotoon: $x \equiv 16 \pmod{31}$

Vastaus: $x \equiv 16 \pmod{31}$

---

Yhteenveto:

• a) $x \equiv 5 \pmod{8}$
• b) $x \equiv 16 \pmod{31}$

Jos tarvitset lisäselvitystä tai tarkempia vaiheita, kysy rohkeasti!

Tässä muutama lisäkysymys, joka voisi kiinnostaa:

1. Miten löytää käänteisluku modulaariyhtälöissä?
2. Voiko kongruenssia ratkaista käyttäen yksinkertaisia lineaarisia yhtälöitä?
3. Mikä on Eukleideen algoritmin rooli kongruenssiyhtälöiden ratkaisemisessa?
4. Miten testata, onko tietty luku käänteisluku modulo n?
5. Millaisia muitakin menetelmiä on käyttää kongruenssiyhtälöiden ratkaisussa?

Vinkki: Muista tarkistaa aina, että mahdolliset ratkaisut todella täyttävät alkuperäisen kongruenssin ja että laskut modulo $n$ ovat oikein suoritettu.