Congruenze in modulo n
Trovare le ultime due cifre in base 10 del numero
$3202^(((1721)^507))$
In classe siamo giunti a ridurre tutto a
$\{(x-=0 mod4),(x-=2 mod25):}$
E poi l'esercizio va concluso a casa (il risultato è $x-=52 mod 100$). Ora, facendo tutti i passaggi, non riesco ad arrivare a trovare la soluzione.
Riporto qui sotto tutti i passaggi
$25$ e $4$ sono coprimi per qui posso applicare il teorema cinese del resto, ovvero:
$\{(x=0+4h),(x=2+25k):}$ con $h,k in ZZ$ da cui
$4h=2+25k$, cioè $4h-25k=2$
Scrivo un'identità di Bezout tra $4$ e $25$
$4u+25v=1$ da cui ricavo $u=-6$e $v=1$ e riscrivendo trovo che
$2*(-6)*4-(-2)*1*25=2$
Da cui ricavo $h=-12$ e $k=-2$ che mi portano a trovare il risultato
$\{(x=-48),(x=-48):}$ ovvero
$x-=-48 mod100$
Ad occhio conoscendo la soluzione vedo che $x-=52 mod100$ va bene ma senza io sarei arrivato alla soluzione $x-=-48 mod100$. Mi dite dove sto sbagliando?
Grazie
$3202^(((1721)^507))$
In classe siamo giunti a ridurre tutto a
$\{(x-=0 mod4),(x-=2 mod25):}$
E poi l'esercizio va concluso a casa (il risultato è $x-=52 mod 100$). Ora, facendo tutti i passaggi, non riesco ad arrivare a trovare la soluzione.
Riporto qui sotto tutti i passaggi
$25$ e $4$ sono coprimi per qui posso applicare il teorema cinese del resto, ovvero:
$\{(x=0+4h),(x=2+25k):}$ con $h,k in ZZ$ da cui
$4h=2+25k$, cioè $4h-25k=2$
Scrivo un'identità di Bezout tra $4$ e $25$
$4u+25v=1$ da cui ricavo $u=-6$e $v=1$ e riscrivendo trovo che
$2*(-6)*4-(-2)*1*25=2$
Da cui ricavo $h=-12$ e $k=-2$ che mi portano a trovare il risultato
$\{(x=-48),(x=-48):}$ ovvero
$x-=-48 mod100$
Ad occhio conoscendo la soluzione vedo che $x-=52 mod100$ va bene ma senza io sarei arrivato alla soluzione $x-=-48 mod100$. Mi dite dove sto sbagliando?
Grazie
Risposte
È la stessa cosa.
"axpgn":
È la stessa cosa.
Ma come fa un numero terminare con le ultime due cifre $52$ o in modulo $48$?
Non capisco questo? C'è modo di trovare $52$ dal $-48$ da me trovato?
"Aletzunny":
Ma come fa un numero terminare con le ultime due cifre $52$ o in modulo $48$?
Questa frase non vuol dire niente, cerca di essere più preciso quando vuoi dire qualcosa …
Cosa significa che un intero $a$ è congruo ad un altro $b$ modulo $c$ ?
Semplicemente che la differenza $a-b$ è un multiplo di $c$
Quindi nel tuo caso, se è vero che $x-52=100k$ cioè $x-52$ è un multiplo di $100$ allora lo sarà anche $x+48$.
Dimostrazione.
Per ipotesi abbiamo che $x-52=100k$ da cui $x=100k+52$.
Sostituendo in $x+48$ otteniamo $x=48+100k+52=100k+100=100(k+1)$ che chiaramente è divisibile per $100$ (come volevasi dimostrare).
Se un numero è congruo a $52$ modulo $100$, sarà congruo anche a $152$, $252$, ecc. ma anche a $-48, -148$, ecc.
Quello che non mi torna è che la richiesta è di trovare le ultime 2 cifre in base 10 del numero
$3202^(((1721)^507))$
E in classe ci è stato detto che è equivalente a risolvere il sistema
$\{(x-=0 mod4),(x-=2 mod25):}$
Ma allora questo numero secondo il mio risultato termine con le ultime due cifre $48$ e non $52$.
Questo non mi è chiaro
$3202^(((1721)^507))$
E in classe ci è stato detto che è equivalente a risolvere il sistema
$\{(x-=0 mod4),(x-=2 mod25):}$
Ma allora questo numero secondo il mio risultato termine con le ultime due cifre $48$ e non $52$.
Questo non mi è chiaro
Quello che non ti è chiaro è quello che ho scritto nel post precedente … rileggilo e rifletti … poi ne riparliamo ma domani perché "tra cinque minuti" NON è "riflettere" …
P.S.: Peccato che "tra cinque minuti" è "domani"
P.S.: Peccato che "tra cinque minuti" è "domani"
Io ci ho provato mezza serata ma davvero non riesco a capire...ho riletto la teoria sulle congruenze ma non riesco a vernirne a una.
Nel senso che alla domanda con quali cifre in base 10 termina il numero dato io avrei risposto 48 anziché 52 e non capisco come arrivare dal mio risultato (che per il sistema impostato è corretto perché -48-0 è multiplo di 4 e -48-2 è multiplo di 25) al risultato "corretto" del libro, cioè che il numero termina con le ultime due cifre 52
Nel senso che alla domanda con quali cifre in base 10 termina il numero dato io avrei risposto 48 anziché 52 e non capisco come arrivare dal mio risultato (che per il sistema impostato è corretto perché -48-0 è multiplo di 4 e -48-2 è multiplo di 25) al risultato "corretto" del libro, cioè che il numero termina con le ultime due cifre 52
Dici che hai letto e riletto la teoria delle congruenze ma mi pare che non l'hai ancora compresa appieno perché, in tal caso, ti sarebbe chiaro che la scrittura $x-=-48 mod 100$ non equivale a $x=-48$ ma a $x-(-48)=k*100$ con $k in ZZ$ (come detto poco sopra).
Quindi le soluzioni di quell'equazione sono infinite (una per ogni $k$) e non una sola ($-48$); difatti lo sono anche $52, 152, 252, -48, -148, -248, …$ )
Quale tra queste infinite soluzioni è quella che risolve il problema? L'unica che ha due cifre cioè $52$ (faccio notare che $-48$ ha due cifre ma con il meno davanti che è difficile da piazzare all'interno di un numero)
Quindi le soluzioni di quell'equazione sono infinite (una per ogni $k$) e non una sola ($-48$); difatti lo sono anche $52, 152, 252, -48, -148, -248, …$ )
Quale tra queste infinite soluzioni è quella che risolve il problema? L'unica che ha due cifre cioè $52$ (faccio notare che $-48$ ha due cifre ma con il meno davanti che è difficile da piazzare all'interno di un numero)
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo