Trovare tutte le coppie di primi $(p, q)$ tali che: $p\mid 5^q+1$, $q\mid 5^p+1$
(facile, vecchio TST italiano)
141. $p\mid 5^q+1$, $q\mid 5^p+1$
141. $p\mid 5^q+1$, $q\mid 5^p+1$
Pota gnari!
Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$
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$
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)$.
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$
Esattomat94 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).
Però per avere il testimone credo che occorra darne una dimostrazione completa 
Potresti chiarirmi questi passaggi? Innanzitutto penso che intendessi $ ord_p(5) \mid (2q,p-1) $, e poi perchè $(p-1,q)=1$?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.
È esatto per qualcosa che hai detto prima, non certo perchè $ (p,q)=1 $.
Pota gnari!
Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$
Si hai ragione 
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.
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$
Ok dai, vai puremat94 ha scritto:Si hai ragione
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.
Pota gnari!
Re: 141. $p\mid 5^q+1$, $q\mid 5^p+1$
Si in realtà è dato che $p<q$ e essendo q primo allora $(p-1,q)$