Understanding basic concept of prime numbers My textbook provides a theorem but I cannot understand the structure of the sentence being used. Could someone please help me understand the meaning of this theorem?

A natural number $n>1$ is prime if and only if for all primes $p\leq \sqrt{n}$, $p$ does not divide $n$.

"for all primes $p\leq \sqrt{n}$, $p$ does not divide $n$". This is the part I don't understand. The premise is that $p$ is less than the square root of $n$ then the conclusion is that $p$ does not divide $n$. So for $p$ to divide $n$ it must be greater than the square root of $n$? I'm really confused as to what information and meaning I'm supposed to see in this theorem.
 A: A positive integer $n\gt 1$ is not prime if and only if there exist positive integers $a$ and $b$, $1\lt a\lt n$, $1\lt b\lt n$, with $n=ab$.
But now notice that we cannot have both $a$ and $b$ greater than $\sqrt{n}$. Why? Because if $a\gt\sqrt{n}$ and $b\gt\sqrt{n}$, then $ab\gt\sqrt{n}\sqrt{n}=n$. But $ab$ is supposed to be equal to $n$.  And we cannot have both be strictly less than $\sqrt{n}$, because then $ab\lt\sqrt{n}\sqrt{n}=n$, again a problem.
In other words, whenever you express $n$ as a product of two positive integers, you must have one less than or equal to $\sqrt{n}$, and the other one be greater than or equal to $\sqrt{n}$.
So if you are looking for proper factors of $n$ (positive integers $a$ such that $1\lt a\lt n$ and $a$ divides $n$), you only have to look for them up to $\sqrt{n}$:  if you don't find any between $2$ and $\sqrt{n}$, then there are none to find.
Of course, because any such factor $a$ must also be the multiple of a prime $p$, $p\leq a$, in fact you only need to check the primes that are between $2$ and $\sqrt{n}$ to see whether $n$ has a proper factor. If $n$ has a proper factor, then there will be a prime between $2$ and $\sqrt{n}$ that divides $n$. If no  prime between $2$ and $\sqrt{n}$  divides $n$, then $n$ has no proper factors, so $n$ will necessarily be a prime.
That's what (one of the implications in) the theorem is telling you.
You are also misidentifying the premise and conclusion. That's because the premise is itself an implication.
The premise is:

If $p$ is a prime and $p\leq\sqrt{n}$ then $p$ does not divide $n$.

The conclusion is:

$n$ is a prime.

A: It says that, in order to see if $n$ is prime, we don't have to test divide $n$ by every prime less than $n$.  It's enough to check all primes $\leq\sqrt n$.  For example, if we want to know if $101$ is prime, it's enough to check that it's not divisible by $2,3,5,\text{ or }7$, because the next prime, $11$ is $>\sqrt{101}$.
This is because if $n=ab$, it's impossible that both $a>\sqrt n$ and $b>\sqrt n$.
A: *

*Let $n$ be a natural number.

*Suppose $n > 1$.

*n is prime if

*

*for all positive integers $p$

*where $p$ is prime

*and $p \leq \sqrt{n}$,

*$p$ does not divide $n$



*and only if

*

*for all positive integers $p$

*where $p$ is prime

*and $p \leq \sqrt{n}$,

*$p$ does not divide $n$
For instance, $17$ is prime if (and only if) all the primes in the interval $[1,\sqrt{17}]$ do not divide $17$.  The primes in the interval $[1, \sqrt{17}]$ are $2$ and $3$.  Since $2 \not\mid 17$ and $3 \not\mid 17$, $17$ is prime.
A: For a number $n>2$, if there is no prime $p$, $1 < p \leq{\sqrt{n}}$ s.t. $p | n$, then there can't be any prime $p'$,  $n > p'>\sqrt{n}$ that divides $n$. (Let's not consider the trivial divisors 1 and $n$)
Let's prove the above statement by contradiction.
Let's assume, to the contrary that there exists such a prime $p'>\sqrt{n}$, s.t. $p' | n$. It implies there exists another number $q$ s.t. $p'.q=n$, i.e., $q=\frac{n}{p'}<\sqrt{n}$.
Now, if $q$ is a prime then it's readily a contradiction, since it divides $n$, contrary to the assumption we started with.
If $q$ is not a prime then it can be written as product of smaller primes $q_1q_2...$ by the prime number theorem. All of them divides $n$ and are smaller than $q$, hence smaller than $\sqrt{n}$, leading to contradiction again.
Hence, such a $p'$ can't exist, which implies there is no prime $1<p<n$ that divides $n$, which implies $n$ is prime and it completes the proof.
