Dimostriamo che:
Un numero intero N non primo ha almeno un divisore che è minore o uguale della radice quadrata di N
Si ragiona per assurdo, cioè si suppone che la tesi sia falsa e dopo alcuni passaggi si cade in contraddizione. La negazione della tesi è la seguente:
(a) Esiste un numero intero non primo che non ha alcun divisore minore uguale della radice quadrata di N.
- Dire che un numero intero k è un divisore di N vuol dire che esiste un altro numero intero q tale che (b) N=k*q
- per la (a) deve essere (c) k>√N e (d) q>√N
- moltiplicando la (c) e la (d) membro a membro si ottiene (e) k*q > N
- sostituendo la (b) nella (e) si ottiene N>N che è un assurdo...infatti N non è maggiore di N!
Quindi (a) risulta falsa. Quindi è vera la sua negazione, cioè: