Pagina 1 di 1

Mersenne 2003

Inviato: 30 gen 2006, 21:07
da psion_metacreativo
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ò...

Inviato: 31 gen 2006, 05:35
da ReKaio
$ 2003\equiv3 (mod \ \ 4) \ \ \land \ \ 2*2003+1=4007 $ primo $ \ \longrightarrow \ \ 4007|2^{2003}-1 $

Inviato: 31 gen 2006, 09:17
da psion_metacreativo
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?

Inviato: 31 gen 2006, 15:37
da Simo_the_wolf
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 $