modulo10^3
- l'Apprendista_Stregone
- Messaggi: 106
- Iscritto il: 29 lug 2007, 00:41
Sicuro di non aver 'traslocato' qualche esponente?Juggler ha scritto:$ $2003^{2002^{2001}} \equiv (3^{(400 \cdot 5+2)})^{2001} \equiv 9^{2001} \equiv 9 \pmod{1000} $ $albert_K ha scritto: ooops...
allora arrivo solo a dire che
$ $2003^{2002^{2001}} \equiv 3^{152} \pmod{1000} $ $
[tex] wHy \matchal{ALBERT}_K ? [/tex]
Io l'ho risolto così:
$ 2003^{2002^{2001}} \equiv 3^{2002^{2001}} \equiv 3^{2^{2001}} \pmod{1000} $
E fin qua mi sembra che c'eravamo tutti. Ora ho separato i due casi modulo 8 e 125. Consideriamo prima il caso modulo 8.
$ 3^{2^{2001}} = 3^{2 \cdot 2^{2000}} = ({3^2})^{2^{2000}}} = 9^{2^{2000}} \equiv 1^{2^{2000}} \equiv 1 \pmod{8} $
Ora consideriamo il caso modulo 125.
$ \phi(125)=100 $, quindi vogliamo vedere la congruenza di $ 2^{2001} \pmod{100} $.
Separiamo nuovamente in congruenza modulo 4 e 25.
$ 2^{2001} \equiv 0 \pmod{4} $
Ovvio.
$ \phi(25)=20 $
$ 2^{2001} \equiv 2 \pmod{25} $
A questo punto per TCR troviamo facilmente $ 2^{2001} \equiv 52 \pmod{100} $.
Sappiamo quindi che $ 3^{2^{2001}} \equiv 3^{52} \pmod{125} $
Ora dovremo cercare di semplificare anche questa schifezza. Se c'è un bel modo di farlo, non l'ho trovato.
Altrimenti, provando a mano, in breve si può arrivare comunque a $ 3^{50} \equiv -1 \pmod{125} $ e quindi $ 3^{52} \equiv -9 \pmod{125} $
Da questo, applicando TCR con la congruenza modulo 8 precedentemente calcolata, si arriva a concludere che $ 2003^{2002^{2001}} \equiv 3^{2^{2001}} \equiv {241} \pmod{1000} $.
EDIT: Cancellata una mia probabile castroneria, che comunque non corrompe la dimostrazione che dovrebbe essere comunque corretta.
$ 2003^{2002^{2001}} \equiv 3^{2002^{2001}} \equiv 3^{2^{2001}} \pmod{1000} $
E fin qua mi sembra che c'eravamo tutti. Ora ho separato i due casi modulo 8 e 125. Consideriamo prima il caso modulo 8.
$ 3^{2^{2001}} = 3^{2 \cdot 2^{2000}} = ({3^2})^{2^{2000}}} = 9^{2^{2000}} \equiv 1^{2^{2000}} \equiv 1 \pmod{8} $
Ora consideriamo il caso modulo 125.
$ \phi(125)=100 $, quindi vogliamo vedere la congruenza di $ 2^{2001} \pmod{100} $.
Separiamo nuovamente in congruenza modulo 4 e 25.
$ 2^{2001} \equiv 0 \pmod{4} $
Ovvio.
$ \phi(25)=20 $
$ 2^{2001} \equiv 2 \pmod{25} $
A questo punto per TCR troviamo facilmente $ 2^{2001} \equiv 52 \pmod{100} $.
Sappiamo quindi che $ 3^{2^{2001}} \equiv 3^{52} \pmod{125} $
Ora dovremo cercare di semplificare anche questa schifezza. Se c'è un bel modo di farlo, non l'ho trovato.
Altrimenti, provando a mano, in breve si può arrivare comunque a $ 3^{50} \equiv -1 \pmod{125} $ e quindi $ 3^{52} \equiv -9 \pmod{125} $
Da questo, applicando TCR con la congruenza modulo 8 precedentemente calcolata, si arriva a concludere che $ 2003^{2002^{2001}} \equiv 3^{2^{2001}} \equiv {241} \pmod{1000} $.
EDIT: Cancellata una mia probabile castroneria, che comunque non corrompe la dimostrazione che dovrebbe essere comunque corretta.
Ultima modifica di RedII il 22 set 2007, 14:45, modificato 1 volta in totale.
Membro dell'EATO.
Ci sono 10 tipi di persone: c'è chi sa leggere il codice binario e chi no.
I nemici dell'italiano sono miei nemici.
Ci sono 10 tipi di persone: c'è chi sa leggere il codice binario e chi no.
I nemici dell'italiano sono miei nemici.
Dopo numerosi errori e ripensamenti credo di esser d'accordo sulla soluzione...dovrebbe essere 241...albert_K ha scritto:In realtà con la calcolatrice di windows si vede facilmente che 3^100 = 1 mod 1000. Quindi dovrebbe essere giusta la prima soluzione (009).
Non so invece come mi sia uscito il 3^152...
[tex] wHy \matchal{ALBERT}_K ? [/tex]
Avresti anche potuto provare che se $ 3^{100} \equiv 1 \pmod{125} $ alloraRedII ha scritto: Sappiamo quindi che $ 3^{2^{2001}} \equiv 3^{52} \pmod{125} $
Ora dovremo cercare di semplificare anche questa schifezza. Se c'è un bel modo di farlo, non l'ho trovato.
Altrimenti, provando a mano, in breve si può arrivare comunque a $ 3^{50} \equiv -1 \pmod{125} $ e quindi $ 3^{52} \equiv -9 \pmod{125} $
$ 3^{50} \equiv 1 \pmod{125} $ oppure $ 3^{50} \equiv -1 \pmod{125} $.
Poichè $ 3^4 \equiv 1 \pmod {5} $ allora $ 3^{50} \equiv (3^4)^ {12}*3^2 \pmod{5} $ e quindi $ 3^{50} \equiv -1 \pmod{5} $
Se $ 3^{50} \equiv -1 \pmod{5} $ allora $ 3^{50} \equiv -1 \pmod{125} $ per quanto detto e $ 3^{52} \equiv -9 \pmod{125} $. E poi continuare...