Numeri primi
Buongiorno potete dimostrarmi matematicamente che per verificare se un numero è primo o no basta verificare i divisori del numero da 2 alla radice quadrata del numero??
Risposte
Se un numero non è primo ha almeno due fattori; se entrambi fossero maggiori della radice il loro prodotto sarebbe maggiore di $"(radice quadrata)*(radice quadrata)=numero"$, mentre vogliamo che gli sia uguale.
Scusa la mia ignoranza ma non ho capito tanto bene
Pensa a 36, ogni volta che cerchi di scriverlo come prodotto di 2 fattori, uno sarà minore di 6 e l'altro maggiore.
$2*18$
$3*12$
$4*9$
$6*6$, che, però, sono uguali.
Pensa a 53, la sua radice è 7,..., se fosse possibile scriverlo come il prodotto di due fattori interi, uno sarebbe minore di 7 e l'altro maggiore.
Adesso che hai visto gli esempi, prova a rileggere l'intervento di giammaria, probabilmente ti sarà più chiaro.
$2*18$
$3*12$
$4*9$
$6*6$, che, però, sono uguali.
Pensa a 53, la sua radice è 7,..., se fosse possibile scriverlo come il prodotto di due fattori interi, uno sarebbe minore di 7 e l'altro maggiore.
Adesso che hai visto gli esempi, prova a rileggere l'intervento di giammaria, probabilmente ti sarà più chiaro.
Ciao,Battisti,e benvenuto su questo Forum!
Andiamo ad un esempio numerico,allora,e poi vediamo se riusciamo a generalizzare:
se ad esempio prendessimo in esame $31$,cosa potremmo dire dopo esserci accorti per conti immediati che non è divisibile per alcun numero naturale tra $2$ e $5$(che è la parte intera di $sqrt(31)$..)?
Beh,nulla,a parte il fatto ovvio che $31$ non ha certo divisori tra $2$ e $5$
(che poi è riscrivere con parole diverse quanto ho appena detto..
passami la ripetizione,allora,che non fà danni ma ti sarà utile
):
ma,immagino ti stia chiedendo,chi ci dice che non ci siano divisori di $31$,addirittura primi,tra $6$ e $30$?
Facciamo gli ottimisti,ed ammettiamo che ve ne è almeno uno che,con gran fantasia,indichiamo con $d$
( $>5$,abbiamo detto..);
sia allora $q$(lettera scelta con la medesima viva e vibrante immaginazione
)il quoziente tra $31$ e $d$,
o se preferisci un numero naturale tale che $31=d*q$:
a quel punto pure $q$ è divisore di $31$,con quoziente proprio $d$,
e dunque è esso stesso $>5$ perchè ci siamo appena accorti che non c'è alcun divisore di $31$ tra $2$ e $5$..
Riepilogando abbiamo dedotto,da quell'ottimistica previsione,
come ci son due naturali $d,q$ t.c. $d>=6,q>=6$ e $d*q=31$;
nessun problema,se non fosse per il particolare che dalle due disuguaglianze possiamo dedurre come $d*q>=6*6=6^2$,
ossia $31>=36$ vista l'uguaglianza:
pensi di riuscire a verificare che arrivi sempre a dedurre castronerie del genere,
ammettendo come un numero primo possa avere divisori maggiori della parte intera della sua radice quadrata ?
E se,dato un numero naturale qualunque $n$,trovassimo suoi divisori tra $2$ e la parte intera della sua radice quadrata?
Beh,semplicemente $n$ sarebbe composto ed avremmo finito:
se invece non trovassimo divisori di $n$ in quel campo ridotto di ricerca,
e per quanto detto nemmeno in quello più largo tra il successivo della parte intera di $sqrt(n)$ ed $n-1$
(altrimenti potremmo dedurre castronerie,ti ricordo..),cosa ne concluderemo?
Beh..in quel caso $n$ sarebbe privo di divisori non banali e dunque è primo:
in ogni caso,come vedi,hai una risposta certa al quesito "$n$ è primo?",
alleggerendo notevolmente la quantità di operazioni da svolgere per potervi rispondere
(meglio farlo fare all'idiota sapiente col quale ti scrivo,
anche perchè è facile infilare quest'algoritmo in un ciclo a tua scelta tra for,while e repeat until )!
La vuoi detta semplice,ora?
Se un numero naturale $n>2$ non è primo,almeno un divisore tra $2$ e la parte intera di $sqrt(n)$ lo deve avere
(altrimenti finiamo nel campo delle corbellerie,procedendo come nel caso di $31$..);
da questo deduci che,se non ha siffatti divisori,non è vero che non è primo(*):
dunque in quest'ultima evenienza sarebbe primo e,in ogni caso,prendi due piccioni con una fava spezzettatissima !
Saluti dal web.
(*)Per la serie "Se sbaglio allora significa che c'ho provato" è come dire "Se non ci provo allora non sbaglio",
almeno in Logica binaria,ma non è la stessa cosa di "Se ci provo allora sbaglio":
nella altri campi della Vita per fortuna non è così perchè la Verità è relativa e ci sono dunque tra Vero e Falso ci sono valori di Verità intermedi
(frase del tutto OT in questo contesto,
e forse "pericolosa" perchè si finisce in un campo al confine tra Filosofia e Matematica,ma m'è piaciuta troppo
)!
Andiamo ad un esempio numerico,allora,e poi vediamo se riusciamo a generalizzare:
se ad esempio prendessimo in esame $31$,cosa potremmo dire dopo esserci accorti per conti immediati che non è divisibile per alcun numero naturale tra $2$ e $5$(che è la parte intera di $sqrt(31)$..)?
Beh,nulla,a parte il fatto ovvio che $31$ non ha certo divisori tra $2$ e $5$
(che poi è riscrivere con parole diverse quanto ho appena detto..
passami la ripetizione,allora,che non fà danni ma ti sarà utile
):ma,immagino ti stia chiedendo,chi ci dice che non ci siano divisori di $31$,addirittura primi,tra $6$ e $30$?
Facciamo gli ottimisti,ed ammettiamo che ve ne è almeno uno che,con gran fantasia,indichiamo con $d$
( $>5$,abbiamo detto..);
sia allora $q$(lettera scelta con la medesima viva e vibrante immaginazione
)il quoziente tra $31$ e $d$,o se preferisci un numero naturale tale che $31=d*q$:
a quel punto pure $q$ è divisore di $31$,con quoziente proprio $d$,
e dunque è esso stesso $>5$ perchè ci siamo appena accorti che non c'è alcun divisore di $31$ tra $2$ e $5$..
Riepilogando abbiamo dedotto,da quell'ottimistica previsione,
come ci son due naturali $d,q$ t.c. $d>=6,q>=6$ e $d*q=31$;
nessun problema,se non fosse per il particolare che dalle due disuguaglianze possiamo dedurre come $d*q>=6*6=6^2$,
ossia $31>=36$ vista l'uguaglianza:
pensi di riuscire a verificare che arrivi sempre a dedurre castronerie del genere,
ammettendo come un numero primo possa avere divisori maggiori della parte intera della sua radice quadrata
?E se,dato un numero naturale qualunque $n$,trovassimo suoi divisori tra $2$ e la parte intera della sua radice quadrata?
Beh,semplicemente $n$ sarebbe composto ed avremmo finito:
se invece non trovassimo divisori di $n$ in quel campo ridotto di ricerca,
e per quanto detto nemmeno in quello più largo tra il successivo della parte intera di $sqrt(n)$ ed $n-1$
(altrimenti potremmo dedurre castronerie,ti ricordo..),cosa ne concluderemo?
Beh..in quel caso $n$ sarebbe privo di divisori non banali e dunque è primo:
in ogni caso,come vedi,hai una risposta certa al quesito "$n$ è primo?",
alleggerendo notevolmente la quantità di operazioni da svolgere per potervi rispondere
(meglio farlo fare all'idiota sapiente col quale ti scrivo,
anche perchè è facile infilare quest'algoritmo in un ciclo a tua scelta tra for,while e repeat until
)!La vuoi detta semplice,ora?
Se un numero naturale $n>2$ non è primo,almeno un divisore tra $2$ e la parte intera di $sqrt(n)$ lo deve avere
(altrimenti finiamo nel campo delle corbellerie,procedendo come nel caso di $31$..);
da questo deduci che,se non ha siffatti divisori,non è vero che non è primo(*):
dunque in quest'ultima evenienza sarebbe primo e,in ogni caso,prendi due piccioni con una fava spezzettatissima
!Saluti dal web.
(*)Per la serie "Se sbaglio allora significa che c'ho provato" è come dire "Se non ci provo allora non sbaglio",
almeno in Logica binaria,ma non è la stessa cosa di "Se ci provo allora sbaglio":
nella altri campi della Vita per fortuna non è così perchè la Verità è relativa e ci sono dunque tra Vero e Falso ci sono valori di Verità intermedi
(frase del tutto OT in questo contesto,
e forse "pericolosa" perchè si finisce in un campo al confine tra Filosofia e Matematica,ma m'è piaciuta troppo
)!
"theras":
Per la serie "Se sbaglio allora significa che c'ho provato" è come dire "Se non ci provo allora non sbaglio"
Vai alla grande!
Benvenuto al forum Battisti, voglio fare una piccola variazione sul tema riguardo alle parole di theras.
Prendi un numero naturale composto $n$ (supponiamolo $\ge 2$).
Un numero $n$ non primo - quindi composto! - puoi scriverlo sempre nella forma (anche in più modi) $n=a\cdot b$ con $a$ e $b$ naturali diversi da $1$ e $n$: se questa affermazione non ti è chiara, pensa alla definizione stessa di numero primo (che, utilizzando questa affermazione, può essere scritto solo come $1 \cdot n$ o $n\cdot 1$ che non fa differenza
).Se vuoi esempi, pensa a $30= 5 \cdot 6$ oppure sempre $30=10 \cdot 3$.
Ora, $n=a \cdot b$.
- Se $a,b$ fossero entrambi maggiori di $\sqrt(n)$, allora avremmo $a\cdot b = n >\sqrt(n) \cdot \sqrt(n) = n$, cioè $n>n$ che è impossibile
- Se $a,b$ fossero entrambi minori di $\sqrt(n)$ allora avremmo $a \cdot b = n < \sqrt(n) \cdot \sqrt(n) =n$ cioè $n
Piccolo appunto, spiego bene questa relazione (l'altra è analoga)
$a\cdot b = n >\sqrt(n) \cdot \sqrt(n) = n$, cioè $n>n$
- $a \cdot b=n$ vale per definizione di $n$ composto esprimibile come $a \cdot b$
- $a \cdot b=n > \sqrt(n) \cdot \sqrt(n)$ vale perché abbiamo supposto $a> \sqrt(n)$ e $b > \sqrt(n)$ quindi trattandosi di tutti interi positivi non abbiamo problemi nel moltiplicare i membri delle disequazioni e abbiamo $a \cdot b > \sqrt(n) \cdot \sqrt(n)$
- $\sqrt(n) \cdot \sqrt(n) = n$ nulla da aggiungere.
Pay attention.
Ho detto che "un numero $n$ non primo - quindi composto! - puoi scriverlo sempre nella forma (anche in più modi) $n=a\cdot b$ con $a$ e $b$ naturali diversi da $1$ e $n$". Questa affermazione potrebbe sembrare che contrasti con il teorema fondamentale dell'aritmetica che dice che ogni naturale si può esprimere in uno e in un solo modo nel prodotto di fattori primi (a meno dell'ordine degli stessi).
In realtà non è così: io ho solo detto che un numero composto è prodotto di altri 2 numeri (anche non primi e anche in diversi modi) mentre il teorema fondamentale dell'aritmetica, applicato ai numeri composti, mi dice che un composto è un prodotto di fattori primi (anche più di 2).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo