congruenza con due primi e un'esponenziale

[Mondo]

Siano p e q due numeri primi tali che $ q|2^p-1 $. Dimostrare che $ q \equiv 1 \;(p) $

[Fedecart]

(premetto che non so fare il simbolo di congruente su Latex! )

$ nq=2^p-1 $
$ nq+1=2^p $
Guardiamola ora mod p. C'è Fermat su $ 2^p $
$ nq+1\equiv2 (mod p) $
$ nq\equiv1 (mod p) $

E qui non so più che fare...

[Haile]

(premetto che non so fare il simbolo di congruente su Latex! )

$ nq=2^p-1 $
$ nq+1=2^p $
Guardiamola ora mod p. C'è Fermat su $ 2^p $
$ nq+1=2 (mod p) $
$ nq=1 (mod p) $

E qui non so più che fare...

OT

Basta passare il mouse sulla formula che ha scritto lui per visualizzarne il codice. Comunque:

Codice: Seleziona tutto

a \equiv b \mod c

$ $a \equiv b \mod c$ $

e la versione con le parentesi:

Codice: Seleziona tutto

a \equiv b \pmod c

$ $a \equiv b \pmod c$ $

[elendil]

Provo:
Se $ q|2^p-1 $ allora $ 2^p-1\equiv0\;(q)\rightarrow $ per Fermat $ p=q-1 $V$ q= minimo\;intero|q-1 $.
Nel primo caso $ q-1\equiv0\;(p)\rightarrowq\equiv1\;(p) $, nel secondo caso poichè q è dispari e p=2 e ritorna che $ q\equiv1\;(p) $

[Mondo]

da $ nq \equiv 1 (p) $ non riesci a concludere perchè $ 3 \times 5 \equiv 1 (7) $ e quindi non ti va bene...

[Fedecart]

da $ nq \equiv 1 (p) $ non riesci a concludere perchè $ 3 \times 5 \equiv 1 (7) $ e quindi non ti va bene...

Non ho capito il tuo messaggio!!

[Mondo]

dicevo solo che usando SOLO l'ultima relazione non ricavi nulla perchè sai solo che $ nq \equiv 1 (p) $ e questo non ti basta per arrivare alla tesi... Il modo giusto di procedere è quello di Elendil

[Fedecart]

Provo:
per Fermat $ p=q-1 $V$ q= minimo\;intero|q-1 $.

Non riesco a capire da questo punto in poi... Sono ancora agli inizi con le congruenze...!

[SkZ]

Provo:
Se $ q|2^p-1 $ allora $ 2^p-1\equiv0\;(q)\rightarrow $ per Fermat $ p=q-1 $V$ p= \textrm{(minimo intero)}|q-1 $.
Nel primo caso $ q-1\equiv0 \pmod{p}\rightarrow q\equiv1\pmod{p} $; nel secondo caso poichè q è dispari e p=2 si ritorna ad avere che $ q\equiv1\pmod{p} $

Federcart, solo qualche piccolo errore di scrittura
(attenzione che si puo' scrivere subito attaccato dietro ad un comando solo se e' una cifra o se e' un altro comando)

[Fedecart]

Continuo a non capire come si può passare da $ 2^p-1\equiv0 (mod q) $ a $ p=q-1 $
Che poi q e p sono dispari entrambi, quindi quell'uguaglianza non può essere vera, è in realtà una congruenza ma modulo cosa? p? q?
Mi dispiace l'ho detto sono io agli inizi!

[Ani-sama]

Continuo a non capire come si può passare da $ 2^p-1\equiv0 \pmod q $ a $ p=q-1 $[...]

Riscrivi come: $ 2^p \equiv 1 \pmod q $. C'è un fatto di... algebra, diciamo. Ogni numero, poniamo $ $a $, modulo qualcosa (poniamo $ n $) ha un "periodo" in termini moltiplicativi, cioè se tu fai le potenze di quel numero a partire da $ 0 $, prima o poi devi trovarne una (chiamala $ m $) tale che quel numero $ $a $ elevato alla $ m $ è congruo a $ $1 $ modulo $ n $. In effetti, se ci pensi, $ m $ è il più piccolo naturale tale che $ a^m \equiv 1 \pmod n $. E c'è di più: ogni naturale $ k $ tale che $ a^k \equiv 1 \pmod n $ è tale che $ m \mid k $. Tutte queste cose si dimostrano in un baleno in un contesto molto più generale fatti i rudimenti di teoria dei gruppi, ma credo proprio che esistano dimostrazioni completamente elementari. Tornando a $ 2^p \equiv 1 \pmod q $, dunque, tu puoi effettivamente concludere che, detto $ m $ il più piccolo naturale $ k $ tale che $ 2^k \equiv 1 \pmod q $, allora $ m \mid p $. Ma se usi l'ipotesi che $ p $ è primo, beh, allora puoi avere $ m=1 $ (da scartare! ogni elemento diverso da $ $1 $ ha periodo maggiore di $ $1 $) oppure $ m=p $, come effettivamente è. In sostanza, hai dimostrato che il periodo di $ 2 $ modulo $ q $ è esattamente $ p $. Ma a questo punto uno è arrivato, perché... beh, sì, c'è il piccolo teorema di Fermat! Ti dice che $ 2^{q-1} \equiv 1 \pmod q $, ma abbiamo anche dimostrato che $ p $ è proprio il periodo di $ 2 $ modulo $ q $, e per quello che si è detto sopra deve essere $ p \mid q-1 $, cioè la tesi.