Primi egoisti

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Nemo
Messaggi: 73
Iscritto il: 03 dic 2013, 17:35

Primi egoisti

Messaggio da Nemo » 20 apr 2014, 10:58

Trovare tutte le coppie $ (p,q) $ di primi tali che $ pq \mid p^p+q^q+1 $
[math]

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Primi egoisti

Messaggio da Triarii » 20 apr 2014, 22:59

Dimostriamo che le uniche soluzioni sono $(5,2)$,$(2,5)$
Intanto si nota per verifica diretta che $p$ e $q$ non possono essere entrambi uguali a $2$
Si noti anche la simmetria dell'espressione in $p$ e $q$. Verifico ora cosa succede se uno dei $2$ è pari. WLOG $p=2$.
Segue che $q\mid 4+1\Rightarrow q=5$. Le soluzioni sono $(5,2)$ e $(2,5)$.
Ora possiamo analizzare il caso in cui entrambe le incognite siano dispari. Si verifica facilmente che $p\ne q$.Assumiamo quindi WLOG $p>q$
Vale
$$q^q\equiv -1 \pmod p\Rightarrow \dfrac {ord_p(q)} {2} \mid q\Rightarrow ord_p(q)=2 \lor 2q$$
$$p^p\equiv -1 \pmod q\Rightarrow \dfrac {ord_q(p)} {2} \mid p\Rightarrow ord_q(p)=2 \lor 2p $$
Ma per una nota divisibilità, $ord_q(p)\mid \varphi (q)\Rightarrow ord_q(p)\le q-1$. Quindi l'unico possibilità è che $ord_q(p)=2$ (altrimenti avremmo $2p\le q-1$, assurdo)
Analizziamo ora l'altro ordine, $ord_p(q)$
Abbiamo due possibilità:
I) $ord_p(q)=2$.
Questa relazione implica che $p\mid q^2-1$, ossia $p\mid q+1 \lor p\mid q-1$
Ma entrambe le relazioni sono assurde! La seconda significa che $p\le q-1$, assurdo per l'ipotesi fatta su $p$, la prima perchè implicherebbe $p=q+1$, ma gli unici due primi consecutivi sono $2$ e $3$, possibilità che abbiamo escluso dalle prime osservazioni fatte (e che infatti non risolve il problema)
II)$ord_p(q)=2q$
Da ciò deriva (per la stessa divisibilità usata in precedenza) $2q\mid p-1\Rightarrow q\mid p-1\Rightarrow p=aq+1$ per qualche $a$ intero positivo.
Sostituendo il valore ottenuto a $p$ nell'espressione iniziale, otteniamo
$$q(aq+1)\mid q^q+(aq+1)^{aq+1}+1$$.
Ma $RHS\equiv 2 \pmod q\equiv 0 \pmod q\Rightarrow q=2$, assurdo sotto l'ipotesi di entrambi dispari (l'ultimo segno di congruenza deriva dal fatto che deve valere ciò affinche sia divisibile per LHS)
EDIT: Editato un errore
Ultima modifica di Triarii il 21 apr 2014, 11:01, modificato 1 volta in totale.
"We' Inge!"
LTE4LYF

Avatar utente
karlosson_sul_tetto
Messaggi: 1441
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Primi egoisti

Messaggio da karlosson_sul_tetto » 21 apr 2014, 10:02

Triarii ha scritto: Ma per una nota divisibilità, $ord_q(p)\mid \varphi (p)\Rightarrow ord_q(p)\le p$. Quindi l'unico possibilità è che $ord_q(p)=2$ (altrimenti avremmo $2p\le p-1$, assurdo)
Analizziamo ora l'altro ordine, $ord_p(q)$
Scusa, perché non possiamo applicare la stessa cosa a $ord_p(q)$?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Primi egoisti

Messaggio da Triarii » 21 apr 2014, 11:04

Ho sbagliato a scrivere :P
$ord_q(p)$ deve dividere $\varphi (q)$, da cui non può seguire $2p\le q-1$ per l'ipotesi $p>q$
Lo stesso ragionamento non può essere applicato a $ord_p(q)$: infatti è plausibile che $2q\le p-1$
"We' Inge!"
LTE4LYF

Rispondi