Selezione Cortona 2001

[DamianoY]

Trovare tutte le coppie $ \left( p,q\right) $ di numeri primi tali che $ p $ divida $ 5^{q}+1 $ e $ q $ divida $ 5^{p}+1 $

Questa era la mia idea (sicuramente sarà piena di errori), ma non so come completare la dimostrazione! Accetto molto volentieri consigli di ogni tipo

Testo nascosto:

Suppongo $ p=q $
Allora $ p| 5^{p}+1 $ ma $ 5^{p}+1\equiv 6\left( mod p\right) $ allora $ p| 6\rightarrow p=2 \vee p=3 $ da quì verificando troviamo le coppie $ \left( 3,3\right), \left( 2,2\right) $

Suppongo WLOG $ p > q=2 $
quindi $ 2| 5^{p}+1 $ e $ p| 26\rightarrow p=2 \vee p=13 $ verificando ottengo che la nuova coppia $ \left( 2,13\right) $ è soluzione (analogamente $ \left( 13,2\right) $ è soluzione)

Suppongo WLOG $ p > q > 2 $
Quindi $ kq=5^{p}+1 $ ma posso scrivere anche $ jp=5^{p}+1-6 $ (perchè $ \left[ 5^{p}+1\right] _{p}\equiv \left[ 6\right] _{p} $) con $ k,j\in \mathbb{N} _{0} $
sottraendole membro a membro e riadattando ottengo $ k=\dfrac {6+jp}{q} $
Adesso analizzo i due casi:
1º Caso
$ q| j\rightarrow q| 6 $ e quindi $ q=3 $, da cui ricaviamo $ p| 126 $ e per le condizioni poste su $ p $ l'unico valore accettabile è $ p=7 $ e verificando si ricava la coppia $ \left( 3,7\right) $
(analogamente è valida la coppia $ \left( 7,3\right) $)
2º Caso
$ q $ non divide $ j $ quindi $ \left[ jp\right] _{q}\equiv \left[ -6\right] _{q } $ e quì mi fermo perchè non so come continuare...

[Drago96]

Purtroppo introducendo $ j, k $ perdi molte informazioni... in particolare ci sono infinite soluzioni di $6+jp=q $... e poi sfrutti una sola delle due condizioni...
Intanto possiamo dire ad esempio che $ p\mid 5^{2q}-1 $, quindi quale può essere l'ordine moltiplicativo di 5? Poi qual è una proprietà interessante dell'ordine?

[DamianoY]

Allora seguendo i tuoi consiglio posso dire che $ O_{p}\left( 5\right) | 2q $ poi sappiano che $ O_{p}\left( 5\right) $ divide $ \phi \left( p\right)=p-1 $ adesso mi verrebbe spontaneo di analizzare i diversi casi ma sicuramente c' è qualcosa che non ho notato... Qualche altro consiglio?

[Drago96]

Beh, $q$ è primo, quindi i casi sono ben pochi, e direi che è giusto analizzarli...
E poi, dato che la cosa è simmetrica in $p,q$ puoi decidere che vale uno tra $p\ge q$ o $q\ge p$, vedi tu quale è più comodo in questo caso

[DamianoY]

Qualcosa non mi è ancora ben chiara... Proviamo dai:
1º caso
$ O_{p}\left( 5\right) =2 $ da cui ne deriva che $ p $ è necessariamente uguale a 3 ( visto che $ 5^{2}\equiv 1 mod (p) $) e da quì deduciamo facilmente i possibili valori per $ q $ (come ho fatto prima).

2º caso
$ O_{p}\left( 5\right) =q $ allora visto che $ p|5^{q}+1 $ allora $ 1+1\equiv 0 mod(p) $ e quindi $ p=2 $ e troviamo le soluzioni dette nel primo post.

3º caso
$ O_{p}\left( 5\right) =2q $ adesso considero $ 2q|2 \times 5^{p}+2 $ (la seconda relazione moltiplicata per $ 2 $), quindi $ 2 \times 5 \times 5^{p-1}+2\equiv 0 mod(2q) $ ovvero $ 12\equiv 0mod(2q) $ e quindi ottengo di nuovo $ q=2,q=3 $

In conclusione le coppie dovrebbero essere $ \left( 2,2\right) $ $ \left( 3,3\right) $ $ \left( 2,13\right) $ $ \left( 13,2\right) $ $ \left( 3,3\right) $ $ \left( 3,7\right) $ $ \left( 7,3\right) $

È corretto? Come faccio ad essere sicuro che non esistano altre soluzioni?

[DamianoY]

Scusate per l'insistenza ... Qualcuno saprebbe dirmi se i miei procedimenti sono corretti o propormi altre soluzione (ancora ho qualche dubbio infatti)?
Grazie in anticipo

[karlosson_sul_tetto]

Prima di tutto direi che per formalità dovresti fare anche il caso $Ord_p(5)=1$, che porta a $p=2$ ed è facile. Sempre per essere molto pignoli, nel secondo ottieni che $25 \equiv 1 \pmod{p}$, quindi $p|24$ e può essere 2 o 3, già analizzati in precedenza (però tutte queste sono solo pignolerie xD).

Non mi è chiaro questo passaggio, potresti spiegarlo?

$2\times 5\times 5^{p−1}+2\equiv 0 \pmod{2q}$ ovvero $12\equiv 0 \pmod{2q}$

[Lasker]

@Damiano: Se vuoi confrontare, il problema è già uscito sul forum in passato qui

[DamianoY]

Prima di tutto direi che per formalità dovresti fare anche il caso $Ord_p(5)=1$, che porta a $p=2$ ed è facile. Sempre per essere molto pignoli, nel secondo ottieni che $25 \equiv 1 \pmod{p}$, quindi $p|24$ e può essere 2 o 3, già analizzati in precedenza (però tutte queste sono solo pignolerie xD).

Non mi è chiaro questo passaggio, potresti spiegarlo?

$2\times 5\times 5^{p−1}+2\equiv 0 \pmod{2q}$ ovvero $12\equiv 0 \pmod{2q}$

Che figuraccia... Credo di aver fatto un errore che nemmeno sto a dire... Domani ricontrollo e provo a riaggiustare quest' ultimo punto!

Grazie mille per tutte le puntualizzazioni

[DamianoY]

Vi prego di correggermi minuziosamente
Spero di non scrivere cavolate... Adesso rifarò il terzo caso:

Sappiamo che $ O_{p}\left( 5\right) =2q $ ovvero $ 5^{2q}\equiv 1 mod\left( p\right) $ e per la prima condizione sappiamo anche che $ -5^{q}\equiv 1 mod\left( p\right) $ quindi $ 5^{2q}\equiv -5^{q} mod\left( p\right) $ ovvero $ 24\equiv 0 mod\left( p\right) $ da cui deduciamo appunto che $ p=2 $ o $ p=3 $

Adesso penso di aver fatto tutto... Va bene?

[DamianoY]

@Damiano: Se vuoi confrontare, il problema è già uscito sul forum in passato qui

Non capisco perchè conclude il terzo caso facendo quelle considerazioni su $ p $ e $ q $ arrivando ad un assurdo...
Cioè quello che mi chiedevo (forse per voi sarà una banalità): è scontato che se $ O_{p} \left( 5\right) =2q $ allora deve valere anche $ O_{q} \left( 5\right) =2p $ ?

[karlosson_sul_tetto]

Questo fatto è dovuto alla simmetria, nella dimostrazione salta un passaggio.
In pratica, dividi in tanti casi (li scrivo tutti per chiarezza):
1) $ord_p(5)=1$ e $ord_q(5)=1$
2) $ord_p(5)=1$ e $ord_q(5)=2$
3) $ord_p(5)=1$ e $ord_q(5)=p$
4) $ord_p(5)=1$ e $ord_q(5)=2p$
5) $ord_p(5)=2$ e $ord_q(5)=1$
6) $ord_p(5)=2$ e $ord_q(5)=2$
7) $ord_p(5)=2$ e $ord_q(5)=p$
8 ) $ord_p(5)=2$ e $ord_q(5)=2p$
9) $ord_p(5)=q$ e $ord_q(5)=1$
10) $ord_p(5)=q$ e $ord_q(5)=2$
11) $ord_p(5)=q$ e $ord_q(5)=p$
12) $ord_p(5)=q$ e $ord_q(5)=2p$
13) $ord_p(5)=2q$ e $ord_q(5)=1$
14) $ord_p(5)=2q$ e $ord_q(5)=2$
15) $ord_p(5)=2q$ e $ord_q(5)=p$
16) $ord_p(5)=2q$ e $ord_q(5)=2p$

In tutti i casi dall'1 al 15, si verifica o $ord_p(5)=1$ o $ord_p(5)=2$ o $ord_p(5)=q$ (oppure una situazione analoga con p e q invertiti); tutte queste possibilità le sappiamo analizzare, quindi ci resta l'ultimo caso in cui $ord_p(5)=2q$ e $ord_q(5)=2p$.

[DamianoY]

Tutto chiarissimo, hai tolto ogni mio dubbio!
In pratica il terzo caso come ho fatto io è completante inutile (era già stato analizzato con gli altri due casi più la tua precisazione $ O_{p}(5)=1 $) mentre mi pare di aver capito che è essenziale analizzare l' ultimo caso arrivando appunto all' assurdo!