Tallteori-oppgave

[svinepels]

Skal vise at kongruensen

[tex]11^{73^n} \equiv 11 \pmod{111}[/tex]

holder for alle n. Ser først at 111 = 3 * 37, og derfor er phi(111) = 2 * 36 = 72. Dermed gir Eulers teorem at

[tex]11^{72} \equiv 1 \pmod{111}[/tex]

Ganger man med 11, får man

[tex]11^{73} \equiv 11 \pmod{111}[/tex]

Når det gjelder 73^n, er det et problem av en type jeg ikke har støtt borti før. Men fant at

[tex]73^2 = 5329 = 48 \cdot 111+1 \equiv 1 \pmod{111}[/tex]

Så dette gir

[tex]11^{73^{2n}} \equiv 11 \pmod{111}[/tex]

Altså har jeg etablert resultatet for alle partall, men ikke oddetall. Noen hint?

[Vektormannen]

Induktivt så går vel dette nesten helt automatisk. Du har vist at [tex]11^{73} \equiv 11[/tex]. Da følger det jo at:

[tex](11^{73})^{73} = 11^{73^2} \equiv 11^{73} \equiv 11[/tex]

Og dette kan du gjenta n ganger.

Edit: litt rotete skrevet

[svinepels]

Stemmer det. At jeg ikke så det..

takk!

[Vektormannen]

Det er fort gjort å henge seg opp i et annet spor, kjenner meg alt for godt igjen i det