modulo10^3

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
Goldrake
Messaggi: 160
Iscritto il: 12 set 2007, 10:57

Messaggio da Goldrake » 21 set 2007, 22:52

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.

Avatar utente
l'Apprendista_Stregone
Messaggi: 106
Iscritto il: 29 lug 2007, 00:41

Messaggio da l'Apprendista_Stregone » 21 set 2007, 23:03

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!

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 22 set 2007, 01:00

Juggler ha scritto:
albert_K ha scritto::oops: :oops: 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? :shock:
[tex] wHy \matchal{ALBERT}_K ? [/tex]

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 22 set 2007, 01:40

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]

Avatar utente
RedII
Messaggi: 32
Iscritto il: 08 mag 2006, 16:45

Messaggio da RedII » 22 set 2007, 13:30

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

Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 » 22 set 2007, 14:01

(cancellato per i passaggi sbagliati...)
Ultima modifica di mod_2 il 22 set 2007, 14:17, modificato 1 volta in totale.
Appassionatamente BTA 197!

Juggler
Messaggi: 29
Iscritto il: 16 gen 2007, 15:59

Messaggio da Juggler » 22 set 2007, 14:13

confermo il risultato, 241

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

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 22 set 2007, 14:46

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...
[tex] wHy \matchal{ALBERT}_K ? [/tex]

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 24 set 2007, 10:57

scusate il ritardo.. ok a redII :)

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 24 set 2007, 15:34

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

Rispondi