[Math] “Prove that 98765432 is not the square of an integer” vs “Deduce that 1234567 is not a perfect square”

discrete mathematicsproof-explanation

"Prove that 98765432 is not the square of an integer" and "Deduce that 1234567 is not a perfect square" are the two statements that my textbook (An Introduction to Mathematical Reasoning by P. Eccles) covers. However, I notice there's a contradiction when I apply their methods in a swapped manner, which I can't seem to figure out.

For simplicity, let's call the proof of the first statement, "Prove that 98765432 is not the square of an integer", Proof 1, and the proof of the second statement, "Deduce that 1234567 is not a perfect square", Proof 2.

Proving that $98765432$ is not the square of an integer:

Proof 1:
Let $n = 98765432$

Proposition 15.2.3 states, "If n is a perfect square (i.e. the square of an integer) then $n = 3q$ or $n = 3q + 1$ for some integer, $q$".

$98,765,432 = 3q + 2$ where $q = 32,921,810$

Thus, we have shown that $98765432$ is not a perfect square, by Proposition 15.2.3

$Q.E.D.$

Then, in another example problem, the book proves the statement "If n is a perfect square, then n = 4q or n = 4q + 1 for some integer, q." to be valid. Then, the author deduces that 1234567 is not a perfect square as follows:

Proof 2:
Let $n = 1234567$

$1,234,567 = 4q + 3$ where $q = 308,641$

Since $1234567$ does not equal $4q$ or $4q + 1$, it is not a perfect square.
Thus, we have deduced $1234567$ is not a perfect square.

$Q.E.D.$

I do comprehend how he used a derivation of the division theorem to prove these statements. What I can't wrap my head around is when I switch the logic used for the two proofs, I theorize that it should work the same way. However, it doesn't and I would like to know why. Moreover, when I use Proposition 15.2.3 ("If n is a perfect square (i.e. the square of an integer) then $n = 3q$ or $n = 3q + 1$ for some integer, $q$.) on the number $n = 1234567$, I get the following:

Proof 1 (revised):
Let $n = 1234567$ *Notice the "revision" is that I am using the number n from Proof 2 instead

$1,234,567 = 3q + 1$ where $q = 411,522$

Thus, we have shown that 1234567 is not a perfect square, by Proposition 15.2.3

We cannot deduce by Proposition 15.2.3 that $1,234,567$ is not the sqaure of an integer since $1,234,567 = 3q + 1$

$Q.E.D.$

Similarly, I did the same with Proof 2 as follows:

Proof 2 (revised):
Let $n = 98765432$ *Note: the revision here is this n is the n from **Proof 1 ** instead

$98,765,432 = 4q $ where $q = 308,641$

Thus, we have deduced 98765432 is not a perfect square.

Since $1234567$ does equal $4q$ or $4q + 1$, it cannot be deduced that n is a perfect square.

$Q.E.D.$

Best Answer

We know that IF $n$ is a perfect square, THEN $n=3q$ or $n=3q+1$ for some $q$. This theorem is false the other way around.

What I'm saying is, if $n$ is not a perfect square, then we can still have $n=3q$ or $n=3q+1$.

Basically it comes down to logic. "If $A$, then $B$" is not the same as "If not $A$, then not $B$", but it is the same as "If not $B$, then not $A$". If it rains, I get wet. If I get wet, it doesn't have to rain - I could be in the shower. But if I don't get wet, we know for sure that it doesn't rain.

This is why you can use the theorem

if $n$ is a perfect square, then $n=3q$ or $n=3q+1$ for some $q$.

To say

if not $n=3q$ or $n=3q+1$ for some $q$, then not $n$ is a perfect square.

which in normal words would be

if $n\neq3q$ or $n\neq3q+1$ for all $q$, then $n$ is not a perfect square.

So in your first example, $98765432$ is not of the form $98765432=3q$ and also not of the form $98765432=3q+1$, thus, it cannot be a perfect square.

Related Question