Problema che mi è stato affibbiato dalla squadra greca una sera ai Balkan:
Trovare tutti i primi p,q tali che $ ~ pq \mid 2^p+2^q $.
Problema degli amici greci
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Proviamoci và, pare interessante...
se $ p=2 $ allora $ q|2^q+2 $ ma $ 2^q +2 \equiv 4 \pmod{q} $ e dunque se un primo è $ 2 $ lo è anche l'altro. Quindi abbiamo come soluzione $ (p,q)=(2,2) $.
Siano ora $ p> q >2 $ (infatti se sono uguali avremo sempre $ p|4 $).
Possiamo quindi dividere per $ 2^q $ ottenendo così $ pq|2^{q-p} +1 $. Ora vediamo che se $ 2^k || q-p $ allora $ 2^{k+1} || ord_p(2) $ e $ 2^{k+1} || ord_q(2) $. Infatti abbiamo che, scrivendo $ p-q=2^k*d $ con $ d $ dispari:
$ 2^{2^k*d} \equiv -1 \pmod{p} $
$ 2^{2^{k+1}*d} \equiv 1 \pmod{p} $
Quindi $ ord_p(2) \nmid 2^k*d $ ma $ ord_p(2)| 2^{k+1}*d $ e quindi $ 2^{k+1} || ord_p(2) $. Similmente per $ q $.
Ma ora abbiamo che $ 2^p+2^q \equiv 2^p+2 \pmod{q} $ e quindi, dividendo per $ 2 $ abbiamo $ 2^{p-1} \equiv -1 \pmod{q} $. Quindi dovrebbe essere che $ 2^k || p-1 $ per gli stessi ragionamenti fatti prima. Ma poichè $ 2^{k+1}|| ord_p(2) |p-1 $ avremo $ 2^{k+1}|p-1 $ che è assurdo!!
se $ p=2 $ allora $ q|2^q+2 $ ma $ 2^q +2 \equiv 4 \pmod{q} $ e dunque se un primo è $ 2 $ lo è anche l'altro. Quindi abbiamo come soluzione $ (p,q)=(2,2) $.
Siano ora $ p> q >2 $ (infatti se sono uguali avremo sempre $ p|4 $).
Possiamo quindi dividere per $ 2^q $ ottenendo così $ pq|2^{q-p} +1 $. Ora vediamo che se $ 2^k || q-p $ allora $ 2^{k+1} || ord_p(2) $ e $ 2^{k+1} || ord_q(2) $. Infatti abbiamo che, scrivendo $ p-q=2^k*d $ con $ d $ dispari:
$ 2^{2^k*d} \equiv -1 \pmod{p} $
$ 2^{2^{k+1}*d} \equiv 1 \pmod{p} $
Quindi $ ord_p(2) \nmid 2^k*d $ ma $ ord_p(2)| 2^{k+1}*d $ e quindi $ 2^{k+1} || ord_p(2) $. Similmente per $ q $.
Ma ora abbiamo che $ 2^p+2^q \equiv 2^p+2 \pmod{q} $ e quindi, dividendo per $ 2 $ abbiamo $ 2^{p-1} \equiv -1 \pmod{q} $. Quindi dovrebbe essere che $ 2^k || p-1 $ per gli stessi ragionamenti fatti prima. Ma poichè $ 2^{k+1}|| ord_p(2) |p-1 $ avremo $ 2^{k+1}|p-1 $ che è assurdo!!
