Determinare le ultime cifra di un numero mediante congruenza
Salve a tutti,
a lezione la professoressa ci ha dimostrato come determinare l'ultima cifra di un numero trovando il resto della divisione per quel numero per 10 e quel resto era proprio l'ultima cifra.
Ovvero ha dimostrato che:
$57432^12 -= r (mod 10)$
Ovvero se divido $57432$ per $10$ ho $r= 2$
Quindi $57432 -= 2 (mod 10)$
Per le proprietà delle congruenze dice che: $57432^12 -= 2^12 (mod 10)$
E poi cerca di trovare a chi è congruo $2^12$ in modulo 10 e ottiene il resto di 6 tramite "alcuni trucchetti", chiamiamoli cosi.
Ora ci ha detto di trovare le ultime due cifre del numero $302^40$, l'unica indicazione che ci da è che per trovare le ultime cifre dobbiamo farlo in modulo $100$.
Però essendo qui una potenza molto alta non riesco a fare gli stessi trucchi della dimostrazione, ovvero mi ritrovo che:
$302^40 -= 2^40 (mod 100)$
E per trovarmi l'ultima cifra mi devo trovare a chi è congruo $2^40$ in modulo $100$.
Se prendo una calcolatrice e divido per 100 tanti auguri, ma volevo farlo tramite calcoli "a mano", perchè credo che sia quello "il punto". Come posso traformare 2^40 in qualcosa di più piccolo in modo che poi sia calcolabile a mano?
Vi ringrazio in anticipo per la disponibilità,
Neptune.
a lezione la professoressa ci ha dimostrato come determinare l'ultima cifra di un numero trovando il resto della divisione per quel numero per 10 e quel resto era proprio l'ultima cifra.
Ovvero ha dimostrato che:
$57432^12 -= r (mod 10)$
Ovvero se divido $57432$ per $10$ ho $r= 2$
Quindi $57432 -= 2 (mod 10)$
Per le proprietà delle congruenze dice che: $57432^12 -= 2^12 (mod 10)$
E poi cerca di trovare a chi è congruo $2^12$ in modulo 10 e ottiene il resto di 6 tramite "alcuni trucchetti", chiamiamoli cosi.
Ora ci ha detto di trovare le ultime due cifre del numero $302^40$, l'unica indicazione che ci da è che per trovare le ultime cifre dobbiamo farlo in modulo $100$.
Però essendo qui una potenza molto alta non riesco a fare gli stessi trucchi della dimostrazione, ovvero mi ritrovo che:
$302^40 -= 2^40 (mod 100)$
E per trovarmi l'ultima cifra mi devo trovare a chi è congruo $2^40$ in modulo $100$.
Se prendo una calcolatrice e divido per 100 tanti auguri, ma volevo farlo tramite calcoli "a mano", perchè credo che sia quello "il punto". Come posso traformare 2^40 in qualcosa di più piccolo in modo che poi sia calcolabile a mano?
Vi ringrazio in anticipo per la disponibilità,
Neptune.
Risposte
Ciao.
Ricorda per esempio che $2^{10}=1024$, quindi $2^{40} = 1024^4$...
Ricorda per esempio che $2^{10}=1024$, quindi $2^{40} = 1024^4$...
Ma anche $1024^4$ è sempre un numero molto alto, non lo abbiamo abbassato per nulla e non mi viene in mente nulla..
Grossomodo l'ho sviluppato in questo modo, spero sia corretto:
$302^40 -= r(mod 100)$
$302 -= 2 (mod 100)$
$302^40 -= 2^40(mod 100)$
A questo punto dobbiamo lavorare su $2^40$, che come hai deto tu può essere scritto come $1024^4$
Quindi se sussiste l'uguaglianza di sopra, possiamo anche dire che esiste la congruenza $2^40 -= 1024^4$
Ovvero possiamo vedere $1024$ a cosa è congruo in $(mod 100)$ ?
e troviamo che $1024 -= 24(mod 100)$
ovvero $1024^4 -= 24^4(mod 100)$
A questo punto possiamo lavorare su $24^4$
Prendiamo $24^2 -= 76 (mod 100)$
Ovvero $24^4 -= 76^2 (mod 100)$
Lavoriamo su $76^2$, vediamo che 76 e 100 sono coprimi tra loro, possiamo quindi semplificarlo in:
$76 -= r (mod 100)$ dove $r$ sarà proprio uguale a 76?
e difatti $2^40 = 1099511627776$ ovvero le sue due ultime cifre sono proprio quelle trovate.
Sempre che possa fare i calcoli sopra detti e non siano "troppo di fantasia".
$302^40 -= r(mod 100)$
$302 -= 2 (mod 100)$
$302^40 -= 2^40(mod 100)$
A questo punto dobbiamo lavorare su $2^40$, che come hai deto tu può essere scritto come $1024^4$
Quindi se sussiste l'uguaglianza di sopra, possiamo anche dire che esiste la congruenza $2^40 -= 1024^4$
Ovvero possiamo vedere $1024$ a cosa è congruo in $(mod 100)$ ?
e troviamo che $1024 -= 24(mod 100)$
ovvero $1024^4 -= 24^4(mod 100)$
A questo punto possiamo lavorare su $24^4$
Prendiamo $24^2 -= 76 (mod 100)$
Ovvero $24^4 -= 76^2 (mod 100)$
Lavoriamo su $76^2$, vediamo che 76 e 100 sono coprimi tra loro, possiamo quindi semplificarlo in:
$76 -= r (mod 100)$ dove $r$ sarà proprio uguale a 76?
e difatti $2^40 = 1099511627776$ ovvero le sue due ultime cifre sono proprio quelle trovate.
Sempre che possa fare i calcoli sopra detti e non siano "troppo di fantasia".
"Neptune":$76$ e $100$ non sono coprimi tra loro. E comunque, a cosa ti servirebbe? Io direi semplicemente così: $76^2 -= (-24)^2 -= 24^2 -= 76$.
Lavoriamo su $76^2$, vediamo che 76 e 100 sono coprimi tra loro, possiamo quindi semplificarlo in:
$76 -= r (mod 100)$ dove $r$ sarà proprio uguale a 76?
e difatti $2^40 = 1099511627776$ ovvero le sue due ultime cifre sono proprio quelle trovate.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo