Negation of "...then $n$ has at least one prime factor $p$ with $1 \lt p \le \sqrt{n}$" for a proof by contradiction.

Question

This is what I'm trying to proof:

If $n$ is a positive composite number, then $n$ has at least one prime factor $p$ with $1 \lt p \le \sqrt{n}$

But I'm a bit confused about how to properly negate the conclusion so I can use contradiction. First, I realized (correct me if I'm wrong) that the conclusion can be rewritten in the form there exists... so it would read:

...there exists a prime factor p, such that $1 \lt p \le \sqrt{n}$

Then, according to Sollow's book, the negation would be something like:

for every prime factor $p$, $p\le1$ or $p\gt\sqrt{n}$

But then I wondered if, instead, it could be written like this:

for every prime number $p$, $p$ is not a factor of n, or $p\le1$ or $p\gt\sqrt{n}$

For wich I would see, first, what happens if I say $p$ is not a factor, and then use $p\le1$ or $p\gt\sqrt{n}$ in some manner.

I incline for the former, but then again, it's a bit confusing, and since I'm still learning how to do proofs (I'm self-taught) then I think this particular form of proposition can bring some valuable information for future proofs. I'd really appreciate any help. Thanks in advance.

Answer 1

A more common negation would be "..., then no prime factor of $n$ lies between $1$ and $\sqrt{n}$."

And then, since all prime factors are positive, you could rewrite that as "then all prime factors of $n$ are greater than $\sqrt{n}$. "

And that's a form where it's particularly easy to reach the conclusion you want (i.e., contradiction). For if $n$ is composite, then it has at least two prime factors (possible equal).

Answer 2

If the theorem you are trying to prove is stated as

If $n$ is a positive composite integer, then it has at least one prime factor $p$ satisfying $1\lt p\le \sqrt{n}$.

we can rephrase it as

$\forall n\in\mathbb Z^+, n \text{ composite}, \exists p \text{ a prime factor of } n \text{ such that } 1\lt p\le \sqrt{n}.$

and the negation is

$\exists n\in\mathbb Z^+, n \text{ composite}, \nexists p \text{ a prime factor of } n \text{ such that } 1\lt p\le \sqrt{n}.$

or

There exists a positive composite integer $n$ with no prime factor $p$ satisfying $1\lt p\le \sqrt{n}$.

If you want to use a proof by contradiction, assume that this statement is true and consider a positive composite integer $n$ with no prime factors $p$ satisfying $1\lt p \le \sqrt{n}$, and try to derive a contradiction from that. If this gives you a contradiction, you may reject the negation of the original statement and conclude that the original statement is true.