Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 27/01/2015, 21:05

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
daniele087
Starting Member
Starting Member
 
Messaggio: 6 di 48
Iscritto il: 13/11/2014, 09:53

Re: Calcolare x = 13^1234 mod 105

Messaggioda minomic » 27/01/2015, 22:32

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.
Avatar utente
minomic
Cannot live without
Cannot live without
 
Messaggio: 3739 di 7860
Iscritto il: 22/01/2011, 18:32

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 27/01/2015, 22:58

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
daniele087
Starting Member
Starting Member
 
Messaggio: 7 di 48
Iscritto il: 13/11/2014, 09:53

Re: Calcolare x = 13^1234 mod 105

Messaggioda minomic » 27/01/2015, 23:01

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.
Avatar utente
minomic
Cannot live without
Cannot live without
 
Messaggio: 3740 di 7860
Iscritto il: 22/01/2011, 18:32

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 27/01/2015, 23:06

uhm...uffa questo esercizio mi sta facendo dannare.
Grazie.
daniele087
Starting Member
Starting Member
 
Messaggio: 8 di 48
Iscritto il: 13/11/2014, 09:53

Messaggioda Gi8 » 27/01/2015, 23:18

$ 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)$
Gi8
Cannot live without
Cannot live without
 
Messaggio: 4514 di 9559
Iscritto il: 18/02/2010, 20:20

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 27/01/2015, 23:38

Grazie Gi8.
Domani riproverò a risolvere l'esercizio e ti/vi farò sapere.
daniele087
Starting Member
Starting Member
 
Messaggio: 9 di 48
Iscritto il: 13/11/2014, 09:53

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 03/02/2015, 13:13

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.
daniele087
Starting Member
Starting Member
 
Messaggio: 10 di 48
Iscritto il: 13/11/2014, 09:53

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 03/02/2015, 15:22

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.
daniele087
Starting Member
Starting Member
 
Messaggio: 11 di 48
Iscritto il: 13/11/2014, 09:53

Re: Calcolare x = 13^1234 mod 105

Messaggioda daniele087 » 03/02/2015, 16:28

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
daniele087
Starting Member
Starting Member
 
Messaggio: 12 di 48
Iscritto il: 13/11/2014, 09:53

Prossimo

Torna a Geometria e algebra lineare

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite