Trovare tutte le coppie $ (p,q) $ di numeri primi tali che $ p|5^q+1 $ e $ q|5^p+1 $
Invito a rispondere chi non abbia già visto la soluzione sul libro "Le olimpiadi della matematica".
Cortona 01..Soluzione mancante?
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Dunque... possiamo supporre wlog $ p \leq q $, ed inoltre sappiamo che $ 5^{2q} \equiv 1 \pmod p $, ossia che l'ordine moltiplicativo modulo p di 5 è uno tra $ \left{ 1,2,q,2q \right} $.
Se è 1, allora $ 4 \equiv 0 \pmod p $, che dà due soluzioni: $ (2,2) $ e $ (2,13) $
Se è 2, allora $ p | 24 $, ed escludendo il caso p=2 si hanno le soluzioni con p=3: $ (3,3) $ e $ (3,7) $
Se è q, allora $ -1 \equiv 5^q $ per ipotesi, ma d'altra parte $ 5^q \equiv 1 \pmod p $ per definizione di ordine moltiplicativo, perciò $ -1 \equiv 1 \pmod p \Rightarrow p=2 $, già trattato
Se infine è 2q, allora $ 2q=ord_p(5) | \varphi(p) = p-1 < p \leq q $, assurdo per "dimensioni".
Ricapitolando, dovrebbero essere solo (spero): (2,2); (2,13); (3,3); (3,7) e le loro simmetriche.
Ora, dal titolo capisco che qualcosa non torna nelle soluzioni ufficiali... cosa?
EDIT: Sono veramente stordito, è che non avevo trovato il problema nel libro... in effetti la soluzione ufficiale - che sto ancora cercando di capire - non riporta la soluzione (3,7), che però (per prova manuale!
) sembra funzionare... appena capisco la loro soluzione magari edito ancora
Ciau!
Se è 1, allora $ 4 \equiv 0 \pmod p $, che dà due soluzioni: $ (2,2) $ e $ (2,13) $
Se è 2, allora $ p | 24 $, ed escludendo il caso p=2 si hanno le soluzioni con p=3: $ (3,3) $ e $ (3,7) $
Se è q, allora $ -1 \equiv 5^q $ per ipotesi, ma d'altra parte $ 5^q \equiv 1 \pmod p $ per definizione di ordine moltiplicativo, perciò $ -1 \equiv 1 \pmod p \Rightarrow p=2 $, già trattato
Se infine è 2q, allora $ 2q=ord_p(5) | \varphi(p) = p-1 < p \leq q $, assurdo per "dimensioni".
Ricapitolando, dovrebbero essere solo (spero): (2,2); (2,13); (3,3); (3,7) e le loro simmetriche.
Ora, dal titolo capisco che qualcosa non torna nelle soluzioni ufficiali... cosa?
EDIT: Sono veramente stordito, è che non avevo trovato il problema nel libro... in effetti la soluzione ufficiale - che sto ancora cercando di capire - non riporta la soluzione (3,7), che però (per prova manuale!
) sembra funzionare... appena capisco la loro soluzione magari edito ancoraCiau!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Se non ricordo male in un passaggio sbaglia a eseguire una somma o una differenza. In ogni caso credo che g(n) specificherà meglio.
PS @ Darkcrystal: comunque il libro dovresti averlo...
EDIT: prova a guardare dove somma due fattori di un prodotto che dovrebbe essere una potenza di 5...
PS @ Darkcrystal: comunque il libro dovresti averlo...
EDIT: prova a guardare dove somma due fattori di un prodotto che dovrebbe essere una potenza di 5...
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
-
g(n)
- Messaggi: 109
- Iscritto il: 14 ott 2007, 19:24
- Località: Codroipo, il paese più anagrammato d'Italia
Esatto, nelle soluzioni ufficiali manca la soluzione (3,7) e simmetrica che in effetti funziona.
La mia soluzione è in pratica quella di darkcrystal. Ho postato il problema un po' per vedere se anche per voi l'idea più semplice fosse quella riguardo agli ordini moltiplicativi, un po' per cercare l'errore(che non ho trovato più che altro perchè non ho capito alcuni passaggi).
Appena riesco gli dedico un po' di tempo. Intanto chiunque trovi qualcosa è pregato di farsi avanti!
EDIT ho visto adesso l'edit di feddystra
Magari domani provo a vedere...Notte!
La mia soluzione è in pratica quella di darkcrystal. Ho postato il problema un po' per vedere se anche per voi l'idea più semplice fosse quella riguardo agli ordini moltiplicativi, un po' per cercare l'errore(che non ho trovato più che altro perchè non ho capito alcuni passaggi).
Appena riesco gli dedico un po' di tempo. Intanto chiunque trovi qualcosa è pregato di farsi avanti!
EDIT ho visto adesso l'edit di feddystra
Magari domani provo a vedere...Notte!