Resto divisione intera ( Piccolo Teorema di Fermat/ Eulero )
Ragazzi, avrei bisogno di una mano: determinare il resto della seguente divisione intera:
$ 29354^362971 // 6 $
Chiaramente da risolvere utilizzando il piccolo teorema di Fermat e il teorema di Eulero: stando ai miei calcoli il resto dovrebbe essere 5 .
Tuttavia è evidente che non è possibile utilizzare la calcolatrice del computer per numeri così grandi al fine di verificare l'esattezza del mio calcolo: esiste un modo alternativo per verificare la bontà del mio svolgimento?
Grazie come al solito.
Se necessario, posso postare la mia risoluzione.
$ 29354^362971 // 6 $
Chiaramente da risolvere utilizzando il piccolo teorema di Fermat e il teorema di Eulero: stando ai miei calcoli il resto dovrebbe essere 5 .
Tuttavia è evidente che non è possibile utilizzare la calcolatrice del computer per numeri così grandi al fine di verificare l'esattezza del mio calcolo: esiste un modo alternativo per verificare la bontà del mio svolgimento?
Grazie come al solito.
Se necessario, posso postare la mia risoluzione.
Risposte
Temo che il resto sia sbagliato.
Infatti, $29354$ è un numero pari, ed elevato per $362971$ rimane un numero pari.
Diviso per $6$, dovrà necessariamente dare resto pari.
Posta la tua soluzione, magari l'errore che hai commesso è minimo
Infatti, $29354$ è un numero pari, ed elevato per $362971$ rimane un numero pari.
Diviso per $6$, dovrà necessariamente dare resto pari.
Posta la tua soluzione, magari l'errore che hai commesso è minimo
[cancellato]
Mod: ho scritto alcuni calcoli errati.
Mod: ho scritto alcuni calcoli errati.
Grazie per l'aiuto ragazzi,
Ecco lo svolgimento:
$ 29354^{362971} \equiv \5^{362971} \mod 6 $
Poichè MCD ( 5,6 ) = 1
Allora $ 5^5 = 1 (mod 6) $
Quindi : $ 5^362971 = 5^{( 5 * 72594 ) + 1} = (5^5)^72594 * 5 = 1 * 5 = 5 mod 6 $
Per cui il resto dovrebbe essere 5 ( stamattina ho rivisto l'esercizio )
Se non è corretto, gentilmente ditemi dove sbaglio , grazie.
Ecco lo svolgimento:
$ 29354^{362971} \equiv \5^{362971} \mod 6 $
Poichè MCD ( 5,6 ) = 1
Allora $ 5^5 = 1 (mod 6) $
Quindi : $ 5^362971 = 5^{( 5 * 72594 ) + 1} = (5^5)^72594 * 5 = 1 * 5 = 5 mod 6 $
Per cui il resto dovrebbe essere 5 ( stamattina ho rivisto l'esercizio )
Se non è corretto, gentilmente ditemi dove sbaglio , grazie.
Il passaggio errato è questo:
Non è vero che $29354-=5_(mod6)$. Piuttosto $29354-=2_(mod6)$
"claw91":
$ 29354^{362971} \equiv \5^{362971} \mod 6 $
Non è vero che $29354-=5_(mod6)$. Piuttosto $29354-=2_(mod6)$
Gi8:
Il passaggio errato è questo:[quote=claw91]$ 29354^{362971} \equiv \5^{362971} \mod 6 $
Non è vero che $29354-=5_(mod6)$. Piuttosto $29354-=2_(mod6)$[/quote]
Allora, sono un pirla senza confini:
Ieri, quando ho scritto la traccia, provenivo da 4 ore di matematica intensiva e mi è sfuggito un piccolissimo, ma rilevante e fondamentale particolare:
Il Dividendo non è $ 29354 $ ma $ 29345 $ .
Per cui, a questo punto, la risoluzione che ho proposto, dovrebbe essere corretta : resto 5 .
Chiedo scusa per questa svista, perdonatemi!
Mi pare di aver capito una cosa facendo gli esercizi vari: è chiaro che quando l'esponente è un numero dispari , si potrà sempre applicare il "trucco" di scrivere l'esponente in modo da farlo risultare una potenza di 1.
Ma non è possibile applicare la stessa strategia quando l'esponente è un numero pari.
Ad esempio:
$ 725843^594 $ diviso 9
$ 725843 = 2 ( mod 9 ) $
$ mcd ( 2,9 ) = 1 $
Allora:
$ 2^8 = 1 (mod 9) $
Quindi: $ 2^594 = 2^{ ( 8 * 74 ) + 2 } = (2^8)^74 * 2^2 = 1 * 4 = 4 (mod 9) $
Resto = 4
E' corretto lo svolgimento? Non sono sicuro che l'operazione di suddivisione del 594 sia lecita ( e la parte finale: $ 2^2 = 4 mod 9 )
Inoltre, un altro dubbio riguardo al seguente esercizio:
Dovendo ricavare il resto della seguente divisione:
$ 57432^1142 $ per $ 9 $
$ 57432 = 3 (mod 9) $
Ma $ mcd ( 3, 9 ) = 3 != 1 $
In questo caso per esempio come si procede?
Vi ho messo in neretto le domande importanti.
Scusatemi ancora per l'errore di battitura.
Allora, sono un pirla senza confini:
Ieri, quando ho scritto la traccia, provenivo da 4 ore di matematica intensiva e mi è sfuggito un piccolissimo, ma rilevante e fondamentale particolare:
Il Dividendo non è $ 29354 $ ma $ 29345 $ .
Per cui, a questo punto, la risoluzione che ho proposto, dovrebbe essere corretta : resto 5 .
Chiedo scusa per questa svista, perdonatemi!
- Vi posto lo svolgimento di un altro esercizio, per verificarne lo svolgimento:
$ 725843^594 $ diviso 9
$ 725843 = 2 ( mod 9 ) $
$ mcd ( 2,9 ) = 1 $
Allora:
$ 2^8 = 1 (mod 9) $
Quindi: $ 2^594 = 2^{ ( 8 * 74 ) + 2 } = (2^8)^74 * 2^2 = 1 * 4 = 4 (mod 9) $
Resto = 4
Giusto?
- Inoltre, un altro dubbio riguardo al seguente esercizio:
Qui il massimo comune divisore non è 1: come si procede in questo caso per portare a termine l'esercizio?
Dovendo ricavare il resto della seguente divisione:
$ 57432^1142 $ per $ 9 $
$ 57432 = 3 (mod 9) $
Ma $ mcd ( 3, 9 ) = 3 != 1 $
Come si procede?
Ieri, quando ho scritto la traccia, provenivo da 4 ore di matematica intensiva e mi è sfuggito un piccolissimo, ma rilevante e fondamentale particolare:
Il Dividendo non è $ 29354 $ ma $ 29345 $ .
Per cui, a questo punto, la risoluzione che ho proposto, dovrebbe essere corretta : resto 5 .
Chiedo scusa per questa svista, perdonatemi!
- Vi posto lo svolgimento di un altro esercizio, per verificarne lo svolgimento:
$ 725843^594 $ diviso 9
$ 725843 = 2 ( mod 9 ) $
$ mcd ( 2,9 ) = 1 $
Allora:
$ 2^8 = 1 (mod 9) $
Quindi: $ 2^594 = 2^{ ( 8 * 74 ) + 2 } = (2^8)^74 * 2^2 = 1 * 4 = 4 (mod 9) $
Resto = 4
Giusto?
- Inoltre, un altro dubbio riguardo al seguente esercizio:
Qui il massimo comune divisore non è 1: come si procede in questo caso per portare a termine l'esercizio?
Dovendo ricavare il resto della seguente divisione:
$ 57432^1142 $ per $ 9 $
$ 57432 = 3 (mod 9) $
Ma $ mcd ( 3, 9 ) = 3 != 1 $
Come si procede?
Per quanto riguarda il primo esercizio,
Passando al secondo esercizio, qua è ancora più semplice:
Devi trovare $3^1142 mod 9$. Tieni presente che $3^2=9-=0_(mod 9)$
PS: Hai postato due volte lo stesso messaggio, perchè?
Tra l'altro hai mandato due messaggi consecutivi in meno di 24 ore (è vietato fare UP prima di 24 ore).
Stai più attento e attieniti al regolamento la prossima volta. Ciao
"claw91":Fin qui tutto ok
$ 725843^594 $ diviso 9
$ 725843 = 2 ( mod 9 ) $
$ mcd ( 2,9 ) = 1 $
"claw91":Questo non è vero. Io direi piuttosto$2^6-=1_(mod9)$
$ 2^8 = 1 (mod 9) $
Passando al secondo esercizio, qua è ancora più semplice:
"claw91":
Dovendo ricavare il resto della seguente divisione:
$ 57432^1142 $ per $ 9 $
$ 57432 = 3 (mod 9) $
Devi trovare $3^1142 mod 9$. Tieni presente che $3^2=9-=0_(mod 9)$
PS: Hai postato due volte lo stesso messaggio, perchè?
Tra l'altro hai mandato due messaggi consecutivi in meno di 24 ore (è vietato fare UP prima di 24 ore).
Stai più attento e attieniti al regolamento la prossima volta. Ciao
Strano! Ero convinto di aver editato il mio messaggio, non di averlo ripostato...
Chiaramente è vero che $ 2^6 = 1 ( mod 9 ) $
Tuttavia, sappiamo che se $ a^(p-1) = 1 ( mod p ) $ se e solo se $ mcd ( a,p ) = 1 $
Nel mio caso risulta $ 725843 = 2 ( mod 9 ) $
$ Mcd ( 2, 9 ) = 1 $ per cui $ 2^(9-1) = 1 ( mod 9 ) = 2^8 = 1 ( mod 9 ) $
Che abbiamo visto essere falso.... come mai in questo caso la formula fallisce allora?
- Per quanto riguarda quindi i casi in cui il Massimo comun divisore è divero da 1, come nel caso del secondo esercizio, esiste una procedura "standard" ?
Il secondo esercizio è un caso "fortunato" in quanto il resto della divisione è $ 3 $ che, guarda caso, è esprimibile , elevandolo al quadrato, come potenza di $ 9 $ , il nostro divisore. ( consentendo quindi di affermare che $ 3^2 = 9 = 0 ( mod 9 ) $ esattamente come hai detto tu. )
Ma se il divisore non fosse $ 9 $ , ma comunque un numero non primo con il resto $ 3 $ come si dovrebbe operare?
P.s: Ma come mai i tag non mi funzionano? Anche se metto il quote, rimane il tag....
Chiaramente è vero che $ 2^6 = 1 ( mod 9 ) $
Tuttavia, sappiamo che se $ a^(p-1) = 1 ( mod p ) $ se e solo se $ mcd ( a,p ) = 1 $
Nel mio caso risulta $ 725843 = 2 ( mod 9 ) $
$ Mcd ( 2, 9 ) = 1 $ per cui $ 2^(9-1) = 1 ( mod 9 ) = 2^8 = 1 ( mod 9 ) $
Che abbiamo visto essere falso.... come mai in questo caso la formula fallisce allora?
- Per quanto riguarda quindi i casi in cui il Massimo comun divisore è divero da 1, come nel caso del secondo esercizio, esiste una procedura "standard" ?
Il secondo esercizio è un caso "fortunato" in quanto il resto della divisione è $ 3 $ che, guarda caso, è esprimibile , elevandolo al quadrato, come potenza di $ 9 $ , il nostro divisore. ( consentendo quindi di affermare che $ 3^2 = 9 = 0 ( mod 9 ) $ esattamente come hai detto tu. )
Ma se il divisore non fosse $ 9 $ , ma comunque un numero non primo con il resto $ 3 $ come si dovrebbe operare?
P.s: Ma come mai i tag non mi funzionano? Anche se metto il quote, rimane il tag....
Primo esercizio:
Attento! Il piccolo teorema di Fermat dice che
"Se $p$ è primo e $a$ è un intero coprimo con $p$, allora $a^(p-1)-=1_(mod p)$."
Ora, è vero che $2$ è coprimo con $9$, ma $9$ non è un numero primo!!!
Quindi non puoi sfruttare il piccolo teorema di Fermat per la risoluzione di questo esercizio.
Secondo esercizio:
Sinceramente, non saprei. La scrittura dei codici sembra corretta, eppure non viene modificata. Strano
"claw91":
Tuttavia, sappiamo che se $ a^(p-1) = 1 ( mod p ) $ se e solo se $ mcd ( a,p ) = 1 $
Nel mio caso risulta $ 725843 = 2 ( mod 9 ) $
$ Mcd ( 2, 9 ) = 1 $ per cui $ 2^(9-1) = 1 ( mod 9 ) = 2^8 = 1 ( mod 9 ) $
Che abbiamo visto essere falso.... come mai in questo caso la formula fallisce allora?
Attento! Il piccolo teorema di Fermat dice che
"Se $p$ è primo e $a$ è un intero coprimo con $p$, allora $a^(p-1)-=1_(mod p)$."
Ora, è vero che $2$ è coprimo con $9$, ma $9$ non è un numero primo!!!
Quindi non puoi sfruttare il piccolo teorema di Fermat per la risoluzione di questo esercizio.
Secondo esercizio:
"claw91":Bisogna valutare caso per caso. Si può sempre sfruttare il piccolo teorema di Fermat (se sono verificate le ipotesi, ovviamente).
Ma se il divisore non fosse $ 9 $ , ma comunque un numero non primo con il resto $ 3 $ come si dovrebbe operare?
"claw91":
P.s: Ma come mai i tag non mi funzionano? Anche se metto il quote, rimane il tag....
Sinceramente, non saprei. La scrittura dei codici sembra corretta, eppure non viene modificata. Strano
Finalmente comincia ad essere tutto più chiaro, e te ne ringrazio.
Praticamente tutti gli esercizi sono risolvibili o con il piccolo teorema di Fermat ( quando p è primo ) oppure con il teorema di eulero (quando p non è primo )....
Ne è rimasto solo uno che non riesco a risolvere... ed è il famoso caso in cui p non è primo ed il massimo comun divisore tra il resto e p è diverso da 1 . ( quind quando i 2 numeri non sono coprimi ) :
$ 43816^20321 $ = ? $ mod 10 $
Allora:
$ 43816 = 6 mod 10 $
Ma $ mcd ( 6,10 ) = 2 $ quindi non sono applicabili nè Eulero nè Fermat, nè tantomeno è possibile esprimere 10 come una potenza di 2 ( come abbiam fatto con 3 e 9 nell'altro esercizio ) ...
Praticamente tutti gli esercizi sono risolvibili o con il piccolo teorema di Fermat ( quando p è primo ) oppure con il teorema di eulero (quando p non è primo )....
Ne è rimasto solo uno che non riesco a risolvere... ed è il famoso caso in cui p non è primo ed il massimo comun divisore tra il resto e p è diverso da 1 . ( quind quando i 2 numeri non sono coprimi ) :
$ 43816^20321 $ = ? $ mod 10 $
Allora:
$ 43816 = 6 mod 10 $
Ma $ mcd ( 6,10 ) = 2 $ quindi non sono applicabili nè Eulero nè Fermat, nè tantomeno è possibile esprimere 10 come una potenza di 2 ( come abbiam fatto con 3 e 9 nell'altro esercizio ) ...
Qua conviene fare in un altro modo.
Cercare quanto vale un numero modulo $10$ equivale a conoscere quanto vale la cifra dell'unità del numero stesso, ok?
Ad esempio, $1382328098-=8_(mod 10)$
Dunque dobbiamo capire qual è la cifra dell'unità di $6^20321$. Tu hai qualche idea?
Suggerimento: qual è la cifra delle unità di $6^1$? e di $6^2$? e di $6^3$? .... e di $6^n$, con $n in NN$?
Cercare quanto vale un numero modulo $10$ equivale a conoscere quanto vale la cifra dell'unità del numero stesso, ok?
Ad esempio, $1382328098-=8_(mod 10)$
Dunque dobbiamo capire qual è la cifra dell'unità di $6^20321$. Tu hai qualche idea?
Suggerimento: qual è la cifra delle unità di $6^1$? e di $6^2$? e di $6^3$? .... e di $6^n$, con $n in NN$?
Credo di aver capito il trucchetto: visto che, appunto, conoscere il resto di una divisione per 10 equivale a nient'altro che conoscere il valore della cifra delle unità di quel numero, nel nostro caso, le potenze di 6 : $ 6^1, 6^2 , 6^25 $ ....., $ 6 ^n $ con $ n in N $ hanno tutte come cifra delle unità $ 6 $....
Per cui anche il nostro bel $ 43816^20321 = 6 mod10 $
Poichè la cifra delle unità di $ 43816^20321 $ è determinata proprio dalla cifra delle unità di $ 6^20321 $ : sappiamo che $ 6^n $ è un numero la cui cifra delle unità è sempre uguale a $ 6 $, per cui il resto associata alla divisione per 10 di $ 6^20321 $ sarà proprio $ 6 $ !
Per cui anche il nostro bel $ 43816^20321 = 6 mod10 $
Poichè la cifra delle unità di $ 43816^20321 $ è determinata proprio dalla cifra delle unità di $ 6^20321 $ : sappiamo che $ 6^n $ è un numero la cui cifra delle unità è sempre uguale a $ 6 $, per cui il resto associata alla divisione per 10 di $ 6^20321 $ sarà proprio $ 6 $ !
Esatto!!! Hai capito benissimo, bravo 
Ti ringrazio per avermi seguito in questi giorni, ora è tutto chiaro! :D
Prego, figurati! Buona continuazione
Poi al massimo se hai tempo e voglia, visto che ti ho impegnato già abbastanza, potresti farti un giro in un altro thread che ho aperto sulla regola di Ruffini applicata ai polinomi.... credo che però venirne a capo sarà veramente facile stavolta....fortunatamente!
Per quanto riguarda la prima domanda, cioè la verifica di esercizi come quello proposto nel primo post, io trovo molto comodo wolfram alpha.
In quel caso, ad esempio, basta scrivere "29354^362971 mod6" per trovare subito la risposta (certo, è utile per la verifica, non è sostituibile alla risoluzione dell'esercizio)
In quel caso, ad esempio, basta scrivere "29354^362971 mod6" per trovare subito la risposta
(certo, è utile per la verifica, non è sostituibile alla risoluzione dell'esercizio)
ragazzi sono nuovo nel forum per favore potreste spiegarmi meglio il procedimento per trovare il resto quando a e p non sono coprimi.. non è tanto chiaro.. grazie
io ad esempio ho $362971^29345$ (mod6)
io ad esempio ho $362971^29345$ (mod6)
$ 362971^29345 (mod6)$
Dato che $6=2*3$, facciamo $362971^29345 (mod 2)$ e $362971^29345 (mod 3)$.
Si ha $362971^29345 -= 1 (mod 2)$ e $362971^29345 -= 1 (mod 3)$.
ora risolviamo ${(x-=1 (mod 2)),(x-=1 (mod 3)):}$
E' molto semplice: la soluzione è $x-=1 (mod 6)$. Fine
Dato che $6=2*3$, facciamo $362971^29345 (mod 2)$ e $362971^29345 (mod 3)$.
Si ha $362971^29345 -= 1 (mod 2)$ e $362971^29345 -= 1 (mod 3)$.
ora risolviamo ${(x-=1 (mod 2)),(x-=1 (mod 3)):}$
E' molto semplice: la soluzione è $x-=1 (mod 6)$. Fine
ah ecco grazie mille ora mi è più chiaro.. quindi basta semplicemente scomporre.. ma quel sistema come lo risolvi? con il teorema cinese dei resti?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo