Calcolare x = 13^1234 mod 105
Ciao,
scusatemi ma sto incontrando varie difficoltà nel capire come svolgere esercizi come: calcolare x = 13^1234 mod 105
Potreste gentilmente spiegarmi come impostare questi esercizi?
Avete qualche dispensa con esercizi di questo tipo?
Grazie
scusatemi ma sto incontrando varie difficoltà nel capire come svolgere esercizi come: calcolare x = 13^1234 mod 105
Potreste gentilmente spiegarmi come impostare questi esercizi?
Avete qualche dispensa con esercizi di questo tipo?
Grazie
Risposte
Ciao, possiamo ragionare in questo modo: \[
13^4 \mod 105 = 1
\] $1234 = 4*308 + 2$, quindi vuol dire che ci sono $308$ "pezzi" che fanno sempre $1$. Il risultato parziale è quindi $1^(308) = 1$. Rimangono fuori due pezzi da $13$, quindi il risultato finale è \[
13^2 \mod 105 = 64
\] Diciamo che quindi una buona strategia è quella di spezzare un problema grande in tanti problemi piccoli.
13^4 \mod 105 = 1
\] $1234 = 4*308 + 2$, quindi vuol dire che ci sono $308$ "pezzi" che fanno sempre $1$. Il risultato parziale è quindi $1^(308) = 1$. Rimangono fuori due pezzi da $13$, quindi il risultato finale è \[
13^2 \mod 105 = 64
\] Diciamo che quindi una buona strategia è quella di spezzare un problema grande in tanti problemi piccoli.
Ciao,
intanto grazie per la risposta.
Purtroppo non mi trovo granchè, perchè l'esercizio l'ho preso dal quaderno (purtroppo lo svolgimento è stato fatto un poco di fretta), e come risultato ho un sistema di 2 congruenze:
x congruo 1 mod 3
x congruo 4 mod 5
intanto grazie per la risposta.
Purtroppo non mi trovo granchè, perchè l'esercizio l'ho preso dal quaderno (purtroppo lo svolgimento è stato fatto un poco di fretta), e come risultato ho un sistema di 2 congruenze:
x congruo 1 mod 3
x congruo 4 mod 5
Su quello non so cosa dirti... Io mi sono limitato a calcolare \[
13^{1234}\mod 105 = 64
\] e confermo che il risultato è corretto: l'ho anche controllato con questo tool online.
13^{1234}\mod 105 = 64
\] e confermo che il risultato è corretto: l'ho anche controllato con questo tool online.
uhm...uffa questo esercizio mi sta facendo dannare.
Grazie.
Grazie.
$ 13^1234 mod 105$
Dato che $105=3*5*7$, calcoliamo separatamente $ 13^1234 mod 3$, $ 13^1234 mod 5$ e $ 13^1234 mod 7$
Si ha $13^1234 -=1^1234 = 1 (mod 3)$, $13^1234 -=...= 4 (mod 5)$ e $13^(1234)-= (-1)^1234= 1 (mod 7)$.
Ora dobbiamo risolvere ${(x-=1 (mod 3)),(x -= 4 (mod 5)),(x-= 1 (mod 7)):}$
Si può fare col teorema cinese del resto, o anche in altri modi.
Ad esempio, posto $y= x-1$, si ha che $y$ è multiplo di $21$ e $y-=3 (mod 5)$
Tra $0$ e $104$ i multipli di $21$ sono solo $0, 21, 42,63,84$. Solo uno di questi è congruo a $3$ modulo $5$, cioè $63$.
Dunque $x-= 64 mod (105)$
Dato che $105=3*5*7$, calcoliamo separatamente $ 13^1234 mod 3$, $ 13^1234 mod 5$ e $ 13^1234 mod 7$
Si ha $13^1234 -=1^1234 = 1 (mod 3)$, $13^1234 -=...= 4 (mod 5)$ e $13^(1234)-= (-1)^1234= 1 (mod 7)$.
Ora dobbiamo risolvere ${(x-=1 (mod 3)),(x -= 4 (mod 5)),(x-= 1 (mod 7)):}$
Si può fare col teorema cinese del resto, o anche in altri modi.
Ad esempio, posto $y= x-1$, si ha che $y$ è multiplo di $21$ e $y-=3 (mod 5)$
Tra $0$ e $104$ i multipli di $21$ sono solo $0, 21, 42,63,84$. Solo uno di questi è congruo a $3$ modulo $5$, cioè $63$.
Dunque $x-= 64 mod (105)$
Grazie Gi8.
Domani riproverò a risolvere l'esercizio e ti/vi farò sapere.
Domani riproverò a risolvere l'esercizio e ti/vi farò sapere.
Scusate il ritardo.
Ho provato a completare l'esercizio ma non sono riuscito.
Sono riuscito a calcolare solo 13^1234.
Non capisco come mai quando vado a calcolare la 2a congruenza e la 3a congruenza devo operare in maniere differenti rispetto al calcolo eseguito per la prima.
Più tardi se non riesco a venirne a capo vi vorrei postare l'esercizio su carta.
Ho provato a completare l'esercizio ma non sono riuscito.
Sono riuscito a calcolare solo 13^1234.
Non capisco come mai quando vado a calcolare la 2a congruenza e la 3a congruenza devo operare in maniere differenti rispetto al calcolo eseguito per la prima.
Più tardi se non riesco a venirne a capo vi vorrei postare l'esercizio su carta.
Fino ad ora sono riuscito a calcolare le prime 2 congruenze.
Vi posto i fogli con i calcoli:
Pagina1
Pagina2
Ho però nette difficoltà nel capire, studiando la soluzione vista in classe, come è stata calcolata l'ultima congruenza, cioè 13^1234 mod 7, perchè viene trovato che:
13 = -1 mod 7
Non capisco quel -1 da dove esca fuori.
Vi posto i fogli con i calcoli:
Pagina1
Pagina2
Ho però nette difficoltà nel capire, studiando la soluzione vista in classe, come è stata calcolata l'ultima congruenza, cioè 13^1234 mod 7, perchè viene trovato che:
13 = -1 mod 7
Non capisco quel -1 da dove esca fuori.
Ragazzi, mi potreste aiutare a capire come si calcola l'ultima congruenza?
Io ho provato in questo modo, ma evidentemente sto sbagliando non tanto il ragionamento (i conti tornano), ma il procedimento, visto che mi vengono numeri più grandi di quelli che sono usciti a lezione.
Devo calcolare 13^1234 mod 7
MCD(13, 7) = -1
phi(7) = 6
13^phi(7) = -1 mod 7 che equivale a dire 13^6 = -1 mod 7
13^1234 = (13^6)^205 * 13^4
13^4 congruo 7 è il risultato, ma ovviamente quella potenza non ci deve stare
Il risultato "corretto" deve essere:
(-1)^1234 mod 7
x congruo 1 mod 7
Io ho provato in questo modo, ma evidentemente sto sbagliando non tanto il ragionamento (i conti tornano), ma il procedimento, visto che mi vengono numeri più grandi di quelli che sono usciti a lezione.
Devo calcolare 13^1234 mod 7
MCD(13, 7) = -1
phi(7) = 6
13^phi(7) = -1 mod 7 che equivale a dire 13^6 = -1 mod 7
13^1234 = (13^6)^205 * 13^4
13^4 congruo 7 è il risultato, ma ovviamente quella potenza non ci deve stare
Il risultato "corretto" deve essere:
(-1)^1234 mod 7
x congruo 1 mod 7
Non capisci perchè $13 -= -1 (mod 7)$?
Due numeri sono congrui modulo 7 (per definizione) se la loro differenza è multiplo di 7.
$13 - (-1)= 13+1=14$, e 14 è multiplo di 7.
Due numeri sono congrui modulo 7 (per definizione) se la loro differenza è multiplo di 7.
$13 - (-1)= 13+1=14$, e 14 è multiplo di 7.
Ciao,
no non è quello il mio dubbio.
Ho difficoltà a capire come mai il prof quando ha fatto vedere questo esercizio ha scritto:
13^1234 mod7
13 = -1 mod 7
13^1234 congruo (-1)^1234 mod 7
quindi x congruo 1 mod7
mentre io ottengo:
MCD(13, 7) = -1
phi(7) = 6
13^phi(7) = -1 mod 7 che equivale a dire 13^6 = -1 mod 7
13^1234 = (13^6)^205 * 13^4
13^4 mod 7
Ora...è vero che 13^4 mod 7 è uguale a 1 mod 7, ma non capisco che trucco o che regola abbia usato per evitare di arrivare a questo punto.
Considera anche se non posso usare calcolatrici all'esame, quindi fare un conto del genere sarebbe da evitare.
no non è quello il mio dubbio.
Ho difficoltà a capire come mai il prof quando ha fatto vedere questo esercizio ha scritto:
13^1234 mod7
13 = -1 mod 7
13^1234 congruo (-1)^1234 mod 7
quindi x congruo 1 mod7
mentre io ottengo:
MCD(13, 7) = -1
phi(7) = 6
13^phi(7) = -1 mod 7 che equivale a dire 13^6 = -1 mod 7
13^1234 = (13^6)^205 * 13^4
13^4 mod 7
Ora...è vero che 13^4 mod 7 è uguale a 1 mod 7, ma non capisco che trucco o che regola abbia usato per evitare di arrivare a questo punto.
Considera anche se non posso usare calcolatrici all'esame, quindi fare un conto del genere sarebbe da evitare.
Tu devi svolgere l'esercizio nello stesso identico modo in cui l'ha svolto il tuo professore (che è lo stesso mio).
La prima cosa da fare, infatti, è semplificare il più possibile. Mai fare un esercizio a macchinetta.
La prima cosa da fare, infatti, è semplificare il più possibile. Mai fare un esercizio a macchinetta.
Le prime 2 congruenze le ho svolte esattamente come fa il prof.
Non capisco l'ultima però.
Anche se ho seguito il procedimento che ha spiegato a lezione, mi vengono numeri differenti (nonostante comunque portino alla soluzione).
Potresti spiegarmi che procedimento si deve utilizzare?
Non capisco l'ultima però.
Anche se ho seguito il procedimento che ha spiegato a lezione, mi vengono numeri differenti (nonostante comunque portino alla soluzione).
Potresti spiegarmi che procedimento si deve utilizzare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo