pq|5^p+5^q
pq|5^p+5^q
Trovare tutte le coppie di numeri primi $ $(p,q)$ $ tali che $ $pq|5^p+5^q$ $.
Appassionatamente BTA 197!
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
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
Ultima modifica di trugruo il 01 gen 2010, 17:47, modificato 1 volta in totale.
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ù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
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Si hai ragione,grazie per la correzione....Maioc92 ha scritto: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ù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
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!
$ 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!
Ultima modifica di Gauss91 il 01 gen 2010, 22:24, modificato 2 volte in totale.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
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....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).
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
P.S.: (2,2) non funziona
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
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.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
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
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
Ci sono due errori che si possono fare lungo la via verso la verità...non andare fino in fondo, e non iniziare.
Confucio
Confucio
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.
$ 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.