A Kick in the Discovery

As the title suggest, this is the fifth in a series of articles on introductory Number Theory. Today’s the day that we learn about fancy arithmetic called modular arithmetic or clock algebra.

A Motivating Mystery

Can you see why you will never find integer solutions to when ?

We’ll spend some time today developing some tools that might seem strange and potentially not very useful… however, you’ll be pleasantly surprised. There are many problems that become obvious due to the use of modular arithmetic. The above problem is one of them!

Clock Counting (aka Modular Arithmetic)

Fun Fundamentals

Do you remember way back when you first learned how to divide two integers (I know I know you don’t like division)? You were supposed to answer with a remainder. Something like 30 divided by 4 equals 7 remainder 2 or simply . Just in case let’s dust off those skills because we are going to need them today!

For no other reason than because we can, we are going to focus on remainders. By this, we mean situations like, “What’s 23’s remainder when dividing by 10?” Well, 23 divided by 10 is 2 R3 or, 23 has a remainder 3 when divided by 10. Similarly, 45 has a remainder of 5 when divided by 10. And if you recall The Division Algorithm from Newbie at

Number Theory (Part 1) you know that we can always find a remainder.

The phrase “# has a remainder of # when divided by #” is very clunky and long. And I’m lazy. So, we will adopt the language of congruence and mod. Instead of saying: 23 has a remainder 3 when divided by 10 we will now say 23 is congruent to 3 (mod 10). Where congruent means “has a remainder” and mod means “when divided by”.

23 has a remainder 3 when divided by 10 23 is congruent to 3 (mod 10).

45 has a remainder of 5 when divided by 10 45 is congruent to 5 (mod 10).

12 has a remainder 0 when divided by 6 12 is congruent to 0 (mod 6).

2000 has a remainder 43 when divided by 103 2000 is congruent to (43 mod 103).¹

Now that we have new language, let’s introduce some new symbols too. OOOoooo

Usually, when we say 5 times 2 equals 10 we don’t write out “times” and “equals” we use symbols like and . Introducing these symbols is a good idea because they have great utility, since our sentences become short expressions. And we can then manipulate the expressions, like we learn in algebra.

5 times 2 equals 10 .

But, we aren’t talking about equality, we are talking about congruency. As we will see they are similar to one another and to highlight this we use similar symbols. When we say 23 is congruent to 3 (mod 10) we’ll write: .

23 is congruent to 3 (mod 10) .

45 is congruent to 5 (mod 10) .

12 is congruent to 0 (mod 6) .

2000 is congruent to 43 (mod 103) .

I think the use of strange notation is a big challenge people have with reading and learning math on their own. Such as the three-lined “equal to” symbol we are now using. When you see with (mod #) it’ll likely mean what we have outlined above: congruency (mod #).

The idea of thinking of congruency as short-hand for remainders is intuitive and quick (sometimes!). However, there is a more formal definition of congruency that captures this intuition and more. We will need this later, so let’s get it out now!

Definition (Congruency): Two integers and are congruent if, is a multiple of . Or if you prefer, when divides .

.

for some integer .

Applying this to our running examples,

( and ).

( and ).

( and ).

( and ).

The reason why this definition was chosen is multifold. One advantage is that we don’t need to focus on remainders that come out of the division algorithm. The algorithm forces us to have the remainder such that: when we are working (mod n) and this is unnecessary. We can consider other numbers congruent to 3 (mod 10) and this definition helps us see more of the numbers congruent to other than . For example, and divides . We also have,

.

And you don’t need to stop before you get to negative numbers either:

.

Since, for example, and divides 30.

We sometimes use the language of reducing, like with fractions. For example, since 23 is congruent to 3, and we could say that we reduced 23 (mod 10) to get 3. Or, we could say, that we reduced 123 to 23 (mod 10), since 123>23.

Another word that you might see is: residue mod n. Just like there is a simplest form of a fraction, there is a `simplest form’ of an integer mod n. But what’s simplest form mean for reducing? We define residue to be the integer we get when we’ve reduced enough to be in the range 0 to n-1 when reducing (mod n). For example, when working (mod 10), we say 3 is the residue of: .

Oh, and if you are wondering why modular arithmetic is sometimes called clock algebra, it’s because you already do this when you are reading a clock (when it’s past noon)! For example, 15 hours after midnight, is 3:00pm. Not 15:00, unless you are in the military. So in a way, 3:00pm is the same as 15:00. This is the same as the statement . So, when you are reading a clock, you are doing modular arithmetic mod 12.

Tricks of the Trade (mod n)

Now that we have some of the basics down, we might wonder if we can add, subtract, multiply, or divide congruences like we do with integers. For example, we already know that and . Is it true that:

or,

or,

But since it doesn’t make sense to combine congruences that use a different mod number (or moduli) we don’t ask any questions regarding changing (mod 10) to some other (mod n) mid calculation (this is akin to how you can’t add fractions when the denominators are not the same). But if we stick to we can try the addition situation. Well, 23+45 =68. And 68 has a remainder of 8 when divided by 10. Similarly, 3+5 = 8, which also has a remainder of 8 when divided by 10. So, it seems to work with addition. For the same reason, congruence works with subtraction and multiplication. Division, however, that’s… more tricky. We save that for later!

Aggravating Addition

What exactly are we aiming to do here?

We want to show that we can reduce before we add or after we add, either way we get the “same sum”, that is, up to congruence.

Modular Addition: If and , then .

Proof: (Click in the Discovery)

Let,

and .

How do we get a foot hold here? How do we compare remainders? This is why we went through the formal definition of congruence. Applying the definition we deduce:

and ,

for some integers and . Since we want to show that , we must show that , for some integer . This is indeed the case! If we add the expressions: and , we see,

.

With some rearranging,

.

And since and are integers their sum is an integer too! We’ve found our integer that we wanted. Namely, . We’re done!

implies .

By the way, since we did not assume were positive, this proof is valid for subtraction too!

Corollary (Modular Subtraction): If and , then .

Problematic Products

We want to do the same thing we did with addition, but with multiplication:

Modular Multiplication: If and , then .

Proof: (Click in the Discovery)

We employ the same strategy! We know by definition,

and ,

and thus,

and .

Since we want to show , let’s multiply and and see we get.

Do you see why we’re finished? Take a look,

Recall the definition of congruence and observe that we’ve just shown , we conclude .

What about division? Is there a division corollary?

Delicate Division

What does it mean?

Division is a tricky one to manage. Since we are only concerning ourself with whole numbers, what would even mean? Well, with normal division, because . So maybe since we understand multiplication using mod, we should think of division in terms of undoing multiplication?

So let’s think of as , where we think of as the number that gets you back to 1 when you multiply by 2. Likewise where is such that .

So maybe we interpret: as where is the number such that:

.

Well, . So I guess ? Indeed! This is how we choose to define division, we define it in terms of undoing multiplication.

Quick recap:

becomes , and since we identify . Thus, .

One bit of notation. Since we only care about integers, writing is clunky and potentially confusing. So, we write as . More generally,

.

Division: We define to be Where we identify as the integer such that .

Does it work?

Ok, so now we know what division means using mods. Is it always true if and , then ? Or, more accurately, . Let’s do a numerical experiment.

Example 1: (mod 11)

Consider and , is it true . Or, more accurately, .

Step 1: Find (mod 11 ) and (mod 11).

Ok, so we need two integers such that and ². There’s no easy way in general to find these numbers. Trial and error yield a possible solution:

and ,

Check the 24 case here. Thus, and .

Step 2: “Divide”

Plugging and into our “division” problem we get:

and

.

So, they do match! Nice!

Let’s try another one.

Example 2: (mod 10)

Very similar to before, but now (mod 10): and . Now let’s try ..

Step 1: Find mod 10 and mod 10.

Ok, what number times ? Hint: If you guess and check some numbers, you might get disappointed. Let’s instead ask a similar question we know how to answer:

What number satisfies equivalently,

.

Recall all the work we did in part 3 to find integer solutions to equations of the form: .

Can you see the issue here? We showed that there is no integer solution to if the greatest common divisor (in this case ) doesn’t divide the right and side N, (in this case 1). And , so there is no integer solution. (For those who didn’t read part 3, which you should, to get more traffic to my website, notice how the left-hand side is always even, but the right-hand side, 1, is odd. We know and hence there is no integer solution!)

What?!?!??? NO solution?

Yup, and as a consequence there is no so there is no way to divide by . This means that some division problems don’t make sense to ask.

What failed (mod 10) and didn’t fail (mod 11)?

What failed (mod 10) was that 24 and 10 share a factor of 2. This then meant that had no integer solution. And as a consequence, there is no , and no way to divide by 24. This wasn’t a problem working (mod 11). Since 11 is prime, we know all non-multiples of 11 are such that . So dividing by 24 and 2 was fine to do.

Remark: By the same logic, you cannot divide by any multiple of 11 (mod 11), such as 11, 22, 33, 44, 55, etc. This is equivalent to dividing by 0, since all these have a residue of 0 (mod 11).

Moral: In order to be able to divide by working (mod n) it must be that

Now we can write a lemma and the division corollary.

Lemma: Let and be integers. Then, there exists if and only if

Proof Idea: Use the connection between the existence of and there being solutions to Then use Bézout’s Identity from (part 3) to finish, just as we did in the example (mod 10).

---

Corollary (Modular Division): If and , then or, better yet,

Proof Idea: We know by the lemma that division makes sense, and by converting division to multiplication we can use modular multiplication.

A Motivating Mystery (The Solution)

Recall the question from the beginning:

Can you see why you will never find integer solution to with ?

Key Idea: If we had no tools at our disposal, we might guess and check different and to see what might happen. When N = 3 it’s not too bad to show that there is no integer solution. It becomes unreasonable when N gets large. However, our guess and check method has merit. All we need to do is minimize our set of numbers we need to guess and check for and .

Consider that if then . This is because we can reduce before or after we multiply and add. Now we don’t have so many numbers to check for and , we only have (n – 1) integers to guess and check from: This is better!

Solution: With the hindsight of knowing the answer let n=4.³ This means that and will be congruent to 0, 1, 2, or 3 (mod 4). Consider the possible values for and (mod 4).

Observe that and can only be 0 or 1 (mod 4). Thus, but not . (Why?)

Now take a look at with . For all these values of N notice , but we just showed that there is no way ! Since there is no way to solve the equation (mod 4), there is no way to solve it in general. Hence: there is no solution! WOWWWW!

Closing Remarks

Modular arithmetic is a very useful tool to have at your disposal. You’d be surprised to see how many times focusing on remainders simplifies life! (Life in general, not just math problems!)

You’re finally ready to learn about Fermat’s little theorem! It’s a beautiful little theorem! We will cover it next time, but I want you to have a chance for a kick in the discovery! So, consider the following:

.

.

.

.

.

.

.

.

.

.

.

.

Notice anything? If so, make a conjecture! Then try to prove it!

Hint: 5, 7, and 11 are primes and that the exponents are (PRIME) – 1. Try these with composite modulus.

Footnote:

1. You can check this one here because I sure didn’t do this one by hand! ↩︎
2. Two b or not two b that is the question… ↩︎
3. The other way to get at n=4 is to try other n’s and realize 4 is the best!. ↩︎