pq|5^p+5^q

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

pq|5^p+5^q

Messaggio da mod_2 » 01 gen 2010, 13:15

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

trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo » 01 gen 2010, 16:12

Ciao spero di non dire cavolate,in caso per favore correggimi :roll:
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.

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 01 gen 2010, 16:18

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ù
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo » 01 gen 2010, 17:46

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....

trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo » 01 gen 2010, 18:41

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) ??????

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 01 gen 2010, 19:42

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 :P ). 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! :roll:
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à!"

trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo » 01 gen 2010, 20:05

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

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 01 gen 2010, 20:57

Sì mi sono perso un po' di soluzioni perché andavo di fretta e non ho fatto una premessa importante :P 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
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"

Il re
Messaggi: 8
Iscritto il: 24 nov 2009, 16:54

Messaggio da Il re » 01 gen 2010, 21:38

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..

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 01 gen 2010, 22:30

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à!"

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 02 gen 2010, 00:06

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.

Avatar utente
Reginald
Messaggi: 137
Iscritto il: 24 gen 2009, 15:52
Località: Trento

Messaggio da Reginald » 02 gen 2010, 11:46

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
Ci sono due errori che si possono fare lungo la via verso la verità...non andare fino in fondo, e non iniziare.
Confucio

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 02 gen 2010, 17:55

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à è?

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 03 gen 2010, 02:09

Reginald ha scritto: o l'ordine di 5 modulo q è multiplo di 4
forse è l'orario ma non capisco come ottieni questo... :oops:
(lo so, sono pazzo a essere sul forum a quest'ora, ma vabbè)
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 03 gen 2010, 02:46

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.

Rispondi