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ò...
Mersenne 2003
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
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 $
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 $