Matematicamente.it

Salve a tutti, come posso ridurre le seguente espressioni?
$ 174^55 mod 221 $
$ 137^110 mod 221 $
Grazie mille!!

Hai provato con il teorema di Eulero?

Il teorema di Eulero è quello che dice:

$a^p \equiv a mod p$

quale che sia $a$ ma con $p$ primo!

Quello è un caso particolare (piccolo teorema di Fermat), il teorema ti dice che $a^(\varphi(n))=1 (mod n)$, per a e n coprimi

armi96 ha scritto:Salve a tutti, come posso ridurre le seguente espressioni?
$ 174^55 mod 221 $
$ 137^110 mod 221 $
Grazie mille!!

ciao !
allora, 174 diviso per 221 ha resti per cicli di 4:

$
174^1 mod 221 = 174
$
$
174^2 mod 221 = 220
$
$
174^3 mod 221 = 47
$
$
174^4 mod 221 = 1
$
$
174^5 mod 221 = 174
$
$
174^6 mod 221 = 220
$
$
174^7 mod 221 = 47

...
$

quindi e' facile capire che, essendo

$
55 mod 4 = 3
$

allora $174^55 mod 221 $ avra' come risposta il terzo elemento del ciclo dei 4 resti possibili, quindi

$
174^55 mod 221 = 47
$

invece, $ 137^110 mod 221 $ e' piu' faticoso, il ciclo dei resti e' piu' ampio, dovresti metterti a calcolare i resti al crescere della potenza di 137 fino a che non ritrovi uno dei resti gia' visti, e quindi con lo stesso procedimento troverai la risposta. Non ho in mente scorciatoie purtroppo