Algebra Modulare

Messaggioda armi96 » 21/03/2019, 18:07

Salve a tutti, come posso ridurre le seguente espressioni?
$ 174^55 mod 221 $
$ 137^110 mod 221 $
Grazie mille!!
armi96
Starting Member
Starting Member
 
Messaggio: 15 di 15
Iscritto il: 14/07/2017, 09:37

Re: Algebra Modulare

Messaggioda Reyzet » 23/03/2019, 18:24

Hai provato con il teorema di Eulero?
Reyzet
Junior Member
Junior Member
 
Messaggio: 81 di 156
Iscritto il: 20/01/2018, 15:24

Re: Algebra Modulare

Messaggioda Lord K » 25/03/2019, 13:39

Il teorema di Eulero è quello che dice:

$a^p \equiv a mod p$

quale che sia $a$ ma con $p$ primo!
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Le domande non sono mai stupide, esprimono dei nostri dubbi, solo le risposte possono esserlo!" Un saggio.
Lord K
Senior Member
Senior Member
 
Messaggio: 1644 di 1644
Iscritto il: 10/04/2008, 14:50
Località: Trieste ed alle volte Udine & Ferrara.

Re: Algebra Modulare

Messaggioda Reyzet » 27/03/2019, 18:13

Quello è un caso particolare (piccolo teorema di Fermat), il teorema ti dice che $a^(\varphi(n))=1 (mod n)$, per a e n coprimi
Reyzet
Junior Member
Junior Member
 
Messaggio: 82 di 156
Iscritto il: 20/01/2018, 15:24

Re: Algebra Modulare

Messaggioda Eryka » 10/04/2019, 02:30

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 :D
Eryka
Starting Member
Starting Member
 
Messaggio: 25 di 31
Iscritto il: 26/04/2017, 20:49


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 17 ospiti