1

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.

Dr. Pulque
  • 13
  • 2
    Since there are no primes $≤1$ you don't need to carry that part of the contrapositive expression around. It's enough to say that the contrapositive is "there exists a composite positive number $n$ for which all the prime factors are $>\sqrt n$". – lulu Sep 01 '19 at 23:58
  • prime is redundant here, as you can say "If $n$ is a positive composite number, then $n$ has at least one factor (divisor, if you prefer) $p$ with $1<p \le \sqrt{n}$." The negation of the second part could then be: "Every factor (divisor) of $n$ is $1$ or strictly greater than $ \sqrt{n}$" – Henry Sep 02 '19 at 00:02
  • Both of your negations are correct and equivalent. When proving A or B, you can assume not A, and then prove B (in other words, A or B is the same as not A $\Rightarrow$ B). So in your context "$p$ is not a factor of $n$ or blah" is equivalent to "if $p$ is a factor of $n$, then blah". – Joel Cohen Sep 02 '19 at 00:28
  • @Henry You are certainly correct. Thanks! – Dr. Pulque Sep 02 '19 at 00:52
  • @lulu Thanks for the observation! – Dr. Pulque Sep 02 '19 at 00:53

2 Answers2

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.

Franklin Pezzuti Dyer
  • 39,754
  • 9
  • 73
  • 166
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).

John Hughes
  • 93,729