Proof by Contradiction: Odd and Its Square

We have had several examples on proof by contradiction in this blog like irrationality of square root of 3 and the sum of root of 2 and root of 3. In this post, we will have another detailed example.

In proof by contradiction, we want to change the statement “if P then Q” to “if NOT Q then NOT P.” These two statements are equivalent, so if we can prove the latter, then we have proved the former. Consider the following theorem.

Theorem: For any integer $latex x$, if $latex x^2$ is odd, then $latex x$ is odd.

We can assign the statements above to P (the hypothesis) and Q (the conclusion) as follows.

P: $latex x^2$ is odd

Q: $latex x$ is odd.

If we are going to change this statement to “if NOT Q then NOT P,” then, we have to find the opposite of P and opposite of Q.  Continue reading

Square of Odd Numbers Minus 1

Many numbers have interesting properties worth investigating. These properties can be used to introduce the notion of proofs. Teachers may try this out in middle school or high school students. Although the proofs might not be as elegant or as formal such as written in books, its notion and the reasoning behind it is more important. Let us try to answer the question below.

Investigate the numbers which are one less than the square of odd numbers.

We can try some examples and see their properties.

$latex 3^2 – 1 = 8$

$latex 5^2 – 1 = 24$

$latex 7^2 – 1 = 48$

$latex 9^2 – 1 = 80$

Looking at the pattern, it is quite obvious that all of them are divisible by $latex 8$. Maybe, you might want to have more examples. To lessen the burden the calculation, you might want to use a spreadsheet to do this.  Continue reading

Proof of Divisibility by 8

If you have read the discussion on divisibility by 4, the proof for divisibility by 8 is somewhat similar. To know that the number is divisible by 4, we just have to look at the last two digits. In divisibility by 8, we look at the last three digits. For example, the number 10938648 is divisible by 8 because the last three digits which is 648 is divisible by 8.

Notice that number with digits $latex abcd$ can be expanded as

$latex 1000a + 100b + 10c + d$

or

$latex 10^3a + 10^2b + 10c + d$.

Now, since 1000 is divisible by 8, any multiples of 1000 are divisible by 8. Since any integer can be represented as

$latex 10^na_n + 10^{n-1}a_{n-1} + 10^{n – 2}a_{n-2} + \cdots + 10^3a_3 + 10^2a_2 + + 10^1a_1 + 10^0a_0$.

Don’t be intimidated, this is just a generalization of the decimal expansion above.

Now, all integral powers of 10 that are equal to 3 or greater are multiples of 1000, so, we only have to check

$latex 10^2a_2 + 10^1a_1 + 10^0a_0$

which is the last three digits of any positive integer.

That is the reason, why we only need to check the three digits of any integer and see if it is divisible by 8.