problema

maths · Messaggio da **maths** » 01 gen 1970, 01:33

Voglio proporvi un problema di Cortona:
 
 Trovare tutte le coppie (p,q) di numeri primi tali che p divida (5^q + 1) e q divida (5^p + 1)
 
 Le soluzioni date sono (2,2) (2,13) (13,2) (3,3)
 
 ma io ne ho trovate altre due:
 (3,7) e (7,3)
 
 
 Voi che ne pensate?
 
 <IMG SRC="images/forum/icons/icon_wink.gif"> [ Questo Messaggio è stato Modificato da: maths il 13-04-2004 12:27 ]

jabberwocky · Messaggio da **jabberwocky** » 01 gen 1970, 01:33

che hai ragione

livingbooks · Messaggio da **livingbooks** » 01 gen 1970, 01:33

Hai ragione, ma come si dimostra che queste sono le uniche coppie?

PFR · Messaggio da **PFR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-04-12 19:44, maths wrote:
 
 Trovare tutte le coppie (p,q) di numeri primi tali che p divida (5^q + 1) e q divida (5^p + 1)
 
 Le soluzioni date sono (2,2) (2,13) (13,2) (3,3)
 
 ma io ne ho trovate altre due:
 (3,7) e (7,3)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Supponiamo che sia P maggiore o uguale a q.
 Sappiamo che 5^p=-1 mod q, da cui
 
 25^p=1 mod q.
 
 1° sottocaso: 25=1 mod q.
 In tal caso q divide 24, dunque q=2 oppure q=3.
 
 Altrimenti, se 25 fosse diverso da 1 (mod q), allora p dovrebbe essere multiplo dell\'ordine moltiplicativo di 25 (rispetto al modulo q), che (per il piccolo teorema di Fermat) è un divisore di q-1: tale ordine, in particolare, dovrebbe essere diverso da 1 e minore di p (dato che p>q-1). Ma questo non può accadere, visto che p è primo.
 
 Quindi o abbiamo q=2 oppure q=3.
 
 Se q =2, si ha che p divide 5^2+1=26, quindi P=2 oppure p=13 (e si verifica che ambedue vanno bene).
 
 Se q=3, abbiamo che p divide 5^3+1=126, quindi p=2 oppure p=3 oppure p=7. Si verifica che (3,2) non è una soluzione, mentre (3,3) e (7,3) vanno bene.
 
 Per ogni soluzione ovviamente c\'è anche la simmetrica, e quindi le troviamo tutte.
 (2,2) (2,13) (13,2) (3,3) (3,7) e (7,3).
 
 Ciao!