Congruenza con numero primo

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
dummy
Messaggi: 5
Iscritto il: 17 gen 2011, 19:51

Congruenza con numero primo

Messaggio da dummy »

Siccome sono una schiappa in teoria dei numeri vi pongo questo quesito:

Se $ p\equiv 3\pmod 4 $ e $ q=2p+1 $ è primo, allora se il numero $ 2^p-1 $ è composto necessariamente $ q\mid 2^p-1. $ In aggiunta dimostrate che esistono infiniti $ p $ per cui $ 2^p-1 $ è composto
paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Congruenza con numero primo

Messaggio da paga92aren »

Dato che il problema è stato postato solo 2 ore fa metto la soluzione nascosta:
SOLUZIONE:
Testo nascosto:
$q=2p+1|2^{2p}-1=(2^p-1)(2^p+1)$ e dato che $q$ è primo mi basta dimostrare che non divide il secondo fattore.
Suppongo per assurdo che $q|2^p+1$ quindi $2^p\equiv -1(q)$ e di conseguenza ord $_q(2)|2p$.
1) se l'ordine è 1 o 2 allora $4\equiv 1 (q)$ quindi $q=3$ e $p=1$ ma sapendo che $p\equiv 3 (4)$ trovo l'assurdo
2) se l'ordine è $p$ allora $2^p\equiv 1(q)$ ma sapevamo che $2^p\equiv -1(q)$ e ottengo l'assurdo.
3) l'ordine è $2p$ allora 2 è un generatore modulo $q$. Posso quindi scrivere $p=2^x$ per $x$ opportuno.

Inoltre so che $(2p+1,2^p+1)=(2^{p-1}-p,2p+1)=(2^{p-2}+p^2,2p+1)=...=(p^p-1,2p+1)$ quindi $p^p\equiv 1 (q)$, sostituendo quanto detto sopra ottengo $0\equiv 2^p+p^p \equiv 2^{px}+2^p \equiv 2^p(2^{p(x-1)}+1(q)$ sapendo che $(2,q)=1$ si ottiene che $2^{p(x-1)}\equiv -1(q)$ da cui si deduce che $x-1$ è dispari (l'ordine di 2 è $2p$) quindi $x$ è pari e $p$ residuo quadratico modulo $q$.

Essendo $(\frac{2p+1}{p})=(\frac{1}{p})=1$ e usando la reciprocità quadratica $(\frac{p}{q})(\frac{q}{p})=-1$ si ottiene che $p$ non è un residuo quadratico modulo $q$. Assurdo.
P.S: spero sia giusta, datemi conferma.
paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Congruenza con numero primo

Messaggio da paga92aren »

Dummy puoi postare un hint per la seconda parte? grazie
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Congruenza con numero primo

Messaggio da fph »

Hmm, dove hai usato che $2^p-1$ è composto? Se non l'hai usato, allora si conclude facilmente...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Congruenza con numero primo

Messaggio da <enigma> »

Ma questa sezione attira tutti i pagliacci del forum? :evil:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Congruenza con numero primo

Messaggio da Mist »

<enigma> ha scritto:Ma questa sezione attira tutti i pagliacci del forum? :evil:
parli tu, burlone !

Però sto diventando uno spammone così, che cazz... :?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Congruenza con numero primo

Messaggio da paga92aren »

fph ha scritto:Hmm, dove hai usato che $2^p-1$ è composto? Se non l'hai usato, allora si conclude facilmente...
Non ho capito l'hint: mi basta dimostrare che esistono infiniti primi tale che $2p+1$ è primo (+ congruenza) che non è per niente banale.
Oppure intendevi qualcos'altro?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Congruenza con numero primo

Messaggio da fph »

paga92aren ha scritto:
fph ha scritto:Hmm, dove hai usato che $2^p-1$ è composto? Se non l'hai usato, allora si conclude facilmente...
Non ho capito l'hint: mi basta dimostrare che esistono infiniti primi tale che $2p+1$ è primo (+ congruenza) che non è per niente banale.
Hmm, no, hai ragione tu, sorry. :(
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nabir Albar
Messaggi: 62
Iscritto il: 22 nov 2010, 19:09
Località: Sto ca... Stoccarda!

Re: Congruenza con numero primo

Messaggio da Nabir Albar »

Nessuno ha detto che $p$ deve essere primo, anche perché altrimenti la seconda parte del problema sarebbe un problema aperto :wink:
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Congruenza con numero primo

Messaggio da <enigma> »

Nabir Albar ha scritto:Nessuno ha detto che $p$ deve essere primo, anche perché altrimenti la seconda parte del problema sarebbe un problema aperto :wink:
Della serie "tanto per non confondere la notazione"... se non è primo è abbastanza banale (e c'è anche su wiki), $\{ 2^n-1\}_{n \in \mathbb N^\ast}$ è una sequenza di Mersenne.

A questo punto: trovate un ragionamento (euristico) a favore del fatto che il numero atteso di $p \leq n$ per cui $M_p$ è primo dovrebbe essere $\sim \frac {e^\gamma} {\log 2} \log n$.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Congruenza con numero primo

Messaggio da paga92aren »

@dummy ma ti smbra il caso di postare una congettura aperta?
Non conosco la fonte, ma guarda qui
Rispondi