# Proof by contrapositive, what should I be assuming?

I am attempting to prove the following statement by proving the contrapositive.

For all natural numbers n, IF n = k * l and (k less than or equal to l) THEN k less than or equal to square root of n

I have found the contrapositive to be:

For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l

I know to prove this we must first assume the first the part to be true (that k is greater than the square root of n) and that can lead me to say that k squared is greater than n.

I am used to approaching the proof by expressing one variable in terms of another such that I can substitute the expression in for the variable in another expression. I would then solve for another variable and prove it is an integer or something like that. In this situation, how can I take the expression from one statement to sub into another if there are no equal signs involved? I do not know how to solve for an expression being not equal to another. Am I even on the right track? If I express k squared to be greater than n, how can I even move that into another equation and still keep the idea that it is greater than.

I don't understand how I can say anything about l without it being on the left side of the if/then statement. In the current iteration of the proof, I am only assuming k to be greater than the square root of n. I don't see how I can assume anything more?

Any hints on what direction I can go from here would be very appreciated.

• If $n=k\cdot l$ and $k\geq l$ then $k\leq \sqrt{n}$ is false. Take $9=9\cdot 1$ for counterexample. You have an inequality sign in the wrong direction. – JMoravitz Oct 9 '17 at 17:50
• also note that when negating $k \ge l$ the correct negation would be $k \lt l$. Maybe you wrote the first part wrong, but the negation is what's right, considering what @JMoravitz said – Francisco José Letterio Oct 9 '17 at 18:02
• You are absolutely correct, I did have an inequality in the wrong direction and have corrected that. Sorry, thank you for noticing – Kaari Landry Oct 9 '17 at 18:11
• "For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l" Another way of putting this: If $k>\sqrt{n}$ then if $n=k*l \implies k > l$. So if $n=k*l$ then $n>\sqrt{n}l$ and $l < \frac n{\sqrt{n}} = \sqrt{n} < k$. – fleablood Oct 9 '17 at 18:40

I find this easier to do when you do it in symbols.

So you have:

$$\forall n,k,l \in \mathbb{N} ((n = k\cdot l \land k \le l) \rightarrow k \le \sqrt{n})$$

Taking the contrapositive (or at least the contrapositive of the main body):

$$\forall n,k,l \in \mathbb{N} (\neg k \le \sqrt{n} \rightarrow \neg (n = k\cdot l \land k \le l))$$

which works out to:

$$\forall n,k,l \in \mathbb{N} (k > \sqrt{n} \rightarrow (\neg n = k\cdot l \lor k > l))$$

Also, since $\neg P \lor Q \Leftrightarrow P \rightarrow Q$, it might be nice to rewrite this to:

$$\forall n,k,l \in \mathbb{N} (k > \sqrt{n} \rightarrow (n = k\cdot l \rightarrow k > l))$$

And since $P \rightarrow (Q \rightarrow R) \Leftrightarrow (P \land Q) \rightarrow R$, we can also do:

$$\forall n,k,l \in \mathbb{N} ((k > \sqrt{n} \land n = k\cdot l) \rightarrow k > l)$$

which is probably the most useful format if you have to actually prove it.

• With the correction I had made to the original question, I get ∀n,k,l∈ℕ((k>n‾√∧n=k⋅l)→k>l). It follows that k^2 > k.l so l must be less than k. I see how I can formally say that now thanks for the help with my formatting! – Kaari Landry Oct 9 '17 at 18:20
• @KaariLandry OK, I updated my answer accordingly. This was easy to do exactly because of the logical formalization, which is one reason why that's a really good idea. :) – Bram28 Oct 9 '17 at 18:26
• I accepted your response as the answer because you gave me generalized rules associated with each step. This gave me a format to be able to make the proof myself rather than providing an answer – Kaari Landry Oct 9 '17 at 19:16
• @KaariLandry Glad I could help! – Bram28 Oct 9 '17 at 23:14

What you have stated is wrong, so it will be hard to prove.

You stated "For all natural numbers n, IF n = k * l and (k greater than or equal to l) THEN k less than or equal to square root of n".

However, you can always write $n = n\times 1$ and this $k$ (with $k=n$) does not satisfy the conclusion.

What is correct is

"For all natural numbers n, IF n = k * l and (k less than or equal to l) THEN k less than or equal to square root of n".

The contrapositive is

If $k > \sqrt{n}$ and $k \le l$ then $n \ne k \times l$.

The proof is easy:

Since $l \ge k > \sqrt{n}$, then $k \times l \gt \sqrt{n}\times \sqrt{n} =n$ so $k \times l \ne n$.

Note that this holds for any positive reals, not just integers.

• I have since edited the question to include that correction, sorry for the confusion. – Kaari Landry Oct 9 '17 at 18:21

"For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l"

Assume $k > \sqrt {n}$.

If $k \le l$ then $k*l > k*k >{\sqrt{n}}^2 =n$.

If $k*l = n$ then $l = \frac {n}k < \frac {n}{\sqrt n} = \sqrt n < k$.

So either $n \ne kl$ or $k> l$.