congruenza con due primi e un'esponenziale

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Mondo
Messaggi: 65
Iscritto il: 22 dic 2007, 16:00
Contatta:

congruenza con due primi e un'esponenziale

Messaggio da Mondo » 23 dic 2008, 12:25

Siano p e q due numeri primi tali che $ q|2^p-1 $. Dimostrare che $ q \equiv 1 \;(p) $
Réver e révéler, c'est à peu prés le meme mot (R. Queneau)

Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da Fedecart » 23 dic 2008, 12:56

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

$ 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...
Ultima modifica di Fedecart il 24 dic 2008, 10:20, modificato 1 volta in totale.

Avatar utente
Haile
Messaggi: 515
Iscritto il: 30 mag 2008, 14:29
Località: Bergamo

Messaggio da Haile » 23 dic 2008, 12:59

Fedecart ha scritto:(premetto che non so fare il simbolo di congruente su Latex! :roll: )

$ 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$ $
[i]
Mathematical proofs are like diamonds: hard and clear.

[/i]

elendil
Messaggi: 78
Iscritto il: 17 lug 2008, 16:18
Località: Provincia di Pistoia

Messaggio da elendil » 23 dic 2008, 13:03

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
Messaggi: 65
Iscritto il: 22 dic 2007, 16:00
Contatta:

Messaggio da Mondo » 23 dic 2008, 13:22

da $ nq \equiv 1 (p) $ non riesci a concludere perchè $ 3 \times 5 \equiv 1 (7) $ e quindi non ti va bene...
Réver e révéler, c'est à peu prés le meme mot (R. Queneau)

Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da Fedecart » 23 dic 2008, 13:36

Mondo ha scritto: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
Messaggi: 65
Iscritto il: 22 dic 2007, 16:00
Contatta:

Messaggio da Mondo » 23 dic 2008, 23:04

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
Réver e révéler, c'est à peu prés le meme mot (R. Queneau)

Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da Fedecart » 24 dic 2008, 00:12

elendil ha scritto: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...!

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 24 dic 2008, 00:50

elendil ha scritto: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)
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da Fedecart » 24 dic 2008, 10:18

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!

Avatar utente
Ani-sama
Messaggi: 418
Iscritto il: 19 feb 2006, 21:38
Località: Antwerpen (BE)
Contatta:

Messaggio da Ani-sama » 24 dic 2008, 14:50

Fedecart ha scritto: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. :)
...

Rispondi