Trovare il resto della divisione
Quali sono le ultime tre cifre del numero $271^12911$ ?
Allora ho capito che devo fare $271^12911 mod 1000$ ma non riesco a capire come procedere... un aiutino?
Allora ho capito che devo fare $271^12911 mod 1000$ ma non riesco a capire come procedere... un aiutino?
Risposte
Vogliamo calcolare:
$271^12911 -= x$ $(1000)$
Dal teorema di Eulero sappiamo che:
$x^(\phi(1000)) -= 1 (1000)$
e $\phi(1000) = \phi(10^3) = (10^(3-1))(10-1) = 900$
$=>$ $x^900 -= 1 (1000)$
$=>$ $271^12911 = 271^(14*900 + 311) -= 271^311 (1000)$
ci troviamo ora in una situazione molto più favorevole dal punto di vista computazione, ma in ogni caso non ancora ottimale
$271^12911 -= x$ $(1000)$
Dal teorema di Eulero sappiamo che:
$x^(\phi(1000)) -= 1 (1000)$
e $\phi(1000) = \phi(10^3) = (10^(3-1))(10-1) = 900$
$=>$ $x^900 -= 1 (1000)$
$=>$ $271^12911 = 271^(14*900 + 311) -= 271^311 (1000)$
ci troviamo ora in una situazione molto più favorevole dal punto di vista computazione, ma in ogni caso non ancora ottimale
Grazie mille 
fin al punto che mi hai descritto ci avevo pensato... il problema rimane nell'andare avanti per arrivare ad una soluzione
fin al punto che mi hai descritto ci avevo pensato... il problema rimane nell'andare avanti per arrivare ad una soluzione
$\phi(1000)=400$.
"Stickelberger":
$\phi(1000)=400$.
Il 900 è sbagliato? si devono prendere i due numeri primi che compongono 1000 ... vero?
è vero, scusate.
potremmo optare per un cammino diverso:
$x -= 271^12911 (1000)$
Poichè $1000 = 2^3*5^3$, applicando il teorema cinese del resto abbiamo:
$\{(x -= 271^12911 (8)),(x -= 271^12911 (125)):}$
e dato che:
$271-= -1 (8)$
$\phi(8) = \phi(2^3) = (2^(3-1))(2-1) = 4$
$12911 -= 3 (4)$
$271 -= 21 (125)$
$\phi(125) = \phi(5^3) = (5^(3-1))(5-1) = 100$
$12911 -= 11 (100)$
il sistema diventa:
$\{(x -= -1 (8)),(x -= 21^11 (125)):}$
ora bisogna trovare la soluzione del sistema
potremmo optare per un cammino diverso:
$x -= 271^12911 (1000)$
Poichè $1000 = 2^3*5^3$, applicando il teorema cinese del resto abbiamo:
$\{(x -= 271^12911 (8)),(x -= 271^12911 (125)):}$
e dato che:
$271-= -1 (8)$
$\phi(8) = \phi(2^3) = (2^(3-1))(2-1) = 4$
$12911 -= 3 (4)$
$271 -= 21 (125)$
$\phi(125) = \phi(5^3) = (5^(3-1))(5-1) = 100$
$12911 -= 11 (100)$
il sistema diventa:
$\{(x -= -1 (8)),(x -= 21^11 (125)):}$
ora bisogna trovare la soluzione del sistema
Alternativamente, si puo’ fare un calcolo "$p$-adico" con $p=10$.
Basta osservare che $270$ e’ divisibile per $10$ e quindi $270^k$ e’
divisibile per $10^3$ se $k\ge 3$. Il binomio di Newton ci da’ quindi la congruenza:
$271^{12911}=(1+270)^{12911}=1 +12911\cdot 270+ ((12911),(2))270^2$ modulo $10^3$.
Per calcolare la contribuzione $12911\cdot 270=10\ (27\cdot 12911)$ modulo $10^3$,
basta determinare $27\cdot 12911$ modulo $100$.
Si ha che $27\cdot 12911=27\cdot 11=297=-3$ modulo $100$.
E quindi $270\cdot 12911=-30$ modulo $10^3$
Similmente, si ha che $((12911),(2))270^2=500\ (27^2\cdot 12911\cdot 1291)$.
Poiche’ il numero fra parentesi e’ dispari, la seconda contribuzione e’ congruo a $500$ modulo $1000$.
E quindi
$271^{12911}=1-30+500=471$ modulo $1000$.
Basta osservare che $270$ e’ divisibile per $10$ e quindi $270^k$ e’
divisibile per $10^3$ se $k\ge 3$. Il binomio di Newton ci da’ quindi la congruenza:
$271^{12911}=(1+270)^{12911}=1 +12911\cdot 270+ ((12911),(2))270^2$ modulo $10^3$.
Per calcolare la contribuzione $12911\cdot 270=10\ (27\cdot 12911)$ modulo $10^3$,
basta determinare $27\cdot 12911$ modulo $100$.
Si ha che $27\cdot 12911=27\cdot 11=297=-3$ modulo $100$.
E quindi $270\cdot 12911=-30$ modulo $10^3$
Similmente, si ha che $((12911),(2))270^2=500\ (27^2\cdot 12911\cdot 1291)$.
Poiche’ il numero fra parentesi e’ dispari, la seconda contribuzione e’ congruo a $500$ modulo $1000$.
E quindi
$271^{12911}=1-30+500=471$ modulo $1000$.
Ok, grazie ... adesso ho capito
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo