4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I am not sure I understand the underlying question fully, but suffice to say that lack of proof is not disproof and lack of disproof is not proof. Trying to prove $1234567$ is not a perfect square using a modulo 3 argument does not work since $1234567\equiv 1\pmod{3}$ which puts it into the realm of "feasibly still a square or not a square." In general when approaching a problem like this, either find an argument that shows without a doubt it is a square or is not a square and if the test is inconclusive search for another test to use. $\endgroup$ – JMoravitz Mar 7 '17 at 9:15
  • $\begingroup$ If you have problem perceiving some logic, you may take an easier example to avoid unnecessary disturbance. In this situation, let's consider: Thm 1. If $x=0$ then $x\ge 0$; Thm 2. If $x=2$ then $x\le 2$. Now how would you use those two theorems to prove $-1\ne 0$ and $1\ne 0$? $\endgroup$ – Cave Johnson Mar 7 '17 at 9:19
  • 1
    $\begingroup$ The possible tests you can use for proving something is not a square is more than just modulo3 and modulo 4 tests., you could do for example a modulo 10 test: The possible final digits for square numbers are $0,1,4,5,6,9$ so if the final digit happens to be a $2,3,7,8$ we know immediately that it cannot be a square. Ironically, the modulo 10 test works for both of your example numbers to prove that they are both not squares. In general, you can design a test for modulo $n$ for any $n$ by looking at the possible values of $x^2$. $\endgroup$ – JMoravitz Mar 7 '17 at 9:19
  • 1
    $\begingroup$ @JMoravitz Thank you! I understand where my misconception lies now. I assumed we were limited to the modulo 3 and modulo 4 cases but I get that it is simply one of many tools that can be utilized to show whether a certain number is a perfect square. $\endgroup$ – sYnChris Mar 7 '17 at 9:25
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The way you wrote your contrapositive statement in the second quoteblock seems off. Recommend changing to be "If $n\neq 3q$ and $n\neq 3q+1$ for all $q$ then..." $\endgroup$ – JMoravitz Mar 7 '17 at 9:26
0
$\begingroup$

As pointed out the theorems only says that squares must fulfill these properties, but it does not say that all numbers fulfilling these properties are squares.

For example we have for $q=2$ that neither $6=3q$ nor $7=3q+1$ is a square. Similarily we have for $q=3$ that neither $12=4q$ nor $13=4q+1$ is a square.

The numbers $12$ and $13$ shows that neither of these criteria are required to work for deciding if they are squares. They both fulfill both requirements that there's an $q=4$ such that $12=3q$ or $13=3q+1$ and there's an $q=3$ such that $12=4q$ and $13=4q+1$.

The way to be guaranteed to decide is to take "integer square root". For example $\sqrt{98765432} = 9938.079895\cdots$. Maybe this isn't considered "mathematical" but we have that $9938^2 = 98763844 < 98765432 < 98783721 = 9939^2$ then one complete that for any other $r\in\mathbb N$ (than $9938$ or $9939$) we have either that $r<9938$ which means that $r^2 < 9938^2$ or $r>9939$ which means $r^2 > 9939^2$ - that is $r^2 \ne 9875432$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.