brain teaser?

Question

Take an odd integer; square it; then divide it by 8. Can the remainder be 3? Can it be 7?
Justify your answer....
HELLLPPPPPP

Answer 1

The remainder's always 1!

Reason is this.

1^2 = 1

3^2 = 9 (remainder is 1)

Every subsequent square is a multiple of 8 larger than the prior odd number square. Thus the remainder will always be 1.

5^2 - 3^2 = 16
7^2 - 5^2 = 24
and so on.

Hope that helps!

Answer 2

We can work in equivalence classes mod 8:

0² ≡ 0 mod 8
1² ≡ 1 mod 8
2² ≡ 4 mod 8
3² ≡ 1 mod 8
4² ≡ 0 mod 8
5² ≡ 1 mod 8
6² ≡ 4 mod 8
7² ≡ 1 mod 8

As you can see, ANY integer squared will have a remainder of either 0, 4, or 1 mod 8. As such, the remainder after squaring cannot be 3 or 7, nor can it be 2, 5, or 6.

If you're not familiar with modular arithmetic, consider the following: any odd integer can be written as 2k+1 with k integer. Squared, this is 4k²+4k+1. Simplified, this is 4(k² + k) + 1. Now, k is either even or odd. If it is even, then k² is even and so is k² + k. If k is odd, then so is k², and so k²+k must be even (since the sum of 2 odd numbers is even). Therefore, k²+k=2n for some integer n. Thus we have 4(2n)+1 = 8n+1, which will always have a remainder of 1 when divided by 8. Therefore, any odd integer squared will have a remainder of 1 when divided by 8, and thus cannot have a remainder of 3 or 7. Q.E.D.

Answer 3

Any odd number can be represented by 2n+1

(2n+1)^2 / 8 = m + r/8, where m is the interger part and r is the remainder.

multiply both sides by 8 to get rid of the fractions...

(2n+1)^2 = 8m + r

then expand...

4n^2 + 4n + 1 = 8m + r

4n^2 + 4n - 8m = r - 1

***** From here we test r = 3 and then r = 7.

Assume that r = 3, therefore r - 1 = 2

4n^2 + 4n - 8m = 2 (divide both sides by 4)

n^2 + n - 2m = 1/2

But n and m are integers so the result cannot be 1/2, so the assumption that r = 3 is false.


Assume that r = 7, so 7 - 1 = 6

4n^2 + 4n - 8m = 6 (divide both sides by 4)

n^2 + n - 2m = 6/4 = 3/2

Again, n and m are integers so the result cannot be 3/2 so the assumption that r = 7 is also false.

This proves by contradiction that the remainder r cannot be equal to 3 or 7.