Classi di congruenza...oltre ai trucchetti :S

[Manara1]

Salve a tutti
per risolvere un esercizio simile:

"Si determini la classe di congruenza modulo 100 del numero

$ 987655678925^72549343 $ "

che passaggi devo percorrere? e quali potrebbero essere i trucchetti da tenere a mente (per esempio che in questo caso 25^x finisce sempre per 25)??

Grazie a tutti per la disponibililtà.

[_luca.barletta]

Benvenuto/a nel forum.

Credo ti possa essere d'aiuto questo topic

[Manara1]

Grazie per il benvenuto e per la pronta risposta.

[Manara1]

mmm...mi sfugge ancora qualcosa

come si può risolvere un esercizio del genere:

"Si usi il piccolo teorema di Fermat per determinare la classe di congruenza modulo 7 del numero
$ 756423813^6666666666666666666661 $ "

quando l'esponente è primo e non ha nulla a che fare con il valore del modulo??

Grazie

[Lord K]

Il piccolo teorema di Fermat cita:

[tex]a^p \equiv a (mod p)[/tex] dove [tex]p[/tex] è primo ed [tex]a[/tex] qualsiasi.

Qui ha dunque senso chiedersi quanto vale:

[tex]6666666666666666666661:7=[\text{numero fastidiosamente lungo}]r4[/tex]

ed anche quanto vale:

[tex]756423813:7=108060544r5[/tex]

Ora sapendo questo si tratta di valutare:

[tex]5^{[\text{numero fastidiosamente lungo}]\cdot 7 +4} \equiv (5^{7})^{[\text{numero fastidiosamente lungo}]} \cdot 5^4 \equiv 5^{[\text{numero fastidiosamente lungo}]}\cdot 2 (mod 7)[/tex]

Da qui si tratta di ripetere il ragionamento per il numero fastidiosamente lungo, visto che:

[tex]5^7 \equiv 5 (mod 7)[/tex]

E con un poca di fatica e due conti arrivi al risultato. Occhio ai conti che c'è da perdersi!