Numeri primi

[HowardRoark]

Mi sono riletto la dimostrazione sul perché i numeri primi siano infiniti, e volevo giocarci un po' per prenderci confidenza. A questo scopo, ho considerato: $p=2*3*5*7*11*13*17*19+1=9699961$, e siccome ho letto la regoletta secondo cui per stabilire se un numero è primo basta considerare i numeri primi minori o uguali di $sqrt(p)$, che in questo caso è circa $3114$, per stabilire se questo numero sia a sua volta primo dovrei dividerlo per tutti i numeri primi $<3114$. Mi sembra un metodo molto noioso ed inefficiente...
Comunque, in generale se considero $n= 2*3*...*p+1$, dove $2,3...,p$ sono tutti numeri primi, non è detto che a sua volta $n$ sia primo: potrebbero esserci divisori primi tali che $p<d<=n$, indicando ovviamente con $d$ questi divisori primi ($d=n$ se il numero ottenuto con questa procedura è primo).
Quindi, potrebbe essere interessante capire se il numero così ottenuto sia a sua volta primo o almeno trovare questi numeri primi maggiori di $p$: è possibile farlo agevolmente?

[HowardRoark]

e siccome ho letto la regoletta secondo cui per stabilire se un numero è primo basta considerare i numeri primi minori o uguali di $ sqrt(p) $

Ho anche un'altra domanda: il fatto che per capire se un numero $n$ sia primo basta cercare tra i numeri primi $<=sqrt(n)$ e vedere se risulta divisibile per uno di questi, non implica che possano esistere numeri primi maggiori di $sqrt(n)$, giusto? Implica solo che, se non esistono numeri primi $<=sqrt(n)$, allora sicuramente $n$ è primo.
Quindi si potrebbe dire che, se $n$ è divisibile per un numero primo maggiore di $sqrt(n)$, allora ha sicuramente almeno due divisori primi.

[marcokrt]

e siccome ho letto la regoletta secondo cui per stabilire se un numero è primo basta considerare i numeri primi minori o uguali di $ sqrt(p) $

Ho anche un'altra domanda: il fatto che per capire se un numero $n$ sia primo basta cercare tra i numeri primi $<=sqrt(n)$ e vedere se risulta divisibile per uno di questi, non implica che possano esistere numeri primi maggiori di $sqrt(n)$, giusto? Implica solo che, se non esistono numeri primi $<=sqrt(n)$, allora sicuramente $n$ è primo.
Quindi si potrebbe dire che, se $n$ è divisibile per un numero primo maggiore di $sqrt(n)$, allora ha sicuramente almeno due divisori primi.

Non è che si tratti di una "regoletta" così su cui possono esserci dubbi... comunque sia, per fugarli, basta una banalissima considerazione logica, ossia: prendiamo \(n=22=2 \cdot 11 \) che è dunque un numero composto; notiamo quindi che \(\sqrt{22} < 11 \) (e anzi, addirittura \( \sqrt{22}<5<\frac{11}{2} \)) che però è uno dei numeri primi che caratterizzano la fattorizzazione di \(n \).
Se non è zuppa, sarà dunque pan bagnato... e quindi abbiamo che ogni numero \(n \in \mathbb{N}-\{0,1\}\) non primo (e quindi composto) ha nella sua fattorizzazione almeno un fattore primo minore o uguale a \(n\) (attenzione, il fatto che l'uguaglianza sia non stretta non è cosa superflua... basti pensare ai quadrati perfetti \(>1\) ).

[HowardRoark]

Non è che si tratti di una "regoletta" così su cui possono esserci dubbi... comunque sia, per fugarli, basta una banalissima considerazione logica, ossia: prendiamo \(n=22=2 \cdot 11 \) che è dunque un numero composto; notiamo quindi che \(\sqrt{22} < 11 \) (e anzi, addirittura \( \sqrt{22}<5<\frac{11}{2} \)) che però è uno dei numeri primi che caratterizzano la fattorizzazione di \(n \).

Questo sembra confermare la mia regola: $2$ è primo ed è minore di $sqrt(22)$ (solo questa considerazione bastava a stabilire che $22$ non è primo), e poiché anche $11$ è un fattore primo di $22$ allora banalmente possono esistere numeri primi maggiori di $sqrt(n)$.

Se non è zuppa, sarà dunque pan bagnato... e quindi abbiamo che ogni numero \(n \in \mathbb{N}-\{0,1\}\) non primo (e quindi composto) ha nella sua fattorizzazione almeno un fattore primo minore o uguale a \(n\) (attenzione, il fatto che l'uguaglianza sia non stretta non è cosa superflua... basti pensare ai quadrati perfetti \(>1\) ).

Qui immagino intendessi dire: ogni numero non primo ha nella sua fattorizzazione almeno un fattore primo$<= sqrt(n)$. Per quanto riguarda i quadrati perfetti, $25$ ha nella sua fattorizzazione $5^2$ e quindi per alcuni di questi (in particolare per quelli la cui radice è un numero intero primo) vale l'uguaglianza, per gli altri il minore stretto.

[ghira]

Non tutti i numeri. Tutti i primi. Molto meno fatica. E ti fermi se una divisione funziona.