Congruence Classes

Hello again,

SO, I was reasonably sickly this week and have accomplished very little beyond making sure I get enough sleep and food to live. As a consequence of my laziness, I didn’t come up with another fun little math problem to share this week. Fortunately, I’m taking a couple math classes this semester to draw from if I ever have an off week, so today I’m gonna draw from that pool and share a cool proof I wrote for homework.

To understand any of what I’m about to say, you’re first gonna need at least a fuzzy idea of what congruence classes are, so that’s where I’ll start:

An integer, a, is said to be congruent to another integer, b, if it can be written in the form a ⦀ b mod c [1].

For those who don’t know, the mod operator is like division, but it only returns the remainder of the two numbers. For example 4 mod 3 = 1 and 4 mod 5 = 4. Pretty simple, but as the congruence suggests, this can quickly become much more complicated. Let’s see some examples of numbers that are congruent to each other:

9 ⦀ 1 mod 8
25 ⦀ 9 mod 8
7 ⦀ -1 mod 8
8 ⦀ 0 mod 8

Very cool. Now we have this, thing…, but it’s pretty unclear what it means and, more importantly, what we’re supposed to do with it. I honestly had a hard time seeing what problem could be solved with this algebraic structure until I found this:

Prove that 8n+7 cannot be written as the sum of 3 squares.

In math, the easiest way to prove that a given statement is true is by proving that if it were false then nothing would make sense and everything would be bad [2]. This process is called proof by contradiction, and here’s mine for this problem:

Suppose 8n+7 = a^2 + b^2 + c^2 for some non negative integers n, a, b, and c.

If this were true, then we could write 8n = a^2 + b^2 + c^2 – 7 by subtracting 7 from both sides.

Because n is a positive integer, we know that if we divide both sides by 8 we will have an integer on both sides and that means that (a^2 + b^2 + c^2 – 7) is divisible by 8.

This means that (a^2 + b^2 + c^2 – 7) ⦀ 0 mod 8 because 8 divides evenly with no remainder.

Given this congruence, we can now say (a^2 + b^2 + c^2) ⦀ 7 mod 8 [3]
The second congruence is very important because now we have worked the problem to a point where it’s almosssst clear that a contradiction is appearing. All we have left to do is prove that the sum of the squares of three numbers cannot be congruent to 7 mod 8, or, in more clear terms, the squares of 3 numbers cannot sum to 7. This is very easy because there are only so many numbers that can sum to 7, specifically (0,0,7), (1,1,5), and (2,2,3).

From here, you might be inclined to say that clearly none of the potential sums are all squared numbers, so we’ve found this contradiction and can leave. However, these aren’t normal squares, they’re congruence classes that represent positive integers less than 8, which means its possible that there is a square greater than 8 that is congruent to n mod 8 so that n is one of the numbers that can potentially sum to 7 [4].

To prove that no number squared can sum with any other two squares to equal 7, we need to construct a table.

We’re almost done at this point. Because any positive integer can be represented as congruent to the integers 0-7 mod 8, their squares can also be represented by what is seen in the table above [5].

Because the congruences of the squares are all either 0, 1, or 4, it is not possible to take these numbers and sum them to 7. This finally indicates that it is not possible to represent 8n+7 as the sum of 3 squares and ends our proof.

Because it is not possible to find 3 integers a, b, and c such that the sum of their squares is congruent to 7 mod 8, we have found a contradiction with our supposition at the very beginning of our proof and demonstrated that it must be false.

This process ended up being a little more difficult to explain than I expected, which is really my bad cause I had already done the work so I knew what it took to achieve the understanding. Anyways, I’ll do something that can be represented physically so that it’s easier to visualize next week. I hope you found this cool, have a nice week until I write my next blog

[1] – The triple bar is supposed to be horizontal, Docs is uncooperative.

[2] – Fun example you’ve probably seen before: https://www.youtube.com/watch?v=hI9CaQD7P6I

[3] – I know I didn’t fully explain the algebraic nature of adding, subtracting, and multiplying congruence classes, but I really can’t write another 1300-word blog this week, so my source here is just gonna have to trust me bro.

[4] – I can tell this sentence is probably a little difficult to digest, but it’s too late to turn back now, so we keep marching forward : ).

[5] – trust me bro