E' carino e ci sono alcune idee utili dietro!
Primi e potenze di 5
Primi e potenze di 5
Trovare tutte le coppie di primi $(p, q)$ tali che $p\mid 5^q+1$ e $q\mid 5^p+1$.
E' carino e ci sono alcune idee utili dietro!
E' carino e ci sono alcune idee utili dietro!
-
iTz_CaBe_95
- Messaggi: 163
- Iscritto il: 14/03/2013, 20:27
Re: Primi e potenze di 5
Mmh, mi sto consumando da quando sono tornato da scuola su questo problemino, riesco a trovare solo le coppie (2,2) e (3,3) ahah
Qualche hint?
Qualche hint?
Re: Primi e potenze di 5
ci sono altre coppie oltre a quelle trovate (7,3) ecc. ,in pratica devi cercare di imporre che tutto sia coprimo e da li puoi provare con la phi ,pero a quel punto mi blocco e non so dirti altro,anche se suppongo sia la strada giusta.
Mi aggiungo alla richiesta hint
Mi aggiungo alla richiesta hint
Re: Primi e potenze di 5
Ci provo io...
Considero q maggiore uguale a p quindi alla fine andranno considerate anche le soluzioni simmetriche
si ha che 5^q = -1 mod p e inoltre 5^(p-1) = 1 mod p per il piccolo teorema di Fermat
essendo q primo, p-1 e q saranno comprimi per cui esistono due numeri x e y tali che qx + (p-1)y = 1 (per il teorema di Bezout)
adesso considero (5^q)^x (5^(p-1))y che sarà pari a 5 e per le congruenze trovate in precedenza sarà congruo a 1 o -1 mod p:
- se 5 = 1 mod p, si ha p=2 sostituendo q può essere uguale a 2 o a 13. Si trovano quindi le soluzioni (2;2) e (2;13) e la sua simmetrica (13;2)
- se 5 = -1 mod p, si ha p=3 sostituendo q può essere uguale a 3 o a 7. Si trovano quindi le soluzioni (3;3) e (3;7) e la sua simmetrica (7;3)
mi scuso per le formule scritte da cani ma si dovrebbe capire... la prossima volta giuro che le scriverò meglio
Considero q maggiore uguale a p quindi alla fine andranno considerate anche le soluzioni simmetriche
si ha che 5^q = -1 mod p e inoltre 5^(p-1) = 1 mod p per il piccolo teorema di Fermat
essendo q primo, p-1 e q saranno comprimi per cui esistono due numeri x e y tali che qx + (p-1)y = 1 (per il teorema di Bezout)
adesso considero (5^q)^x (5^(p-1))y che sarà pari a 5 e per le congruenze trovate in precedenza sarà congruo a 1 o -1 mod p:
- se 5 = 1 mod p, si ha p=2 sostituendo q può essere uguale a 2 o a 13. Si trovano quindi le soluzioni (2;2) e (2;13) e la sua simmetrica (13;2)
- se 5 = -1 mod p, si ha p=3 sostituendo q può essere uguale a 3 o a 7. Si trovano quindi le soluzioni (3;3) e (3;7) e la sua simmetrica (7;3)
mi scuso per le formule scritte da cani ma si dovrebbe capire... la prossima volta giuro che le scriverò meglio
Re: Primi e potenze di 5
piccolo errore di battitura...
è evidente che la quantità da considerare è (5^q)^x (5^(p-1))^y
è evidente che la quantità da considerare è (5^q)^x (5^(p-1))^y
Re: Primi e potenze di 5
per quel poco che ho letto mi paiono sballati i conti
elenco le imprecisioni che ho visto..
il teorema di fermat funziona solo con modulo e base coprima,avresti dovuto verificare che q e p siano diversi da 5
[tex]p-1[/tex] e [tex]q[/tex] non sono necessariamente coprimi, infatti se prendi [tex]p=19 \ q=3[/tex] per esempio.
elenco le imprecisioni che ho visto..
il teorema di fermat funziona solo con modulo e base coprima,avresti dovuto verificare che q e p siano diversi da 5
[tex]p-1[/tex] e [tex]q[/tex] non sono necessariamente coprimi, infatti se prendi [tex]p=19 \ q=3[/tex] per esempio.
Re: Primi e potenze di 5
Sul primo fatto sono d'accordo con te, è una specificazione che va fatta anche se nelle soluzioni che ho trovato non ci sono 5 quindi sono tutte valide
Riguardo al secondo devi tener presente che q è maggiore di p per cui quello che dico è vero
Riguardo al secondo devi tener presente che q è maggiore di p per cui quello che dico è vero
Re: Primi e potenze di 5
Ok,hai ragione,dovevo leggere anche quella parte
PS: usa il Latex per le formule,si fa col tasto "tex" in alto a destra e ci scrivi tutte le formule con qualche accorgimento
PS: usa il Latex per le formule,si fa col tasto "tex" in alto a destra e ci scrivi tutte le formule con qualche accorgimento
Re: Primi e potenze di 5
Bella l'idea di Bezout!
Io l'avevo fatto così
Supponiamo WLOG $p\le q$.
Da $p\mid 5^q+1$ otteniamo $5^{2q}\equiv1\pmod p$; ciò significa che $\text{ord}_p(5)\mid\gcd(2q,p-1)$. Ma $\gcd(2q,p-1)$ vale $1$ sse $p=2$ e vale $2$ in tutti gli altri, poichè $(q,p-1)=1$ per questioni di grandezza, e quindi rimane solo il fattore $2$.
Quindi $\text{ord}_p(5)\in\{1,2\}$, che porta alle soluzioni trovate (infatti $p\mid26$ o $p\mid6$, e quindi si trova $p$ e poi $q$ di conseguenza)
Io l'avevo fatto così
Supponiamo WLOG $p\le q$.
Da $p\mid 5^q+1$ otteniamo $5^{2q}\equiv1\pmod p$; ciò significa che $\text{ord}_p(5)\mid\gcd(2q,p-1)$. Ma $\gcd(2q,p-1)$ vale $1$ sse $p=2$ e vale $2$ in tutti gli altri, poichè $(q,p-1)=1$ per questioni di grandezza, e quindi rimane solo il fattore $2$.
Quindi $\text{ord}_p(5)\in\{1,2\}$, che porta alle soluzioni trovate (infatti $p\mid26$ o $p\mid6$, e quindi si trova $p$ e poi $q$ di conseguenza)