OliForum Matematico

Mmm, no, l'errore è già nella prima affermazione.
Non puoi elevare al cubo anche il modulo.
Osserva:
$ 5\equiv2\pmod3 $
Se valesse la tua regola dovrebbe essere
$ 125\equiv8\pmod{27} $
che è falsa.

Ops
Comunque poi rileggendo il post mi son accorto anche di un errore stupido nell'applicazione del piccolo di Fermat
Grazie mille
Da domani: sotto a ripetere le congruenze!

Juggler ha scritto:

albert_K ha scritto: ooops...

allora arrivo solo a dire che

$ $2003^{2002^{2001}} \equiv 3^{152} \pmod{1000} $ $

$ $2003^{2002^{2001}} \equiv (3^{(400 \cdot 5+2)})^{2001} \equiv 9^{2001} \equiv 9 \pmod{1000} $ $

Sicuro di non aver 'traslocato' qualche esponente?

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...

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.

(cancellato per i passaggi sbagliati...)

confermo il risultato, 241

@albert_K: si hai ragione ero di fretto ho visto male

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...

Dopo numerosi errori e ripensamenti credo di esser d'accordo sulla soluzione...dovrebbe essere 241...

scusate il ritardo.. ok a redII

RedII 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} $

Avresti anche potuto provare che se $ 3^{100} \equiv 1 \pmod{125} $ allora
$ 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...