141. $p\mid 5^q+1$, $q\mid 5^p+1$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da kalu » 24 gen 2013, 14:04

Trovare tutte le coppie di primi $(p, q)$ tali che: $p\mid 5^q+1$, $q\mid 5^p+1$
(facile, vecchio TST italiano)
Pota gnari!

mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da mat94 » 24 gen 2013, 21:57

Con semplici considerazioni sull'ordine di 5 modulo p e q arrivi a casi piccoli che si fanno a mano. Le soluzioni dovrebbero essere (2,2),(3,3),(2,13),(13,2),(7,3),(3,7).

scambret
Messaggi: 696
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da scambret » 24 gen 2013, 22:26

Vediamo..

Se $q=2$ allora otterrei $q \mid 26$ e $2 \mid 5^q+1$. $5^q+1 \equiv 0 \pmod 2 \forall q \geq 1$ e quindi a mano si verifica che $(2,2), (2,13) e (13,2)$ soddisfano

Se $q=5$ allora otterrei $p \mid 5^5+1$ e $5 \mid 5^p+1$, impossibile a prescindere per la seconda divisibilità!

Adesso $p=q$ e ottengo $p \mid 5^p +1$. Dato che $p \neq 5$ posso usare il piccolo teorema di fermat e ottengo $p \mid 6$ e ottengo le coppie $(2,2), (3,3)$ che soddisfano (una l'avevo già trovata).

Vabè adesso wlog suppongo $p<q$ e $p,q \neq \{2,5 \}$

Posso scrivere $p \mid 5^q +1 $ come $5^{2q} \equiv 1 \pmod p$ e quindi $ord_p (5) \mid 2q$ e inoltre $ord_p (5) \mid \varphi (p)$. Quindi $p \mid (2q,p-1)$ ma essendo già p e q coprimi allora $p-1$ e $q$ saranno ancora coprimi. E quindi $ord_p (5)= \{1, 2 \}$ e quindi $5-1 \equiv 0 \pmod p$ o $5^2 -1 \equiv 0 \pmod p$.

A questo punto (essendo $p \neq 2$), allora $p=3$

Se $p=3$ ottengo $3 \mid 5^q+1$ e $q \mid 126$. Perciò $q = 7$ (sfruttando l'ipotesi $p<q$) che soddisfa (con il piccolo teorema di fermat si abbassa presto l'esponente di $5^7+1$ e quindi anche $(3,7), (7,3)$ sono soluzioni.

Perciò le soluzioni sono $(2,2), (3,3), (2,13), (13,2), (3,7), (7,3)$.

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da kalu » 24 gen 2013, 22:58

mat94 ha scritto:Con semplici considerazioni sull'ordine di 5 modulo p e q arrivi a casi piccoli che si fanno a mano. Le soluzioni dovrebbero essere (2,2),(3,3),(2,13),(13,2),(7,3),(3,7).
Esatto :) Però per avere il testimone credo che occorra darne una dimostrazione completa :roll:
scambret ha scritto:Vediamo..
Posso scrivere $p \mid 5^q +1 $ come $5^{2q} \equiv 1 \pmod p$ e quindi $ord_p (5) \mid 2q$ e inoltre $ord_p (5) \mid \varphi (p)$. Quindi $ p \mid (2q,p-1) $ ma essendo già p e q coprimi allora $p-1$ e $q$ saranno ancora coprimi.
Potresti chiarirmi questi passaggi? Innanzitutto penso che intendessi $ ord_p(5) \mid (2q,p-1) $, e poi perchè $(p-1,q)=1$?
È esatto per qualcosa che hai detto prima, non certo perchè $ (p,q)=1 $.
Pota gnari!

mat94
Messaggi: 198
Iscritto il: 20 ago 2012, 10:29

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da mat94 » 25 gen 2013, 08:52

Si hai ragione :D
Si ha che $ 5^{2p}\equiv 1\mod q $ e che $ 5^{2q}\equiv 1\mod p $. Quindi si ha che $ ord_{q}(5)|2p $ e quindi $ ord_{q}(5)= 1,2,p$ o $2p$. Se l'ordine fosse 1 o 2 si avrebbe q=2 e q=3 da cui le soluzioni $ (2,2),(13,2),(3,3),(7,3) $ (le soluzioni simmetriche si trovano ponendo p=2 e p=3). Ora bisogna vedere quando l'ordine è p o 2p. Se l'ordine fosse p si avrebbe $1 \equiv -1 \pmod{q}$ da cui q =2 che abbiamo già trattato. Ora supponiamo che l'ordine di 5 modulo p e q sia 2q e 2p rispettivamente. Allora si ha $2p|q-1$ e $2q|p-1$ , dunque q>2p e p>2q , un assurdo.

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da kalu » 25 gen 2013, 14:16

mat94 ha scritto:Si hai ragione :D
Si ha che $ 5^{2p}\equiv 1\mod q $ e che $ 5^{2q}\equiv 1\mod p $. Quindi si ha che $ ord_{q}(5)|2p $ e quindi $ ord_{q}(5)= 1,2,p$ o $2p$. Se l'ordine fosse 1 o 2 si avrebbe q=2 e q=3 da cui le soluzioni $ (2,2),(13,2),(3,3),(7,3) $ (le soluzioni simmetriche si trovano ponendo p=2 e p=3). Ora bisogna vedere quando l'ordine è p o 2p. Se l'ordine fosse p si avrebbe $1 \equiv -1 \pmod{q}$ da cui q =2 che abbiamo già trattato. Ora supponiamo che l'ordine di 5 modulo p e q sia 2q e 2p rispettivamente. Allora si ha $2p|q-1$ e $2q|p-1$ , dunque q>2p e p>2q , un assurdo.
Ok dai, vai pure :)
Pota gnari!

scambret
Messaggi: 696
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$

Messaggio da scambret » 25 gen 2013, 20:16

Si in realtà è dato che $p<q$ e essendo q primo allora $(p-1,q)$

Rispondi