Proprietà delle congruenze a me sconosciuta
Salve a tutti,
nel dimostrare una semplificazione di una congruenza siamo arrivati a:
$10^16 -= 10*10^5 (mod 11)$
a questo punto la professoressa ha detto che, considerando:
$10^(2p) -= 1 (mod 11)$
$10^(2p+1) -= -1 (mod 11)$
possiamo applicarlo alla nostra formula e ottenere
$10^16 -= 1 (mod 11)$
Sinceramente da quel "considerando" non riesco a dedurre quale sia la formula generale. Quel $p$ starà per pari? cioè sta dicendo che in modulo undici tutte le potenze pari di 10 sono congrue 1 e tutte le dispari sono congrue -1? e ciò vale solo se abbiamo come base della potenza 10 e modulo 11? o cosa? No perchè ho un piccolo "prontuario delle proprietà" e non mi risulta questa.
nel dimostrare una semplificazione di una congruenza siamo arrivati a:
$10^16 -= 10*10^5 (mod 11)$
a questo punto la professoressa ha detto che, considerando:
$10^(2p) -= 1 (mod 11)$
$10^(2p+1) -= -1 (mod 11)$
possiamo applicarlo alla nostra formula e ottenere
$10^16 -= 1 (mod 11)$
Sinceramente da quel "considerando" non riesco a dedurre quale sia la formula generale. Quel $p$ starà per pari? cioè sta dicendo che in modulo undici tutte le potenze pari di 10 sono congrue 1 e tutte le dispari sono congrue -1? e ciò vale solo se abbiamo come base della potenza 10 e modulo 11? o cosa? No perchè ho un piccolo "prontuario delle proprietà" e non mi risulta questa.
Risposte
Ok quella di sopra l'ho trovata, è una proprietà del modulo di una potenza di 10 per 11.
Però adesso me ne sfugge un'altra:
Abbiamo $4526^236 -= 4^236 (mod7)$
e subito dopo dice di considerare $4^236$ dicendo che $7$ è primo, $mcd(4,7)=1$ allora applichiamo il piccolo teorema di fermat.
Ma il piccolo teorema di fermat non lo si applica se e solo se un determinato numero è elevato ad un numero $p$ primo ed il modulo è il medesimo numero $p$?
Come ha fatto a far diventare $4^236$ in $4^7$?
Però adesso me ne sfugge un'altra:
Abbiamo $4526^236 -= 4^236 (mod7)$
e subito dopo dice di considerare $4^236$ dicendo che $7$ è primo, $mcd(4,7)=1$ allora applichiamo il piccolo teorema di fermat.
Ma il piccolo teorema di fermat non lo si applica se e solo se un determinato numero è elevato ad un numero $p$ primo ed il modulo è il medesimo numero $p$?
Come ha fatto a far diventare $4^236$ in $4^7$?
Quando $(a, p) = 1$ (corollario importante del teorema di fermat) $a^(p-1) \equiv 1 (mod p)$.
Nel tuo caso $4^(236) \equiv 4^(6\cdot39)\cdot4^2 \equiv (4^6)^(39)\cdot4^2 \equiv 4^2 \equiv 2 (mod 7)$
P.S.
Nel tuo esempio precedente, quello è vero perchè $10 \equiv -1 (mod 11)$ e chiaramente vale in generale, non solo per 10 e 11 ma per ogni coppia di numeri consecutivi.
Nel tuo caso $4^(236) \equiv 4^(6\cdot39)\cdot4^2 \equiv (4^6)^(39)\cdot4^2 \equiv 4^2 \equiv 2 (mod 7)$
P.S.
Nel tuo esempio precedente, quello è vero perchè $10 \equiv -1 (mod 11)$ e chiaramente vale in generale, non solo per 10 e 11 ma per ogni coppia di numeri consecutivi.
Giusto, sono regole "stupide" ma il fatto di non avercele tutte sotto mano mi sta facendo un pò perdere. In rete però non riesco a trovare un prontuario delle formule completo, mi sa che mi devo mettere e "crearmelo".
Nel secondo esempio difatti mi sfuggiva come arrivasse a 7, così di colpo, perchè mancavano i passaggi intermedi e non mi sono accorto che aveva semplicemente applicato la regola delle potenze.
Per il primo caso invece mi potresti scrivere la formula generale ? cosi la capisco meglio.
Nel secondo esempio difatti mi sfuggiva come arrivasse a 7, così di colpo, perchè mancavano i passaggi intermedi e non mi sono accorto che aveva semplicemente applicato la regola delle potenze.
Per il primo caso invece mi potresti scrivere la formula generale ? cosi la capisco meglio.
Non è che sono "regole generali", sono casi che di volta in volta devi vedere a occhio... nel tuo primo esempio, se hai $n^k (mod$ $n+1)$, poichè $n \equiv -1 (mod$ $n+1)$ hai che $n^k \equiv (-1)^k (mod$ $n+1)$ e quindi può assumere solo i valori $1$ (potenze pari) e $-1$ (potenze dispari).
Capisco, posso cogliere l'occasione per chiedere se questo esercizio l'ho svolto bene? anche perchè credo che magari il tutto possa risolversi con meno passaggi.
L'esercizio dice di calcolare l'$r$ di questa congruenza: $21^362 -= r (mod 118)$
Mi accorgo subito (si vabbè dicono tutti cosi, io in realtà mi sono fatto 6 divisioni per accorgermene) che $mcd(118,21) = 1$
Utilizzo quindi il teorema di eulero fermat:
$21^(\phi(118)) -= 1 mod (118)$
Per calcolarci $\phi(118)$ ci scomponiamo prima in fattori primi $118$ ed otteniamo che $118= 2*59$
Ovvero dobbiamo calcolarci:
$\phi(59) * \phi(2)$ che è uguale a $1*58=58$
Abbiamo quindi che $21^58 -= 1 (mod 118)$
Ora scomponiamo $362$ in modo che risulti come un prodotto di 58 ed otteniamo:
$362 = 58*6+14$ ovvero $(21^58)^6 * 21^14 -= 1* 21^14 mod (118)$
Quindi $21^362 -= 21^14 mod (118)$
Abbiamo quindi $21^14 -= r (mod 118)$ e dobbiamo calcolarci questa r.
Ora da qui in poi non so se potevo risparmiarmi qualche calcolo oppure sono tutti necessari.
Riscriviamo $21^14$ come $(21^2)^7$ e otteniamo $21^2 = 441$
Quindi $21^2 -= 87 (mod 118)$
$(21^2)^7 -= 87^7 (mod 118)$
Essendo $87^7$ ancora troppo grande ce lo scomponiamo ancora per vedere a cosa e congruo e otteniamo:
$87^7 = (87^2)^3 * 87$
$87^2 -= 17 (mod 118)$
$(87^2)^3*87 -= 17^3*87 (mod 118)$
$17^3*87 = 427431$ ed $427431 -= 35 (mod 118)$
Quindi per transitività:
$87^7 -= 35 (mod 118)$
$21^14 -= 35 (mod 118)$
E come risultato avremo quindi che $21^362 -= 35 (mod 118)$
Quindi in pratica ottenendo anche dal teorema di Eulero-Fermat un numero abbastanza grande ho continuato a "semplificare" fino ad otteere un numero che la calcolatrice è riuscito a divideremi, ed alla fine ho detto che per transitività quel numero è proprio il resto che stavo cercando.
Ho fatto bene i calcoli? e sopratutto non è che magari mi è sfuggita qualche proprietà che mi poteva risparmiare tutti questi calcoli finali?
L'esercizio dice di calcolare l'$r$ di questa congruenza: $21^362 -= r (mod 118)$
Mi accorgo subito (si vabbè dicono tutti cosi, io in realtà mi sono fatto 6 divisioni per accorgermene) che $mcd(118,21) = 1$
Utilizzo quindi il teorema di eulero fermat:
$21^(\phi(118)) -= 1 mod (118)$
Per calcolarci $\phi(118)$ ci scomponiamo prima in fattori primi $118$ ed otteniamo che $118= 2*59$
Ovvero dobbiamo calcolarci:
$\phi(59) * \phi(2)$ che è uguale a $1*58=58$
Abbiamo quindi che $21^58 -= 1 (mod 118)$
Ora scomponiamo $362$ in modo che risulti come un prodotto di 58 ed otteniamo:
$362 = 58*6+14$ ovvero $(21^58)^6 * 21^14 -= 1* 21^14 mod (118)$
Quindi $21^362 -= 21^14 mod (118)$
Abbiamo quindi $21^14 -= r (mod 118)$ e dobbiamo calcolarci questa r.
Ora da qui in poi non so se potevo risparmiarmi qualche calcolo oppure sono tutti necessari.
Riscriviamo $21^14$ come $(21^2)^7$ e otteniamo $21^2 = 441$
Quindi $21^2 -= 87 (mod 118)$
$(21^2)^7 -= 87^7 (mod 118)$
Essendo $87^7$ ancora troppo grande ce lo scomponiamo ancora per vedere a cosa e congruo e otteniamo:
$87^7 = (87^2)^3 * 87$
$87^2 -= 17 (mod 118)$
$(87^2)^3*87 -= 17^3*87 (mod 118)$
$17^3*87 = 427431$ ed $427431 -= 35 (mod 118)$
Quindi per transitività:
$87^7 -= 35 (mod 118)$
$21^14 -= 35 (mod 118)$
E come risultato avremo quindi che $21^362 -= 35 (mod 118)$
Quindi in pratica ottenendo anche dal teorema di Eulero-Fermat un numero abbastanza grande ho continuato a "semplificare" fino ad otteere un numero che la calcolatrice è riuscito a divideremi, ed alla fine ho detto che per transitività quel numero è proprio il resto che stavo cercando.
Ho fatto bene i calcoli? e sopratutto non è che magari mi è sfuggita qualche proprietà che mi poteva risparmiare tutti questi calcoli finali?
Credo che l'esercizio sia giusto (in realtà non ho controllato i calcoli), io non credo che l'avrei fatto con meno passaggi. Volevo chiederti solo una cosa:
Ma hai usato l'algoitmo di Euclide per il calcolo del MCD?
E' più facile vedere che $118=2\cdot59$ e che $21=3\cdot7$ è la fattorizzazione in primi di $118$ e $21$ e quindi $MCD(118,21)=1$. Così è più facile accorgersene subito!
Io di solito uso l'algoritmo di Euclide o quando i numeri sono troppo grandi o quando devo trovare l'identità di Bezout.
"Neptune":
Mi accorgo subito (si vabbè dicono tutti cosi, io in realtà mi sono fatto 6 divisioni per accorgermene) che $mcd(118,21) = 1$
Ma hai usato l'algoitmo di Euclide per il calcolo del MCD?
E' più facile vedere che $118=2\cdot59$ e che $21=3\cdot7$ è la fattorizzazione in primi di $118$ e $21$ e quindi $MCD(118,21)=1$. Così è più facile accorgersene subito!
Io di solito uso l'algoritmo di Euclide o quando i numeri sono troppo grandi o quando devo trovare l'identità di Bezout.
"cirasa":
Credo che l'esercizio sia giusto (in realtà non ho controllato i calcoli), io non credo che l'avrei fatto con meno passaggi. Volevo chiederti solo una cosa:
[quote="Neptune"]
Mi accorgo subito (si vabbè dicono tutti cosi, io in realtà mi sono fatto 6 divisioni per accorgermene) che $mcd(118,21) = 1$
Ma hai usato l'algoitmo di Euclide per il calcolo del MCD?
E' più facile vedere che $118=2\cdot59$ e che $21=3\cdot7$ è la fattorizzazione in primi di $118$ e $21$ e quindi $MCD(118,21)=1$. Così è più facile accorgersene subito!
Io di solito uso l'algoritmo di Euclide o quando i numeri sono troppo grandi o quando devo trovare l'identità di Bezout.[/quote]
Bè si, si parla dell'algoritmo euclideo delle divisioni successive. Per trovare che 118 e 21 sono coprimi, ovvero che il loro mcd è 1, bisogna fare 6 divisioni.
Tra l'altro bezout è un'altro che non mi ricordo, e tra l'altro lo si può evitare facilmente: Una volta che hai trovato l'mcd, sempre che sia diverso da 1, dividi i numeri per il loro mcd e ottieni dei numeri "semplici" e a quel punto le identità le trovi ad occhio, senza aver bisogno dell'algoritmo. Tant'è che a fure di non usarlo me lo sono dimenticato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo