Niech n bedzie...

[Hac_mi;]

taką liczba naturalna, że \(\displaystyle{ n>1}\) i n nie jest liczbą pierwszą. Udowodnić przez zaprzeczenie, że n posiada co najmniej jeden dzielnik pierwszy p taki, że \(\displaystyle{ p \leqslant \sqrt{n}}\)

[przemk20]

niech liczb p bedzie najmniejszym z dzielnikow liczby n, wtedy
\(\displaystyle{ n = p \cdot n_1 \geq p \cdot p = p^2 \iff \ \sqrt{n} \geq p}\)

[Piotr Rutkowski]

Przez zaprzeczenie:
Załóżmy, że każdy dzielnik pierwszy jest \(\displaystyle{ p>\sqrt{n}}\)
Rozpatrzmy 2 przypadki:
-niech n będzie kwadratem liczby naturalnej, wtedy \(\displaystyle{ a^{2}=n \Rightarrow a=\sqrt{n}}\)
Jeżeli a jest liczbą pierwszą to otrzymujemy natychmiastowo sprzeczność z założeniem
Jeśli a jest liczbą złożoną, to można go przedstawić w postaci iloczynu różnych liczb pierwszych, zatem:
\(\displaystyle{ a=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{n}^{\alpha_{n}}}\) oczywiście każdy z dzielników liczby a jest \(\displaystyle{ \leq a}\) oraz jest także dzielnikiem liczby n, przez co otrzymaliśmy, że \(\displaystyle{ \exists p|n \ p\leq \sqrt{n}}\) czyli sprzeczność z założeniem
-n nie jest kwadratem liczby naturalnej
Oczywiście istnieją dzielniki liczby n, a więc istnieje taki dzielnik liczby n, że \(\displaystyle{ \exists p_{1}|n \ p_{1} > \sqrt{n}}\) (z założenia) w takim razie istnieje też dzielnik liczby n postaci \(\displaystyle{ \frac{n}{p_{1}}=a}\) skoro \(\displaystyle{ p_{1} > \sqrt{n}}\) to \(\displaystyle{ \frac{n}{p_{1}} < \sqrt{n}}\), a więc \(\displaystyle{ a < \sqrt{n}}\) korzystając znów z rozkładu na czynniki pierwsze
\(\displaystyle{ a=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{n}^{\alpha_{n}}}\) to znów \(\displaystyle{ \exists p|n \ p \leq \sqrt{n}}\).
Znów otrzymaliśmy sprzeczność z założeniem co kończy zadanie