Un classico (caso particolare del Teorema di Dirichlet):
Dimostrare che ci sono infiniti primi del tipo 4n+3 (più semplice) e infiniti primi del tipo 4n+1 (più tosto)
infiniti primi 4n+1 e 4n+3
Per la prima parte:
Supponiamo che i primi di tale forma siano in un numero finito.
Sia ora $ P $ il prodotto di tutti i numeri primi $ \le $ del più grande di essi. Ovviamente $ P \equiv 2 \pmod{4} $. Quindi $ P+1 $ è nuovamente primo, inoltre $ P+1 \equiv 3 \pmod{4} $, contraddizione in quanto sarebbe un nuovo primo di tale forma. Ne risulta che tali primi sono infiniti.
Seconda parte:
Supponiamo finiti quelli del secondo tipo e procediamo come prima.
Analogamente, $ P-1 $ è primo, in quanto $ P-1 \equiv -1 (mod $ qualsiasi primo considerato nel prodotto $ ) $. Abbiamo ora $ P-1 \equiv 1 \pmod{4} $, contraddizione in quanto avremmo un primo in più rispetto al loro numero (finito). Anche questi sono quindi infiniti.
Supponiamo che i primi di tale forma siano in un numero finito.
Sia ora $ P $ il prodotto di tutti i numeri primi $ \le $ del più grande di essi. Ovviamente $ P \equiv 2 \pmod{4} $. Quindi $ P+1 $ è nuovamente primo, inoltre $ P+1 \equiv 3 \pmod{4} $, contraddizione in quanto sarebbe un nuovo primo di tale forma. Ne risulta che tali primi sono infiniti.
Seconda parte:
Supponiamo finiti quelli del secondo tipo e procediamo come prima.
Analogamente, $ P-1 $ è primo, in quanto $ P-1 \equiv -1 (mod $ qualsiasi primo considerato nel prodotto $ ) $. Abbiamo ora $ P-1 \equiv 1 \pmod{4} $, contraddizione in quanto avremmo un primo in più rispetto al loro numero (finito). Anche questi sono quindi infiniti.
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Cavoli è vero può non essere primo ma semplicemente divisibile per primi ancora non considerati nel prodotto 
Mannaggia, sembrava troppo facile... chiedo scusa
Tento di rimediare. Se$ P+1 \equiv 3 \pmod 4 $ allora almeno uno dei primi che lo dividono (non considerato nel prodotto, of course) dev'essere $ \equiv 3 \pmod 4 $, ma ciò sarebbe una contraddizione in quanto abbiamo ipotizzato che i primi di tale forma sono finiti.
Mannaggia, sembrava troppo facile... chiedo scusa Tento di rimediare. Se$ P+1 \equiv 3 \pmod 4 $ allora almeno uno dei primi che lo dividono (non considerato nel prodotto, of course) dev'essere $ \equiv 3 \pmod 4 $, ma ciò sarebbe una contraddizione in quanto abbiamo ipotizzato che i primi di tale forma sono finiti.
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
-
Stoppa2006
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
Scusate ma non so ancora usare il TeX...
Ho pochissimo tempo quindi dimostro solo che se -1 è un residuo quadratico modulo p allora p è congruo a 1 modulo 4:
Se -1 è un quadrato modulo p allora $ x^4 $ è congruo a 1 modulo p da cui l'ordine di x è 1,2,4 ma non può essere nè 1 nè 2 per ipotesi, allora x ha ordine 4, quindi (per Fermat... credo
) 4|p-1, da cui la tesi.
(Vale anche il viceversa ma non serve per dimostrare il problema...)
Ho pochissimo tempo quindi dimostro solo che se -1 è un residuo quadratico modulo p allora p è congruo a 1 modulo 4:
Se -1 è un quadrato modulo p allora $ x^4 $ è congruo a 1 modulo p da cui l'ordine di x è 1,2,4 ma non può essere nè 1 nè 2 per ipotesi, allora x ha ordine 4, quindi (per Fermat... credo
) 4|p-1, da cui la tesi.(Vale anche il viceversa ma non serve per dimostrare il problema...)
-
Stoppa2006
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
Provo a dimostrare che esistono infiniti primi $ p $ con:
$ p \equiv -1 \pmod p $
Supponiamo per assurdo che ne esistano un numero finito:
$ \{p_1,...,p_k\} $
e consideriamo:
$ N = (p_1...p_k)^2+1 $
Allora:
$ \forall p\in\{p_1,...,p_k\}, \ N \equiv 1 \pmod p\Rightarrow\forall q|N,\ q\equiv 3 \pmod 4 $
Ma allora poichè esiste un primo $ q $ che divide $ N $ congruo 3 modulo 4 ho che:
$ (p_1...p_k)^2\equiv-1\pmod q $
Ma questo è assurdo poichè se $ -1 $ è un quadrato modulo $ q $ primo, allora questo primo deve essere congruo a 1 modulo 4 (intervento precedente...).
$ p \equiv -1 \pmod p $
Supponiamo per assurdo che ne esistano un numero finito:
$ \{p_1,...,p_k\} $
e consideriamo:
$ N = (p_1...p_k)^2+1 $
Allora:
$ \forall p\in\{p_1,...,p_k\}, \ N \equiv 1 \pmod p\Rightarrow\forall q|N,\ q\equiv 3 \pmod 4 $
Ma allora poichè esiste un primo $ q $ che divide $ N $ congruo 3 modulo 4 ho che:
$ (p_1...p_k)^2\equiv-1\pmod q $
Ma questo è assurdo poichè se $ -1 $ è un quadrato modulo $ q $ primo, allora questo primo deve essere congruo a 1 modulo 4 (intervento precedente...).
A giudicare da quel che segue, si direbbe che le intenzioni dello scrivente (tu!?) erano di dimostrare casomai che esistono infiniti primi $ p \equiv 1 \bmod 4 $. Ho scritto 1, non -1... Non sarebbe improprio se ti decidessi di editare l'intervento incriminato. In alternativa, la santa inquisizione potrebbe anche risolversi di condannarlo al rogo.Stoppa2006 ha scritto:Provo a dimostrare che esistono infiniti primi $ p $ con $ p \equiv -1 \bmod 4 $
Falso. Vista l'impostazione che hai dato al tuo proof, nessuno può escludere infatti che $ N + 1 $ sia una potenza di 2.Stoppa2006 ha scritto:Supponiamo [...] ne esistano un numero finito $ \{p_1,...,p_k\} $ e consideriamo $ N = (p_1\ldots p_k)^2+1 $. Allora:
$ \forall p\in\{p_1,...,p_k\}, \ N \equiv 1 \bmod p\quad\Longrightarrow\quad\forall q|N,\ q\equiv 3 \bmod 4 $
Posto la mia soluzione della seconda parte:
Suppongo per assurdo che ci sia un numero finito di primi del tipo 4n+1.
Detti $ p_1,...,p_n $ tali primi, considero $ N=(p_1...p_n)^2+4 $.Si osserva facilmente $ N \equiv 1 \pmod{4} $.
Si presentano ora due casi:
-N primo ---> c'è un altro primo del tipo 4n+1 ---> ASSURDO
-N composto
Lemma 1:Se un primo q della forma 4n+3 divide $ x^2+y^2 $ allora divide sia x sia y.
Dal Lemma 1 segue che nessun primo del tipo 4n+3 divide N, perciò N è divisibile per un primo della forma 4n+1.
Ma nessun $ p_i $ divide N poichè $ N =(p_1...p_n)^2+4\equiv 4 \pmod{p_i}\neq0 $.
Perciò c'è un ulteriore primo del tipo 4n+1 ---> ASSURDO
Dimostrazione Lemma 1
Suppongo per assurdo che x non sia divisibile per q.
Allora x ammette un inverso $ i_x $ modulo q.
Per ipotesi $ x^2+y^2\equiv 0 \pmod{q} $.
Moltiplico ambo i membri dell'equazione per $ i_x^2 $ ottenendo
$ 0\equiv (x^2+y^2)i_x^2\equiv (x i_x)^2 + (i_x y)^2 \equiv 1 + (i_x y)^2 \pmod{q} $. Ma l'equazione $ (i_x y)^2 \equiv -1 \pmod{p} $ non ammette soluzione per il Lemma 2.
Lemma 2:L'equazione $ x^2 \equiv -1 \pmod{p} $ non ha soluzioni con p primo della forma 4n+3.
Dimostrazione Lemma 2
Necessariamente x non è divisibile per p.
Per il piccolo teorema di Fermat si ha $ x^{p-1} \equiv 1 \pmod{p} $.
Perciò $ -x^{p-1} \equiv x^2 \pmod{p} $.
Poichè x è primo con p ammette un inverso $ i_x $ modulo p, quindi posso moltiplicare per $ i_x^2 $ ambo i membri e ottengo
$ -1 \equiv x^{p-3} \pmod{p} $.
Sfruttando l'ipotesi p=4n+3, quindi $ -1 \equiv x^{4n}\equiv (x^2)^{2n} \pmod{p} $.
Ma per ipotesi $ x^2 \equiv -1 \pmod{p} $, quindi mettendo insieme le ultime due equazioni si ottiene $ 1 \equiv -1 \pmod{p} $, ASSURDO (infatti p>2).
Suppongo per assurdo che ci sia un numero finito di primi del tipo 4n+1.
Detti $ p_1,...,p_n $ tali primi, considero $ N=(p_1...p_n)^2+4 $.Si osserva facilmente $ N \equiv 1 \pmod{4} $.
Si presentano ora due casi:
-N primo ---> c'è un altro primo del tipo 4n+1 ---> ASSURDO
-N composto
Lemma 1:Se un primo q della forma 4n+3 divide $ x^2+y^2 $ allora divide sia x sia y.
Dal Lemma 1 segue che nessun primo del tipo 4n+3 divide N, perciò N è divisibile per un primo della forma 4n+1.
Ma nessun $ p_i $ divide N poichè $ N =(p_1...p_n)^2+4\equiv 4 \pmod{p_i}\neq0 $.
Perciò c'è un ulteriore primo del tipo 4n+1 ---> ASSURDO
Dimostrazione Lemma 1
Suppongo per assurdo che x non sia divisibile per q.
Allora x ammette un inverso $ i_x $ modulo q.
Per ipotesi $ x^2+y^2\equiv 0 \pmod{q} $.
Moltiplico ambo i membri dell'equazione per $ i_x^2 $ ottenendo
$ 0\equiv (x^2+y^2)i_x^2\equiv (x i_x)^2 + (i_x y)^2 \equiv 1 + (i_x y)^2 \pmod{q} $. Ma l'equazione $ (i_x y)^2 \equiv -1 \pmod{p} $ non ammette soluzione per il Lemma 2.
Lemma 2:L'equazione $ x^2 \equiv -1 \pmod{p} $ non ha soluzioni con p primo della forma 4n+3.
Dimostrazione Lemma 2
Necessariamente x non è divisibile per p.
Per il piccolo teorema di Fermat si ha $ x^{p-1} \equiv 1 \pmod{p} $.
Perciò $ -x^{p-1} \equiv x^2 \pmod{p} $.
Poichè x è primo con p ammette un inverso $ i_x $ modulo p, quindi posso moltiplicare per $ i_x^2 $ ambo i membri e ottengo
$ -1 \equiv x^{p-3} \pmod{p} $.
Sfruttando l'ipotesi p=4n+3, quindi $ -1 \equiv x^{4n}\equiv (x^2)^{2n} \pmod{p} $.
Ma per ipotesi $ x^2 \equiv -1 \pmod{p} $, quindi mettendo insieme le ultime due equazioni si ottiene $ 1 \equiv -1 \pmod{p} $, ASSURDO (infatti p>2).