Pagina 1 di 1

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

Inviato: 24 gen 2013, 14:04
da kalu
Trovare tutte le coppie di primi $(p, q)$ tali che: $p\mid 5^q+1$, $q\mid 5^p+1$
(facile, vecchio TST italiano)

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

Inviato: 24 gen 2013, 21:57
da mat94
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).

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

Inviato: 24 gen 2013, 22:26
da scambret
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)$.

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

Inviato: 24 gen 2013, 22:58
da kalu
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 $.

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

Inviato: 25 gen 2013, 08:52
da mat94
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.

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

Inviato: 25 gen 2013, 14:16
da kalu
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 :)

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

Inviato: 25 gen 2013, 20:16
da scambret
Si in realtà è dato che $p<q$ e essendo q primo allora $(p-1,q)$