OliForum Matematico

Trovare tutte le coppie di numeri primi $ $(p,q)$ $ tali che $ $pq|5^p+5^q$ $.

Ciao spero di non dire cavolate,in caso per favore correggimi
intanto la situazione è simmetrica rispetto a p e q
analizziamo prima quindi il caso p=q

abbiamo che

2*5^p = p^2 * k con k intero

mod p abbiamo usando fermat
2*5 = 0 (mod p)
cioè 10 = 0 (mod p)
da cui le coppie (p,q) = (2,2) ; (5,5)

torniamo al caso generale

5^p + 5^q = pq*k

nel membro destro chiaramente deve comparire un multiplo di 5,ma se deve comparire in p o in q deve essere necessariamente 5,in quanto p e q sono numeri primi(il caso in cui compaia sia in p che in q l'abbiamo già esaminato)
supponiamo allora che sia p=5 (tanto per q è simmetrica la cosa)
otteniamo che
5(5^4 + 5^(q-1) ) = 5qk
5^4 + 5^(q-1) = qk
applicando ancora fermat
5^4 + 1 = 0 (mod q)
2*313 = 0(mod q)
da cui le coppie (p,q) = (5,2) ; (5,313) e simmetriche

supponiamo invece che il multiplo di 5 compaia in k
5^p + 5^q = pq*k

si vede che dividendo per 5 sempre entrambi i membri,si può procedere fino a quando il più piccolo tra 5^p e 5^q ( che supponiamo essere wlog 5^q) non diventa 1
da cui si deduce che k= a*5^q con a in N

DA FINIRE.......

Ciao

trugruo ha scritto:da cui si deduce che k= 5^q
quindi
5^p + 5^q = pq*5^q
5^(p-q) + 1 = pq
che è assurda modulo 2 tranne quando almeno uno fra p e q è = 2

attento, perchè cosi sarebbe troppo semplice. Hai solo dimostrato che $ k=5^q\cdot a $ con $ a\in\mathbb N $. Quindi il pezzo dopo non funziona più

Maioc92 ha scritto:

trugruo ha scritto:da cui si deduce che k= 5^q
quindi
5^p + 5^q = pq*5^q
5^(p-q) + 1 = pq
che è assurda modulo 2 tranne quando almeno uno fra p e q è = 2

attento, perchè cosi sarebbe troppo semplice. Hai solo dimostrato che $ k=5^q\cdot a $ con $ a\in\mathbb N $. Quindi il pezzo dopo non funziona più

Si hai ragione,grazie per la correzione....

boh è un quarto d'ora che ci penso,ma non mi viene nulla per concludere in maniera pulita quella parte,maioc tu hai qualche idea?
Più che altro avrei un dubbio:
se a^k = 1 (mod b)
allora deve essere necessariamente
a = +-1 (mod b) ??????

Trasformiamo la condizione iniziale in
$ pq | 5^p(1+5^{q-p}) $, quindi $ pq | 5^p $, cioè $ p = q = 5 $, oppure $ pq | 1 + 5^{q-p} $ (che è possibile solo per $ p \neq q $ ).
Quest'ultima condizione ha come condizione sufficiente che valgano entrambe, $ 5^{q-p} \equiv -1 \pmod{q} $ e $ 5^{p-q}\equiv -1 \pmod{p} $.
Supponiamo dapprima $ p, q, \neq 5 $.
Da fermat sappiamo che $ 5^{q-1} \equiv -5^{p-1} \equiv 1 \pmod{q} $,e che $ 5^{p-1} \equiv -5^{2p - q - 1} \equiv 1 \pmod{p} $; quindi dovrà essere $ 5^{p-1} + 1 \equiv 0 \pmod{q} $ e $ 5^{q+1} + 1 \equiv 0 \pmod{p} $.
Condizione necessaria e sufficiente affinché, per esempio, sia $ 5^{q+1} \equiv -1 \pmod{p} $ è che $ ord_p(5) $ sia pari: in tal caso (si vedano la scheda N06 di gobbino) è $ q+1 = d_1\displaystyle\frac{ord_p(5)}{2} $ con $ d_1 $ dispari. Analogamente si trova l'espressione per p-1, impostando così il sistema

$ q+1 = d_1\displaystyle\frac{ord_p(5)}{2} $
$ p-1 = d_2\displaystyle\frac{ord_q(5)}{2} $

Essendo $ p-1 = a \cdot ord_p(5) $ e $ q-1 = b \cdot ord_q(5) $ per le proprietà degli ordini moltiplicativi, sarà, sostituendo nel sistema di sopra,

$ \displaystyle\frac{d_1}{a}\displaystyle\frac{p-1}{2} = q+1 $
$ \displaystyle\frac{d_2}{b}\displaystyle\frac{q-1}{2} = p-1 $

(non so come si fa la parentesi graffa per il sistema ). Questo, risolto per esempio rispetto a q, dà
$ q = \displaystyle\frac{\frac{d_1d_2}{4ab} + 1}{\frac{d_1d_2}{4ab} -1} $. Imponendo che q sia intero e primo, si trova $ \frac{d_1d_2}{4ab} = 2 $, che dà $ q = 3 $ da questo è poi facile (magari tramite la condizione di partenza $ pq|1+5^{q-p} $) trovare che deve essere $ p=2 $ o $ p = 13 $.
Supponiamo ora che sia p = 5, allora la condizione iniziale dà $ 5q | 5^5 + 5^q $, cioè $ 5q | 5^5(1 + 5^{q-5}) $, che dà q = 5, come già detto, o $ 1+5^{q-5} \equiv 0 \pmod{q} $, che ha come soluzioni (si usi il teorema di fermat) q = 2 o q =313.
Ricapitolando, le soluzioni sono (5,5), (2, 3), (3, 13), (2,5), (5, 313) e le loro simmetriche.
Spero di non aver preso cantonate!

Gauss91 ha scritto:e di partenza $ pq|1+5^{q-p} $) trovare che deve essere $ p=2 $.
Ricapitolando, le soluzioni sono (5,5), (2, 3), (3,2).

Ciao,secondo me ti sei perso qualche soluzione ad esempio se guardi il mio topic sopra,ho trovato altre soluzioni oltre alle tue ,e le ho verificate anche con wolfram ed effettivamente sono soluzioni....
anzi se vuoi guarda se riesci continuare quella parte della mia soluzione dove c'è scritto "DA FINIRE"
le coppie a cui mi riferisco sono
2,2 5,2 5,313

ciao

Sì mi sono perso un po' di soluzioni perché andavo di fretta e non ho fatto una premessa importante Il teorema di fermat infatti posso applicarlo solo se $ p \neq 5 $. Il caso p = 5 bisogna farlo a mano. Ora edito.

P.S.: (2,2) non funziona

Gauss91 ha scritto:$ 5^{p-1} + 1 \equiv 0 \pmod{q} $ e $ 5^{q+1} + 1 \equiv 0 \pmod{p} $.

Non ho capito come le giustifichi queste..

Azz... hai ragione! E' sbagliato sostituire 0 a 2p, perché p = 0 (mod p), l'ho imparato oggi sulla mia pelle . Quindi tutto il resto salta! Però è strano che sbagliando vengano molte soluzioni, e facendo giusto neanche una... dovrebbe esserci qualche intoppo.

Io dico che la situazione è simmetrica in p e q, già nel testo.
Volendo si può vedere che $ 5^{p-q}\=-1=-1^{-1}=5^{q-p} \ \ (mod pq) $.
E quindi $ 5^{p-1}+1 $ è divisibile per q. E viceversa.
Il tuo $ q+1 $ diventa $ q-1 $.
Forse ora si aggiusta.

Ci provo anche io..anche se ho la sensazione di scrivere un mucchio di scemenze, almeno capisco dov'è l'errore...si ha che $ 5^p\equiv -5^q\pmod q $. Ora a meno che q non sia 5, posso dividere per 5 e ho $ 5^{p-1}\equiv -5^{q-1}\equiv -1\pmod q $(1). Allora ho che o $ -1\equiv 1\pmod q $ e quindi q è 2, oppure p=2, o l'ordine di 5 modulo q è multiplo di 4, quindi $ q\equiv 1\pmod 4 $ perchè la phi di un primo r è r-1 e l'ordine divide la phi. Rifacendo lo stesso lavoro su p ho $ 5^q\equiv -5^p\pmod p\to 5^{q-1}\equiv -1\pmod p $ e, a meno che p non sia 2, ho che 4 non divide l'ordine di p ma 8 sì e quindi $ p\equiv 1\pmod 8 $. Ma allora se ripesco la (1) ho che 8 non divide l'ordine di q ma sedici si, quindi $ q\equiv 1\pmod {16} $, e quindi posso rifare la stessa strada infinite volte, quindi per infiniti n si ha $ p\equiv 1\pmod {2^n} $ ma questo non può essere quindi il caso che nessuno tra p e q sia o 5 o 2 è assurdo.
Caso 1: p è 5:
ho che $ q|5^q+5^5 $ quindi o q è 5, che mi da soluzione, o $ q|5^{q-5}+1 $, oppure $ q|5^{5-q}+1 $, ma allora, se x è l'ordine di 5 modulo q, ho che $ q\equiv 1\pmod x $ per fermat e che $ 2q\equiv 10\pmod x $, ma allora $ 2\equiv 10\pmod x $ e quindi o x=1, o x=2, o x=4, o x=8. Se x=1 allora $ q|5-1 $ e quindi q=2. q=2 e p=5 è effettivamente soluzione. Se x=2 allora $ p|25-1 $ e quindi o q=2 o q=3. q=3 e p=5 non è soluzione provando. Se x=4 allora $ q|624 $ e quindi o q=2 o q=13 o q=3 . Provando q=13 e p=5 però non funziona, neppure q=3. Se x=8 allora ho $ q|5^8-1 $ e quindi o q=313, che funziona, o q=13 che non funziona, o q=2, che ho già provato prima, o q=3 che non funziona.
Caso 2:p è 2:
$ q|5^q+25 $. Se q è diverso da 5 (il caso che sia 5 lo ho contato sopra come soluzione) posso fare $ q|5^{q-2}+1 $ e quindi se x è l'ordine ho che $ 2q\equiv 4\pmod x $ e che $ q\equiv 1\pmod x $. Ma allora $ 4\equiv 2\pmod x $ e allora o x è 2, o x=1. x=2 mi dice che $ q|24 $ e allora o q=3, che mi da soluzione, o q=2, che non funge. Se x=1 ho q=2 che non va bene.
Le soluzioni, se non ho sbagliato(cosa che temo di aver fatto) sono 5;5 2;3 5;313 5;2

Gauss91 ha scritto: $ 5^{q+1} + 1 \equiv 0 \pmod{p} $.


Essendo $ p-1 = a \cdot ord_p(5) $ e $ q-1 = b \cdot ord_q(5) $ per le proprietà degli ordini moltiplicativi

perchè: $ 5^{q+1} + 1 \equiv 0 \pmod{p} $.
e quale proprietà è?

Reginald ha scritto: o l'ordine di 5 modulo q è multiplo di 4

forse è l'orario ma non capisco come ottieni questo...
(lo so, sono pazzo a essere sul forum a quest'ora, ma vabbè)

Escludo che p o q siano diversi da 5 o 2 entrambi.
$ pq|1+5^{p-q} $
Quindi
$ 5^{p-1}=5^{p-1-(q-1)}=5^{p-q}=-1 \ \ (mod\ q) $.
Viceversa:
$ 5^{q-1}=-1\ \ (mod\ p) $.

Allora valgono queste cose:
$ ord_q(5) \ non\ \ \ divide\ \ \ p-1 $
$ ord_q(5)\ |\ 2(p-1) $ perché $ 5^{2(p-1)}=(-1)^2=1\ \ (mod\ q) $.
$ ord_q(5)\ |\ q-1 $ ovviamente.

Allora:
$ v_2(q-1) \geq v_2(ord_q(5))=v_2\left[2(p-1)\right]=v_2(p-1)+1 $
Allora:
$ v_2(q-1) \geq v_2(p-1)+1 $
e simmetricamente:
$ v_2(p-1) \geq v_2(q-1)+1 $
Assurdo.