Did you know 2 ≅ 9, Mod 7?

A few days back we discussed mathematical induction and had a gay old time with showing how we can depend upon the function below to be able to accurately calculate the sum of the first n integers.

[math]frac{n(n+1)}{2}[/math]

I thought that was neat. My Discrete Mathematics course is proving to be quite fun and yesterday we took another step into the obscurities of equality classes. I will attempt, modestly, to share some of the cool shit we went over yesterday, regarding congruence.

If i were to ask you what day of the week is 42 days from today you could start counting it out, and you would eventually land on “Thursday” the same as today. Did you know that 49 days from today is also on Thursday? This goes on and on to oblivion. We have a calendar that has 7 day weeks and if you divide 42 by 7 you get a remainder of 0. This remainder is of the utmost importance, because it allows us to draw the congruence relationship between the days of the week.

[0] = { 0, 7, 14, 21, 28, 35, 42, 49, ...}
[1] = { 1, 8, 15, 22, 29, 36, 43, 50, ...}
[2] = { 2, 9, 16, 23, 30, 37, 44, 51, ...}
[3] = { 3, 10, 17, 24, 31, 38, 45, 52, ...}
[4] = { 4, 11, 18, 25, 32, 39, 46, 53, ...}
[5] = { 5, 12, 19, 26, 33, 40, 47, 54, ...}
[6] = { 6, 13, 20, 27, 34, 41, 48, 55, ...}

These are what we call Equivalence Classes which follow a few rules which come from set theory, so i will use that .

  1. Reflexivity – any value x is related to itself
  2. Symmetry – If x relates to y, then y relates to x in the same way
  3. Transitive – if x relates to y, and y relates to z, then x relates to z

In order to try to un-obfuscate this, because variables tend to scare people, let’s walk through our relationship we discussed earlier, Mod 7.
Reflexivity – Is 1 related to 1, mod 7?

Yes, absolutely. It would be hard not to have this be the case.

[math]frac{1}{7}=0 r1[/math]

Symmetry – If 1 is related to 8, is 8 related to 1, Mod 7?

Yes, absolutely. they both leave the same remainder 1

[math]frac{8}{7}=1 r1[/math]

Transitive – If 1 is related to 8 and 8 is related to 43, is 1 related to 43, Mod 7?

It most certainly is, all three have the same remainder.

[math]frac{43}{7}=6 r1[/math]

This is an equivalence relationship, called Modulus. It works on all modulus arithmetic, the only thing that may change is the number of groups. Mod 7 has 7 groups, but Mod 42 has 42. The groups start with 0 (because 7/7 is actually leaving the remainder of 0) so computer dev’s should be comfortable. Ill get more of this sort of cool shit to you all in just a little bit.

For instance, did you know that if ab that a2b2?