Mersenne 2003

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Mersenne 2003

Messaggio da psion_metacreativo » 30 gen 2006, 21:07

Simpatico quesito datato almeno di 3 anni, ovvero quasi l'ultima volta che ho postato qualcosa su questo meraviglioso forum:

Dimostrare che $ M_{2003} $ è composto.

P.S.
$ M_{2003} $ è il numero di Mersenne di esponente $ 2003 $
Ovviamente è richiesta soluzione olimpica senza l'uso di computer.
Ammetto che in origine il quesito era posto diversamente ma il testo originale metteva troppo in evidenza le ipotesi necessarie, forse ora sono troppo oscure però...

ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio » 31 gen 2006, 05:35

$ 2003\equiv3 (mod \ \ 4) \ \ \land \ \ 2*2003+1=4007 $ primo $ \ \longrightarrow \ \ 4007|2^{2003}-1 $
_k_

Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo » 31 gen 2006, 09:17

ovviamente giusto Kaio, e in generale vale:

Se $ p\equiv3\ (mod\ 4) $ e $ 2p+1 $ è primo allora $ M_{p} $ è composto e in particolare $ 2p+1 | M_{p} $.

Qualche riga per giustificare tutto ciò la vogliamo spendere?

Simo_the_wolf
Moderatore
Messaggi: 1032
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 31 gen 2006, 15:37

Allora, abbiamo che se $ q $ è un primo dispari vale: $ \displaystyle \left( \frac 2q \right) = (-1)^{\frac {q^2-1}8} $ dove $ \left( \frac ab \right) $ è il simbolo di Legendre ed è 1 se $ a $ è residuo quadratico modulo $ b $ e -1 se non lo è.

Quindi se abbiamo che $ 4|p-3 $ allora $ 4|p+1 $.
ma allora $ 16|(2p+1)^2-1=4p^2+4p=4p(p+1) $ e allora $ 2| \frac {(2p+1)^2-1}8 $ e allora $ 2 $ è residuo quadratico modulo $ 2p+1 $ (Infatti avremo che $ \displaystyle \left( \frac 2{2p+1} \right) = (-1)^{\frac {{2p+1}^2-1}8}=1 $).

Quindi abbiamo che esiste un $ a $ trale che $ a^2\equiv 2 \pmod{2p+1} $ e quindi $ 2^p \equiv a^{2p} \equiv 1 \pmod {2p+1} $.

quindi $ 2p+1|2^p-1=M_p $

Rispondi