2

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.

Arturo Magidin
  • 398,050
Bobby B
  • 419
  • The statement of the theorem in your book seems to me poorly worded in at least 2 ways! Maybe more context from the book would change that appearance, but essentially, it is circular, both in the use of the word 'prime' and in how 'n' is specified, for the 'if' condition and the 'then' conclusion. If it's a textbook maybe you don't have much choice, but I'd look around for a better book...or at least an alternate way of presenting the same concept. –  Feb 19 '21 at 22:21
  • I'm using Number Theory Through Inquiry by Marshal, Odell and Starbird. This textbook doesn't offer much explanation of ideas and concepts. It simply states theorems and expects me to "figure it out on my own". Apparently this is the “Moore method” of learning. The biggest flaw of this method is that a student unable to understand a concept is never given a direct answer by the professor. I'm left to drown. But I'd love a suggestion on a better Number Theory textbook. – Bobby B Feb 19 '21 at 22:57
  • 1
    You might consider asking on this site for a number theory text recommendation: 3 I like, at different levels, all relatively older (not necessarily therefore inferior!) are, Hardy and Wright, Niven and Zuckerman, and Oystein Ore. For example, in Hardy and Wright, there is the straightforward statement about composite numbers, "If $ab = n$, then $a$ and $b$ cannot both exceed $\sqrt{n}$, which it seems was missing or not sufficiently highlighted in your text. –  Feb 20 '21 at 22:44

4 Answers4

3

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.

Arturo Magidin
  • 398,050
2

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$.

saulspatz
  • 53,131
0
  • 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.

Eric Towers
  • 67,037
0

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.

Sandipan Dey
  • 2,111