Potenze di un intero modulo m (ordine)
Ho provato varie volte a rifare questo esercizio, senza capire dove sbaglio.
Consegna: Trovare l'ordine di 3 modulo 31.
Mi sono messa a calcolare tutte le potenze di 3, sperando di trovare ad un certo punto una ripetizione.
Le potenze di 3 (mod 31) che ho calcolato partendo dall'esponente zero fino al 28 sono le seguenti:
1, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 2, 6, 18, 23, 5, 15, 14, 11, 2, 6.
Mi sono accorta che cominciava una ripetizione di: 2, 6, 18, 23 ....
E quindi mi sono resa conto che c'era qualcosa che non andava, un lemma infatti afferma che poichè 3 e 31 sono relativamente primi allora la sequenza delle potenze di tre è sempre periodica e il periodo comincia dal primo elemento, non dal diciottesimo come nel mio caso.
Ho ricontrollato gli elevamenti a potenza tre volte, ma mi sembrano giusti.
Ho dato un'occhiata alla soluzione che risulta essere 30. E mi sembra sbagliata. L'ordine dovrebbe essere il più piccolo esponente a cui elevo tre ed ottengo un numero congruo ad uno. Ma in questo caso risulterebbe congruo a 23 non ad uno.
Se qualcuno sapesse spiegarmi come fare l'esercizio in maniera corretta, che cosa sbaglio nel mio procedimento gli sarei molto grata, grazie. (spero di essermi spiegata bene)
Consegna: Trovare l'ordine di 3 modulo 31.
Mi sono messa a calcolare tutte le potenze di 3, sperando di trovare ad un certo punto una ripetizione.
Le potenze di 3 (mod 31) che ho calcolato partendo dall'esponente zero fino al 28 sono le seguenti:
1, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 2, 6, 18, 23, 5, 15, 14, 11, 2, 6.
Mi sono accorta che cominciava una ripetizione di: 2, 6, 18, 23 ....
E quindi mi sono resa conto che c'era qualcosa che non andava, un lemma infatti afferma che poichè 3 e 31 sono relativamente primi allora la sequenza delle potenze di tre è sempre periodica e il periodo comincia dal primo elemento, non dal diciottesimo come nel mio caso.
Ho ricontrollato gli elevamenti a potenza tre volte, ma mi sembrano giusti.
Ho dato un'occhiata alla soluzione che risulta essere 30. E mi sembra sbagliata. L'ordine dovrebbe essere il più piccolo esponente a cui elevo tre ed ottengo un numero congruo ad uno. Ma in questo caso risulterebbe congruo a 23 non ad uno.
Se qualcuno sapesse spiegarmi come fare l'esercizio in maniera corretta, che cosa sbaglio nel mio procedimento gli sarei molto grata, grazie. (spero di essermi spiegata bene)
Risposte
Però dopo $23$ non c'è $5$. C'è $7$.
Infatti $23*3= 69 -= 7 (mod 31)$
Io farei così:
l'ordine di $3$ modulo $31$ è un divisore di $30$
(in generale, se $(a,n)=1$, l'ordine di $a$ modulo $n$ è un divisore di $varphi(n)$, dove $varphi$ è la funzione di Eulero).
Dato che i divisori di $30$ sono $1,2,3,5,6,10,15,30$, controlliamo solo questi.
$3^1=3$ , $3^2=9$, $3^3=27-= -4 (mod 31)$,
$3^5=3^3* 3^2 -= -4 * 9 (mod 31)= -36 -= -5 (mod 31)$,
$3^6 -= -5*3 = -15 (mod 31)$
$3^10 = 3^5 * 3^5 -= -5 *(-5) (mod 31)= 25$
$3^15= 3^10 * 3^5 -= 25*(-5) (mod 31)= -125 -= -1 (mod 31)$
Dunque, poichè nessuno di questi è congruo a $1$ modulo $31$, si ha che l'ordine di $3$ modulo $31$ è $30$.
Infatti $23*3= 69 -= 7 (mod 31)$
Io farei così:
l'ordine di $3$ modulo $31$ è un divisore di $30$
(in generale, se $(a,n)=1$, l'ordine di $a$ modulo $n$ è un divisore di $varphi(n)$, dove $varphi$ è la funzione di Eulero).
Dato che i divisori di $30$ sono $1,2,3,5,6,10,15,30$, controlliamo solo questi.
$3^1=3$ , $3^2=9$, $3^3=27-= -4 (mod 31)$,
$3^5=3^3* 3^2 -= -4 * 9 (mod 31)= -36 -= -5 (mod 31)$,
$3^6 -= -5*3 = -15 (mod 31)$
$3^10 = 3^5 * 3^5 -= -5 *(-5) (mod 31)= 25$
$3^15= 3^10 * 3^5 -= 25*(-5) (mod 31)= -125 -= -1 (mod 31)$
Dunque, poichè nessuno di questi è congruo a $1$ modulo $31$, si ha che l'ordine di $3$ modulo $31$ è $30$.
Perfetto, ho capito. Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo