OliForum Matematico

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)

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.

Eheh... hai studiato male la dimostrazione di Euclide che i numeri primi sono infiniti!

$ ~ 2\cdot 3 \cdot 5 \cdot 7 - 1 = 11 \cdot 19 $
$ ~ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 59 \cdot 509 $

L'idea è quella... ma c'è qualcosa da sistemare nel primo punto. Nel secondo è più difficile.

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.

aiutino per la seconda parte:

Lemma(da dimostrare): nessun quadrato è congruo a -1 mod(p) se p è un primo del tipo 4n+3

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...)

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...).

ehm... modulo 4, forse!

Si modulo 4...

Stoppa2006 ha scritto:Provo a dimostrare che esistono infiniti primi $ p $ con $ p \equiv -1 \bmod 4 $

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: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 $

Falso. Vista l'impostazione che hai dato al tuo proof, nessuno può escludere infatti che $ N + 1 $ sia una potenza di 2.

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).