OliForum Matematico

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

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

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?

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 $