Prove all squares are congruent to 0,1 or 4 mod 8

Hi

I know this is obvious but how do you actually PROVE that all squares are congruent to either 0, 1 or 4 mod 8

i see if you write them out like
0^2 = 0 mod 8
1^2 = 1 mod 8
2^2 = 4 mod 8
....1
0
1
4
1

But how do you actually prove it :confused:

Many thanks!

Reply 1

around

13

Proof by exhaustive enumeration is what you've done.

Reply 2

deepthoughts44

OP

1

Thanks for this. And I'm glad that I've done it right - but in fact I don't understand why I've done it right :frown:

. I fully appreciate the pattern continues but why is proving that the residues {0, 1, 2, 3, 4, 5, 6, 7} all square to give residues {0, 1, 4} sufficient? How could I be sure that 5389^2 wouldn't give a different remainder

Sorry as I know it's probably a ridiculous question

Reply 3

miml

17

deepthoughts44

Hi

I know this is obvious but how do you actually PROVE that all squares are congruent to either 0, 1 or 4 mod 8

i see if you write them out like
0^2 = 0 mod 8
1^2 = 1 mod 8
2^2 = 4 mod 8
....1
0
1
4
1

But how do you actually prove it :confused:

Many thanks!

This is a perfectly valid proof, if you want to tighten it up a bit just say that all numbers greater than 7 are congruent to one of {0,1,2,3,5,6,7} and therefore the squares of this number mod 8 will be congruent to a square of {0,1,2,3,4,5,6,7} mod 8.

eg 999^2 = -1^2 (mod8) = 7^2 (mod 8) = 1 (mod 8)

Reply 4

BJack

19

deepthoughts44

I fully appreciate the pattern continues but why is proving that the residues {0, 1, 2, 3, 4, 5, 6, 7} all square to give residues {0, 1, 4} sufficient? How could I be sure that 5389^2 wouldn't give a different remainder

Any integer must be congruent to 0,1,2,3,4,5,6 or 7 (mod 8). Thus its square must be congruent to 0,1,4,9,16,25,36 or 49 (mod 8), i.e. 0,1,4,1,0,1,4 or 1 (mod 8).

Reply 5

deepthoughts44

OP

1

miml

This is a perfectly valid proof, if you want to tighten it up a bit just say that all numbers greater than 7 are congruent to one of {0,1,2,3,5,6,7} and therefore the squares of this number mod 8 will be congruent to a square of {0,1,2,3,4,5,6,7} mod 8.

eg 999^2 = -1^2 (mod8) = 7^2 (mod 8) = 1 (mod 8)

Many thanks for this and especially your example! I see what you mean now!!!

Reply 6

deepthoughts44

OP

1

thank you everyone :biggrin:

Reply 7

w4rtorn

i refuse to believe you're still doing your A-levels (makes me feel better if i do that)

Reply 8

ExpiredRice

1

So let us take two numbers a and a + 1. When you square them, the difference between their squares is 2a + 1. (a^2 + 2a + 1 - a^2).

We observe that 0^2 is congruent to 0 mod 8.

1^2 is congruent to 1 mod 8, adding 2(0) + 1 = 1, which is congruent to 1 mod 8.

2^2 is congruent to 4 mod 8, adding 2(1) + 1 = 3, which is congruent to 3 mod 8.

3^2 is congruent to 1 mod 8, adding 2(2) + 1 = 5, which is congruent to 5 mod 8.

4^2 is congruent to 0 mod 8, adding 2(3) + 1 = 7, which is congruent to 7 mod 8.

5^2 is congruent to 1 mod 8, adding 2(4) + 1 = 9, which is congruent to 1 mod 8.

At this point, it looks like there is a pattern:

4x^2 is congruent to 0 mod 8.

(4x + 1)^2 is congruent to 1 mod 8.

(4x + 2)^2 is congruent to 4 mod 8.

(4x + 3)^2 is congruent to 1 mod 8.

. Now, let us prove that this is the case for any number n.

n^2 is congruent to x mod 8.

(n + 1)^2 is congruent to x + 2n + 1 mod 8, adding 2n + 1.

(n + 2)^2 is congruent to x + 4n + 4 mod 8, adding 2n + 3.

(n + 3)^2 is congruent to x + 6n + 1 mod 8, adding 2n + 5. (This creates x + 6n + 9 mod 8, but we remove 8 because we know x + 6n + 9 is congruent to x + 6n + 1 mod 8).

(n + 4)^2 is congruent to x mod 8, adding 2n + 7. (This creates x + 8n + 8 mod 8, but we remove 8n + 8 for the same reason).

We have just proven that n^2 is congruent to (n + 4)^2 mod 8. Therefore, the pattern holds and every number will be 0, 1 or 4 mod 8.