Resto divisione esponente elevato
Ciao Ragazzi
mi trovo in difficoltà con un esercizio, ovvero: calcolare il resto della divisione per 3 di \(\displaystyle 5^{427} \)
il mio ragionamento è stato questo (che poi l'ho preso dal libro):
la divisione di \(\displaystyle 5^{427} \) per 3 è come dire \(\displaystyle 5^{427} mod 7 \)
osservo che \(\displaystyle 5 \equiv 2 mod 3 \)
quindi posso dire che \(\displaystyle 5^{427} \equiv 2^{427} mod 3 \)
a questo punto dato che il MCD(2,3)=1 grazie ad un corollario del piccolo teorema di fermat, posso dire che \(\displaystyle 2^2 \equiv 1 mod 3 \)
e potrei concludere dicendo che
\(\displaystyle 5^{427} \equiv 2^{427} = 2^{123*2+1} = (2^2)^{213} * 2 \equiv 1^{123} * 2 = 2 \equiv ??? \)
per rispettare la congruenza mod 3 non saprei come concludere, perchè se tengo conto che \(\displaystyle a \equiv b (mod n) \) è come dire che a-b deve essere multiplo di n allora non saprei che scrivere
spero di essere stato chiaro nell'esporre il problema... grazie a tutti per l'aiuto
mi trovo in difficoltà con un esercizio, ovvero: calcolare il resto della divisione per 3 di \(\displaystyle 5^{427} \)
il mio ragionamento è stato questo (che poi l'ho preso dal libro):
la divisione di \(\displaystyle 5^{427} \) per 3 è come dire \(\displaystyle 5^{427} mod 7 \)
osservo che \(\displaystyle 5 \equiv 2 mod 3 \)
quindi posso dire che \(\displaystyle 5^{427} \equiv 2^{427} mod 3 \)
a questo punto dato che il MCD(2,3)=1 grazie ad un corollario del piccolo teorema di fermat, posso dire che \(\displaystyle 2^2 \equiv 1 mod 3 \)
e potrei concludere dicendo che
\(\displaystyle 5^{427} \equiv 2^{427} = 2^{123*2+1} = (2^2)^{213} * 2 \equiv 1^{123} * 2 = 2 \equiv ??? \)
per rispettare la congruenza mod 3 non saprei come concludere, perchè se tengo conto che \(\displaystyle a \equiv b (mod n) \) è come dire che a-b deve essere multiplo di n allora non saprei che scrivere
spero di essere stato chiaro nell'esporre il problema... grazie a tutti per l'aiuto
Risposte
Salve!
Immagino che intendevi quello che sto per dirti:
il resto della divisione di $5^(427)$ per $3$ è come dire vedere quanto vale $5^(427) ("mod "3)$.
Bene.
Sì, in teoria va bene, ma in questo caso sai che $2^2=4$ direttamente. Diciamo che al posto tuo avrei scomodato Fermat se avessi avuto numeri mostruosi.
Premetto che non ci ho capito granché in quello che scrivi.
Comunque hai che, modulo 3, $5^(427)\equiv 2^(427)$ e ok.
$2^(427)$, in generale, è $2^(426)\cdot 2= (2^2)^(213)\cdot 2$ e ok.
Dunque, poiché, come hai detto prima per il 5 e il 2 ora hai che $4 \equiv 1 ("mod "3)$ allora
$4^(213)\cdot 2 \equiv 1^(213) \cdot 2 \equiv 2 ("mod "3)$
e a posto... il resto di $5^(427)$ per $3$ è 2 proprio perché $5^(427)\equiv 2 ("mod "3)$ come hai trovato... finish!
"duombo":
la divisione di \(\displaystyle 5^{427} \) per 3 è come dire \(\displaystyle 5^{427} mod 7 \)
Immagino che intendevi quello che sto per dirti:
il resto della divisione di $5^(427)$ per $3$ è come dire vedere quanto vale $5^(427) ("mod "3)$.
quindi posso dire che \(\displaystyle 5^{427} \equiv 2^{427} mod 3 \)
Bene.
a questo punto dato che il MCD(2,3)=1 grazie ad un corollario del piccolo teorema di fermat, posso dire che \(\displaystyle 2^2 \equiv 1 mod 3 \)
Sì, in teoria va bene, ma in questo caso sai che $2^2=4$ direttamente. Diciamo che al posto tuo avrei scomodato Fermat se avessi avuto numeri mostruosi.
e potrei concludere dicendo che
\(\displaystyle 5^{427} \equiv 2^{427} = 2^{123*2+1} = (2^2)^{213} * 2 \equiv 1^{123} * 2 = 2 \equiv ??? \)
per rispettare la congruenza mod 3 non saprei come concludere, perchè se tengo conto che \(\displaystyle a \equiv b (mod n) \) è come dire che a-b deve essere multiplo di n allora non saprei che scrivere
spero di essere stato chiaro nell'esporre il problema... grazie a tutti per l'aiuto
Premetto che non ci ho capito granché in quello che scrivi.
Comunque hai che, modulo 3, $5^(427)\equiv 2^(427)$ e ok.
$2^(427)$, in generale, è $2^(426)\cdot 2= (2^2)^(213)\cdot 2$ e ok.
Dunque, poiché, come hai detto prima per il 5 e il 2 ora hai che $4 \equiv 1 ("mod "3)$ allora
$4^(213)\cdot 2 \equiv 1^(213) \cdot 2 \equiv 2 ("mod "3)$
e a posto... il resto di $5^(427)$ per $3$ è 2 proprio perché $5^(427)\equiv 2 ("mod "3)$ come hai trovato... finish!
Prima di tutto grazie mille perchè mi hai fatto capire che cosa non andava nel mio ragionamento. La parte che non hai capito è occhio e croce la traduzione (a mio modo) di quello che hai scritto tu sotto, il mio problema è che non avevo capito che alla fine andava benissimo concludere che 2 è proprio il resto della divisione perchè \(\displaystyle 5^{427}\equiv2(mod 3) \) mi ero proprio perso su questo passaggio.
Cmq Fermat l'ho citato solo perchè ho cercato di seguire gli argomenti di teoria che riporta il libro, putroppo sta materia la trovo un po ostica. Ora devo capire come comportarmi quando mi si chiede di dividere per un numero non primo!!
Grazie veramente tanto
Cmq Fermat l'ho citato solo perchè ho cercato di seguire gli argomenti di teoria che riporta il libro, putroppo sta materia la trovo un po ostica. Ora devo capire come comportarmi quando mi si chiede di dividere per un numero non primo!!
Grazie veramente tanto
"duombo":
Prima di tutto grazie mille perchè mi hai fatto capire che cosa non andava nel mio ragionamento.
Prego, ma comunque controlla se qualcuno viene a smentirmi che non si sa mai.
Cmq Fermat l'ho citato solo perchè ho cercato di seguire gli argomenti di teoria che riporta il libro
Sì, infatti è giusto.
Ora devo capire come comportarmi quando mi si chiede di dividere per un numero non primo!!
E' passato un anno dalla tesi e da quando lavoro di matematica non ricordo più granché... però ricordo un algoritmo di Lagrange (se non erro) per facilitare le potenze dei numeri con le congruenze. L'avevo scritto anche sulla tesi (che sta su matematicamente.it da qualche parte) ma un utente m'ha fatto notare che c'è un errore di battitura (e non solo uno, ma questa è un'altra storia).
***
In pratica, vedi come scrivere l'esponente dividendolo sempre per 2. Per es.
$427=426+1=213\cdot 2 +1= (212+1)\cdot 2 +1= ((106 \cdot 2 +1)+1) \cdot 2 +1$ e così via.
Se, poi, ad es., hai quanto vale $2^(106)$ modulo quello che ti pare[nota]Mi sono fermato a $106$, ma ovviamente si poteva andare oltre $106=53 \cdot 2= ((26\cdot 2)+1)\cdot 2$... fino ad arrivare a $1$. E' molto simile a quello che si fa quando si trasforma un numero dalla base 10 alla base 2.[/nota], lo elevi (elevi il resto!
) al quadrato e ottieni $2^(212)$. Moltiplichi per 2 e ottieni $2^(213)$ (sempre modulo quello che vuoi). Poi rielevi il tutto al quadrato e infine rimoltiplichi per due.Serve apposta per accorciare il calcolo delle potenze in modulo.
Non ricordo come si chiama questo metoduccio (mi sembra dovuto a Lagrange), ma il punto è che l'ho trovato in un solo libro e su google non si trova niente (ma forse perché non ricordo il nome).
Ciao.
Non sono in grado di seguire i vostri ragionamenti.
Io ho solo notato che se l'esponete è dispari avanza $2$, se l'esponente è pari avanza $1$.
Non sono in grado di seguire i vostri ragionamenti.
Io ho solo notato che se l'esponete è dispari avanza $2$, se l'esponente è pari avanza $1$.
"Zero87":
Non ricordo come si chiama questo metoduccio (mi sembra dovuto a Lagrange), ma il punto è che l'ho trovato in un solo libro e su google non si trova niente (ma forse perché non ricordo il nome).
L'algoritmo in questione potrebbe essere questo ?
1) scrivo in base $2$ la potenza $427$.
$427=2 \cdot 213 + 1$
$213=2 \cdot 106 + 1$
$106=2 \cdot 53 + 0$
$53=2 \cdot 26 + 1$
$26=2 \cdot 13 + 0$
$13=2 \cdot 6 + 1$
$6=2 \cdot 3 + 0$
$3=2 \cdot 1 + 1$
$1=2 \cdot 0 + 1$
Dunque $427$ in base $2$ è $110101011$
2) faccio corrispondere $1$ a quadrare $(Q)$ e moltiplicare $(X)$ per $5$ e faccio corrispondere $0$ solo a quadrare $(Q)$.
Dunque $110101011$ mi diventa $QX QX Q QX Q QX Q QX QX$. A questo punto procedo con le operazioni:
$1 \rightarrow_Q 1 \rightarrow_X 5 \rightarrow_Q 25 \equiv 1 (mod 3) \rightarrow_X 5 \rightarrow_Q 25 \equiv 1 (mod 3) \rightarrow_Q 25 \equiv 1 (mod 3) \rightarrow_Q 1 \rightarrow_X 5 \rightarrow_{Q Q X Q Q X} 5 \rightarrowQ 25 \equiv 1 (mod 3) \rightarrow_X 5 \equiv 2 (mod 3)$
Un altro esercizio mi chiede invece di "determinare $15^15 (mod 15)$ (attenzione).".
Attenzione perche ? Perche dovrei osservare che se $a \equiv b (mod m) \Rightarrow a^k \equiv b^k (mod m)$ e quindi evitare di utilizzare l'algoritmo e concludere immediatamente che se $15 \equiv 0 (mod m) \Rightarrow 15^15 \equiv 0 (mod m)$ ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo