Cifra delle migliaia di numero non calcolabile
Determina la cifra delle unità e quella delle centinaia del numero $17^{169}$.
Procedimento seguito:
per calcolare la cifra delle migliaia è come calcolare il resto della divisione per 1000,
$\varphi(1000) = 400$
per il teorema di Eulero vale la relazione
$\overline{17}^{400} \equiv 1 \ mod \ 1000$
ma come scompongo $17^{169}$ in modo da semplificare il calcolo?
Procedimento seguito:
per calcolare la cifra delle migliaia è come calcolare il resto della divisione per 1000,
$\varphi(1000) = 400$
per il teorema di Eulero vale la relazione
$\overline{17}^{400} \equiv 1 \ mod \ 1000$
ma come scompongo $17^{169}$ in modo da semplificare il calcolo?
Risposte
"Frodo478":
ma come scompongo $ 17^{169} $ in modo da semplificare il calcolo?
viewtopic.php?p=838211#p838211
Non saprei come spiegarlo meglio... non che all'epoca lo abbia spiegato in chissà quale metodo fantastico.
"Zero87":
In pratica, vedi come scrivere l'esponente dividendolo sempre per 2. Per es.
$427=426+1=213\cdot 2 +1= (212+1)\cdot 2 +1= ((106 \cdot 2 +1)+1) \cdot 2 +1$ e così via.
Questo è quello che vorrei fare, ma nel mio caso $7^{169}$ è minore di $7^{400}$. Io credo che dovrei appunto scomporre il numero cercando di ottenere $7^{400}$ che risulta conguente ad $1$ e quindi "semplificarlo".
In questo caso l'esponente risulta essere minore, quindi non riesco ad usare il giochino.
Non ti seguo, ma persevero - in buona fede - con il metodo che ricordo
$169=168+1=(84\cdot 2)+1=((42\cdot 2) \cdot 2)+1$, ecc...
in pratica si va avanti a iosa anche se ora mi sono fermato
$17^169=(((17^42)^2)^2)\cdot 17$
e il calcolo - lo avessi scomposto tutto - sarebbe stato semplice perché in modulo basta moltiplicare/elevare a potenza i vari resti di volta in volta se il numero è maggiore di 1000.
$169=168+1=(84\cdot 2)+1=((42\cdot 2) \cdot 2)+1$, ecc...
in pratica si va avanti a iosa anche se ora mi sono fermato
$17^169=(((17^42)^2)^2)\cdot 17$
e il calcolo - lo avessi scomposto tutto - sarebbe stato semplice perché in modulo basta moltiplicare/elevare a potenza i vari resti di volta in volta se il numero è maggiore di 1000.
"Zero87":
Non ti seguo, ma persevero - in buona fede - con il metodo che ricordo
Ti ringrazio, infatti non è ancora chiaro come arrivare alla soluzione, ma spero di riuscire a completare l'esercizio
Ora eseguendo i calcoli sono arrivato qui:
$17^{169} = ((((((17^{2})^{2})+1)^{2^{2}})+1)^{2^{3}})+1$
Il problema è che ora come semplifico il calcolo?
Dovrei risolvere $17^{169} \ mod \ 1000$ cosi da trovare le ultime tre cifre di questo numero gigantesco.
Con questo metodo, alla fine, hai calcoli molto più brevi - invece di fare $17\cdot 17 \cdot ...$ per $169$ volte, fai meno calcoli ma comunque i calcoli ce li hai lo stesso. 
Comunque la scomposizione ha qualche problemuccio, come esponenti dovrebbero comparire solo tanti 2, ma magari hai raggruppato qualcosa che ora mi sfugge.
Comunque ho finalmente trovato quello che cercavo, cioè post passati dove parlavo di questo algoritmo quando le mie conoscenze, più prossime alla laurea, erano migliori!
viewtopic.php?p=841464#p841464
viewtopic.php?p=786893#p786893 (specie i 2 post sotto a questo).
Comunque la scomposizione ha qualche problemuccio, come esponenti dovrebbero comparire solo tanti 2, ma magari hai raggruppato qualcosa che ora mi sfugge.
Comunque ho finalmente trovato quello che cercavo, cioè post passati dove parlavo di questo algoritmo quando le mie conoscenze, più prossime alla laurea, erano migliori!
viewtopic.php?p=841464#p841464
viewtopic.php?p=786893#p786893 (specie i 2 post sotto a questo).
Il professore di algebra a lezione ci ha insegnato il "metodo della potenza veloce" (non che sia poi così veloce); le uguaglianze sono da intendersi come congruenze modulo \(1000\):
\(17^1 = 17\)
\(17^2 = (10+7)^2 = 289\)
\(17^4 = 289^2 = 521\)
\(17^8 = 521^2 = 441\)
\(17^{16} = 441^2 = 481\)
\(17^{32} = 481^2 = 361\)
\(17^{64} = 361^2 = 321\)
\(17^{128} = 321^2 = 41\)
ora, \(169 = 2^0 + 2^3 + 2^5 + 2^7\) perciò
\(17^{169} = 17^1 \cdot 17^8 \cdot 17^{32} \cdot 17^{128} = 17 \cdot 441 \cdot 361 \cdot 41 = 497 \cdot 801 = 97\)
è molto bovino come conteggio ma se hai pazienza è fattibile.
\(17^1 = 17\)
\(17^2 = (10+7)^2 = 289\)
\(17^4 = 289^2 = 521\)
\(17^8 = 521^2 = 441\)
\(17^{16} = 441^2 = 481\)
\(17^{32} = 481^2 = 361\)
\(17^{64} = 361^2 = 321\)
\(17^{128} = 321^2 = 41\)
ora, \(169 = 2^0 + 2^3 + 2^5 + 2^7\) perciò
\(17^{169} = 17^1 \cdot 17^8 \cdot 17^{32} \cdot 17^{128} = 17 \cdot 441 \cdot 361 \cdot 41 = 497 \cdot 801 = 97\)
è molto bovino come conteggio ma se hai pazienza è fattibile.
"Zero87":
fai meno calcoli ma comunque i calcoli ce li hai lo stesso.
Si, come idea ha senso, però era il calcolo che dovevo sbrogliare in un modo più facile
"vlander":
è molto bovino come conteggio ma se hai pazienza è fattibile.
Bestia
il metodo è piuttosto crudele e soprattutto richiede una calcolatrice
, però effettivamente funziona a dovere per lo sporco lavoro che deve fare. Mi sa che lo imparerò nel caso serva... In ogni caso, grazie ad entrambi per la soluzione ed i preziosi consigli
Si potrebbe anche osservare che $1000=8\times 125$ e usare il teorema cinese del resto.
A mano:
Poiche’ $17\equiv 1$ mod $8$, abbiamo che $17^{169}=1$ mod $8$.
Per calcolare $17^{169}$ mod $125$ osserviamo prima che $\phi(125)=100$ e quindi
$17^{169} = 17^{69}$ mod $125$. Poiche’ $17^2=289=39=-1+40$ mod $125$ abbiamo che
$17^69=17^{1+2\cdot 34}=17\cdot(-1+40)^{34}$ mod $125$
Usando il binomio di Newton questo e’ congruo a
$17\cdot(1-40\cdot 34+40^2\cdot (34\cdot 33)/2)$ mod $125$
Per calcolare $40\cdot 34=5\cdot 8\cdot 34$ mod $125$ e' utile notare che
il risultato dipende solo dal valore di $8\cdot 34$ mod $25$.
E quindi $40\cdot 34=5\cdot -3$ mod $125$.
Similmente $40^2\cdot (34\cdot 33)/2=5^2\cdot(8^2\cdot 17\cdot 33)$ mod $125$
dipende solo dal valore di $8^2\cdot 17\cdot 33$ mod $5$.
E quindi $40^2\cdot (34\cdot 33)/2=5^2\cdot(-1)$ mod $125$.
Conclusione:
$17^{169} = 17\cdot(1+15-25)=-17\cdot 9=-153=97$ modulo $125$.
Per caso $97$ e' gia' congruo a $1$ modulo $8$. Vediamo quindi che
$17^{169} =97$ modulo $1000$.
A mano:
Poiche’ $17\equiv 1$ mod $8$, abbiamo che $17^{169}=1$ mod $8$.
Per calcolare $17^{169}$ mod $125$ osserviamo prima che $\phi(125)=100$ e quindi
$17^{169} = 17^{69}$ mod $125$. Poiche’ $17^2=289=39=-1+40$ mod $125$ abbiamo che
$17^69=17^{1+2\cdot 34}=17\cdot(-1+40)^{34}$ mod $125$
Usando il binomio di Newton questo e’ congruo a
$17\cdot(1-40\cdot 34+40^2\cdot (34\cdot 33)/2)$ mod $125$
Per calcolare $40\cdot 34=5\cdot 8\cdot 34$ mod $125$ e' utile notare che
il risultato dipende solo dal valore di $8\cdot 34$ mod $25$.
E quindi $40\cdot 34=5\cdot -3$ mod $125$.
Similmente $40^2\cdot (34\cdot 33)/2=5^2\cdot(8^2\cdot 17\cdot 33)$ mod $125$
dipende solo dal valore di $8^2\cdot 17\cdot 33$ mod $5$.
E quindi $40^2\cdot (34\cdot 33)/2=5^2\cdot(-1)$ mod $125$.
Conclusione:
$17^{169} = 17\cdot(1+15-25)=-17\cdot 9=-153=97$ modulo $125$.
Per caso $97$ e' gia' congruo a $1$ modulo $8$. Vediamo quindi che
$17^{169} =97$ modulo $1000$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo