problema congruenza

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
matteo16
Messaggi: 303
Iscritto il: 10 dic 2007, 21:16

problema congruenza

Messaggio da matteo16 » 06 lug 2008, 17:24

Determinare il pi`u piccolo intero positivo $ n $ tale che
$ 5^n\equiv1 (mod 11) $

la risposta è $ 5 $ ma io credevo $ 10 $


ho applicato il piccolo teorema di Fermat dicendo che, poichè $ 11 $ è primo

allora in generale se 0<=a<p si ha che $ a^p-1\equv1 (mod p) $

quindi, tornando a sopra, ho pensato

$ n=11-1=10 $

come mai non è così?

tra l'altro gli unici numeri per cui n potesse essere $ 2 $ (per esempio) modp
sono quelli della forma $ p-1 $

quindi in questo caso al massimo sarebbe $ 10^2\equiv1 (mod 11) $ ma questo è un altro caso

non riesco a capire come mai il mio ragionamento è sbagliato :?

¬[ƒ(Gabriel)³²¹º]¼+½=¾
Messaggi: 849
Iscritto il: 22 ott 2006, 14:36
Località: Carrara/Pisa

Messaggio da ¬[ƒ(Gabriel)³²¹º]¼+½=¾ » 06 lug 2008, 17:43

il problema chiede di trovare l'ordine moltiplicativo di 5 modulo 11, l'unica cosa che puoi dire usando fermat è che l'ordine moltiplicativo divide 10.

matteo16
Messaggi: 303
Iscritto il: 10 dic 2007, 21:16

Messaggio da matteo16 » 06 lug 2008, 19:29

¬[ƒ(Gabriel)³²¹º]¼+½=¾ ha scritto:il problema chiede di trovare l'ordine moltiplicativo di 5 modulo 11, l'unica cosa che puoi dire usando fermat è che l'ordine moltiplicativo divide 10.
ah ho capito


forse io ho scambiato il 5 mod 11 come un generatore e allora lì sarebbe 10
invece 5 non è un generatore mod 11

ma quindi Fermat? come lo uso? quando lo posso usare?

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 06 lug 2008, 22:41

Per questo problema, lasci stare fermat e fai quattro conti, (tanto, proprio per fermat, sei sicuro di non dover fare più di 10 moltiplicazioni banali), se invece vuoi vedere come applicarlo in un altro esercizio, la ricerca di "fermat" in TdN dà 82 risultati

nicelbole
Messaggi: 14
Iscritto il: 16 mag 2007, 16:47

Messaggio da nicelbole » 06 lug 2008, 22:46

Fermat ti serve per quello che ti ha detto Gabriel: gli unici valori possibili per n sono tra i divisori di 10. Dunque n può essere 1, 2, 5 o 10, e il "controllo" a mano si riduce a quattro casi.

matteo16
Messaggi: 303
Iscritto il: 10 dic 2007, 21:16

Messaggio da matteo16 » 07 lug 2008, 09:27

ok ho capito grazie a tutti per le spiegazioni
effettivamente potevo farlo anche a mano ma avrei impiegato più tempo

Rispondi