[Lesson] Modular Arithmetic

[Ender]

Lesson and Problems

Edit: Edited the problems because some of them were poorly composed.

[Miamiandy]

Good correction, because there is no x and y where x^2 +y^2 = 3

[rabbit]

I like:

In math, you think about it as .  This is read as "6 is congruent to 1 modulo 5".

Just a liiiiiiiiiiiitle off..

Anyway, that is a really bad lesson..

[Miamiandy]

Should've proof read it.

[Ender]

I like:

In math, you think about it as .  This is read as "6 is congruent to 1 modulo 5".

Just a liiiiiiiiiiiitle off..

Anyway, that is a really bad lesson..

You pointed out a semantic mistake rather pedantically and then said it was a bad lesson, without any explanation. Do you value your opinion at all or do you want it to be ignored due to your insubstantial and ineffective argument...

Anyways, thanks for bringing it to my attention that the lesson needs proofreading.

[rabbit]

He doesn't explain powered associations at all, he doesn't explain the first example at all.  He simply says "this is that and that is congruent to blah."  Very little is explained, and there isn't enough lesson to teach how to properly do the problems.

really bad lesson

[Rule]

You say you believe that there are too many exercises and not enough "problems" included in standard math lessons, yet you have solely given exercises and no "problems."

Decent lesson, although it still needs to be refined.  I am not going to sift through specific details, because I am sure you will notice them yourself on a repeated reading.

[Ender]

I would like to revive and salvage this topic. In response to Rule, I think that their having to find the modulos that are the key to these problems was the problem-solving aspect.

But here's a hint for some of the problems, which I will repost here.

1. What is the remainder of 3500 when it is divided by 7. Do not use a
calculator.
2. Find all integer solutions to x^2 + y^2 = 195
3. Find all integer solutions to x^4 + y^4 = 257.
4. Find all integer solutions to x^3 + y^3 = 6668
5. Find all integer solutions to 3x^3 + 5y^3 = 686

Solution to 2:
 
The number 4 is a useful modulus for squares.

Consider the times table modulo 4.

0  1 2 3 4 5 6 7 8 9 10
1  1 2 .  .  . 
2  2 0
3  3 2 1
4  .        0
5  .           1
6  .              .
7                     .                     
8                        .
9
10                           0

Notice that all the squares modulo 4 are congruent to 0 or 1.

Thus x^2 =~ 0 or 1 (mod 4), y^2 =~ 0 or 1 (mod 4), and since 195 = 200 - 5 =~ -1 (mod 4), there are no solutions. In other words, if x = y, then x must be congruent to y modulo any m, and in this problem we see it is impossible for 0 or 1 plus 0 or 1 to add up to -1 aka 3.*

*Remember that -1 =~ m - 1 (mod m). It's useful to use -1 because it can be generalized, i.e. 7 =~ 3 (mod 4), but 7 =~ 7 (mod 8 ), however we can generalize this to say that 7 is congruent to -1 for both modulo 4 and 8.

The next problems are hinged on finding useful modulos. I added one more problem, #3, as a follow-up to this.

Edit: I don't like it when my (mod 8 ) gets turned into a smiley face...

[d&q]

Here's how I learned modular arithmetic,

Imagine we decide to do all arithmetic in base 5. Doing arithmetic in different number bases is not always easy; for example, you don't want to memorize a multiplication table for base 16. (B * C = 84?!) So just to make it easier on ourselves, we will consider only the last digits. All numbers which have the same last digit in base 5 will be considered equal:

2₅ = 12₅ = 22₅ = 32₅ = ...

In base 10, this looks like

2 = 7 = 12 = 17 = ...

The usual way to show that we are using this system is to replace the = with ≡, and also to append the suffix (mod 5). We thus write, for example, 12 ≡ 7 (mod 5). We say that 12 is congruent to 7 mod 5.

Another way to look at mods is that 2, 7, 12, 17, etc. all have the same remainder (2) when divided by 5. This method of viewing modular arithmetic makes actual computation much easier. It is often useful to find the smallest nonnegative integer which is congruent to x mod y. (For example, the smallest integer congruent to 12 mod 5 is 2.) When we perform this task, we say that we 'mod out' the 12. Now you see how our second way of viewing mods is useful. To mod out 7631 in mod 7, we can either find 7631 in base 7 and look at the last digit, or we can divide by 7 and look at the remainder.

In this discussion of remainders, we have used mods to denote the amount more than a multiple of 5 a given number is. For example, 2, 7, 12, 17, etc. are all exactly 2 more than a multiple of 5. In the same way we can define negative mods as the amount less than a multiple of 5 a number is. Since 2, 7, 12, 17, etc. are all 3 less than the nearest multiple of 5, they are all congruent to -3 mod 5. Extending this reasoning, we can write in mod 5:

... ≡ -13 ≡ -8 ≡ -3 ≡ 2 ≡ 7 ≡ 12...

Note that each term is five away from the one before it and after it.

Why does the remainder method described above work?

Solution: Consider 7631 in base 7. It is 31151₇, or

3*7⁴ + 1*7³ + 1*7² + 5*7 +1

When we divide this expression by seven, the seven evenly divides the first 4 terms of the sum and leaves the last term as the remainder, i.e. 7631/7 = 3*7³ + 1*7² + 1*7 + 5, with a remainder of 1. Hence we see that the last digit of 7631 written in base 7 is the same as the remainder we have upon dividing 7631 by 7. This is why the remainder method works.

How many positive integers less than 100 are congruent to 3 mod 5?

Solution: The smallest is obviously 3. The largest number is 98. How many are there in between? We have 3 = 0(5) + 3 and 98 = 19(5) + 3, and the other numbers congruent to 3 mod 5 will be 1(5) + 3, 2(5) + 3, and so on. The number by which 5 is multiplied can be 0, 1, 2, ..., 19, so there are 20 possibilities.

Once the principle of congruence is understood, we can move on to doing actual arithmetic with it. One thing we can do with a congruence like

12 ≡ 7 (mod 5)

is add the same thing to both sides:

12 + 3 ≡ 7 + 3 (mod 5)

We can do this because if the last digits in base 5 are the same before the addition, they will be the same after the addition. Clearly the same will be true for subtraction.

How about for multiplication? Again, the same should hold. If the last digits are the same before multiplication, they will be the same after.

Not only can we multiply or add the same quantities to both sides, but if x and y have the same last digit in base 5, then we can add x to one side and y to the other in mod 5. For example, since 8 and 13 have the same last digit in base 5,

12 + 13 ≡ 7 + 8 (mod 5)

Applying this concept to multiplication, since 12 and 7 are congruent mod 5, we can multiply one side by 12 and other by 7, yielding

12² ≡ 7² (mod 5)

In this manner, we can raise the two sides to any positive integral power!

WARNING: Division is a much more complicated matter. For instance, clearly 5 ≡ 10 (mod 5), but if we divide both sides by 5, we have 1 ≡ 2 (mod 5), a false relation. Just remember that division doesn't generally work in modular arithmetic.

In finding the last digit of a sum or product of two numbers, we don't need to do the entire sum or product, just the sum or product of the last digits of the two numbers. In mods, this is reflected by the fact that we can "mod out" before or after doing operations; the order doesn't matter. By this we mean that we can mod out the factors of a product and then multiply the results rather than having to mod out the product of the numbers. For example, since 9899 ≡ 4 (mod 5) and 7677 ≡ 2 (mod 5), we can say  9899 * 7677 ≡ 4 * 2 ≡ 8 ≡ 3 (mod 5) rather than first multiplying 9899 and 7677 and modding out the product.


Let's summarize what we can do with congruences. If a ≡ b (mod m), then for all positive integers c:

1. a + c ≡ b + c (mod m)

2. a - c ≡ b - c (mod m)

3. ac ≡ bc (mod m)

4. a^c ≡ b^c (mod m)

5. (a + b) (mod m) ≡ a(mod m) + b (mod m)

6. ab (mod m) ≡ (a (mod m))(b (mod m))