3 frequently asked questions about modular arithmetic

Modular arithmetic is a special type of arithmetic that involves only integers. This goal of this article is to explain the basics of modular arithmetic while presenting a progression of more difficult and more interesting problems that are easily solved using modular arithmetic.

Motivation

Let's use a clock as an example, except let's replace the at the top of the clock with a .

3 Frequently Asked Questions About Modular Arithmetic

Starting at noon, the hour hand points in order to the following:

3 Frequently Asked Questions About Modular Arithmetic

This is the way in which we count in modulo 12. When we add to , we arrive back at . The same is true in any other modulus (modular arithmetic system). In modulo , we count

3 Frequently Asked Questions About Modular Arithmetic

We can also count backwards in modulo 5. Any time we subtract 1 from 0, we get 4. So, the integers from to , when written in modulo 5, are

3 Frequently Asked Questions About Modular Arithmetic

where is the same as in modulo 5. Because all integers can be expressed as , , , , or in modulo 5, we give these integers their own name: the residue classes modulo 5. In general, for a natural number that is greater than 1, the modulo residues are the integers that are whole numbers less than :

3 Frequently Asked Questions About Modular Arithmetic

This just relates each integer to its remainder from the Division Theorem. While this may not seem all that useful at first, counting in this way can help us solve an enormous array of number theory problems much more easily!

Residue

We say that is the modulo- residue of when 3 Frequently Asked Questions About Modular Arithmetic, and .

Congruence

There is a mathematical way of saying that all of the integers are the same as one of the modulo 5 residues. For instance, we say that 7 and 2 are congruent modulo 5. We write this using the symbol : In other words, this means in base 5, these integers have the same residue modulo 5:

3 Frequently Asked Questions About Modular Arithmetic

The (mod 5) part just tells us that we are working with the integers modulo 5. In modulo 5, two integers are congruent when their difference is a multiple of 5. In general, two integers and are congruent modulo when is a multiple of . In other words, 3 Frequently Asked Questions About Modular Arithmetic when is an integer. Otherwise, $a 
otequiv b pmod{n}$, which means that and are not congruent modulo .

Examples

  • 3 Frequently Asked Questions About Modular Arithmetic because is a multiple of .
  • because , which is an integer.
  • because , which is not a multiple of .
  • because , which is not an integer.

Sample Problem

Find the modulo residue of .

Solution:

Since R , we know that

and is the modulo residue of .

Another Solution:

Since , we know that

We can now solve it easily

and is the modulo residue of

Another Solution:

We know is a multiple of since is a multiple of . Thus, and is the modulo residue of .

Making Computation Easier

We don't always need to perform tedious computations to discover solutions to interesting problems. If all we need to know about are remainders when integers are divided by , then we can work directly with those remainders in modulo . This can be more easily understood with a few examples.

Addition

Problem

Suppose we want to find the units digit of the following sum:

We could find their sum, which is , and note that the units digit is . However, we could find the units digit with far less calculation.

Solution

We can simply add the units digits of the addends:

The units digit of this sum is , which must be the same as the units digit of the four-digit sum we computed earlier.

Why we only need to use remainders

We can rewrite each of the integers in terms of multiples of and remainders:

.
When we add all four integers, we get

At this point, we already see the units digits grouped apart and added to a multiple of (which will not affect the units digit of the sum):

.

Solution using modular arithmetic

Now let's look back at this solution, using modular arithmetic from the start. Note that

Because we only need the modulo residue of the sum, we add just the residues of the summands:

so the units digit of the sum is just .

Addition rule

In general, when , and are integers and is a positive integer such that

the following is always true:

.

And as we did in the problem above, we can apply more pairs of equivalent integers to both sides, just repeating this simple principle.

Proof of the addition rule

Let , and where and are integers. Adding the two equations we get:

Which is equivalent to saying

Subtraction

The same shortcut that works with addition of remainders works also with subtraction.

Problem

Find the remainder when the difference between and is divided by .

Solution

Note that and . So,

Thus,

so 1 is the remainder when the difference is divided by . (Perform the subtraction yourself, divide by , and see!)

Subtraction rule

When , and are integers and is a positive integer such that

the following is always true:

.

Multiplication

Modular arithmetic provides an even larger advantage when multiplying than when adding or subtracting. Let's take a look at a problem that demonstrates the point.

Problem

Jerry has boxes of soda in his truck. The cans of soda in each box are packed oddly so that there are cans of soda in each box. Jerry plans to pack the sodas into cases of cans to sell. After making as many complete cases as possible, how many sodas will Jerry have leftover?

See also:  Protein power: dna vs. rna

Solution

  • First, we note that this word problem is asking us to find the remainder when the product is divided by .
  • Now, we can write each and in terms of multiples of and remainders:

    This gives us a nice way to view their product:

  • Using FOIL, we get that this equals

We can already see that each part of the product is a multiple of , except the product of the remainders when each and are divided by 12. That part of the product is , which leaves a remainder of when divided by . So, Jerry has sodas leftover after making as many cases of as possible.

Solution using modular arithmetic

First, we note that

Thus,

meaning there are sodas leftover. Yeah, that was much easier.

Multiplication rule

When , and are integers and is a positive integer such that

The following is always true:

.

Exponentiation

Since exponentiation is just repeated multiplication, it makes sense that modular arithmetic would make many problems involving exponents easier. In fact, the advantage in computation is even larger and we explore it a great deal more in the intermediate modular arithmetic article.

Note to everybody: Exponentiation is very useful as in the following problem:

Problem #1

What is the last digit of if there are 1000 7s as exponents and only one 7 in the middle?

We can solve this problem using mods. This can also be stated as . After that, we see that 7 is congruent to -1 in mod 4, so we can use this fact to replace the 7s with -1s, because 7 has a pattern of repetitive period 4 for the units digit. is simply 1, so therefore , which really is the last digit.

Problem #2

What are the tens and units digits of ?

We could (in theory) solve this problem by trying to compute , but this would be extremely time-consuming. Moreover, it would give us much more information than we need. Since we want only the tens and units digits of the number in question, it suffices to find the remainder when the number is divided by . In other words, all of the information we need can be found using arithmetic mod .

We begin by writing down the first few powers of mod :

A pattern emerges! We see that (mod ). So for any positive integer , we have (mod ). In particular, we can write

  1. (mod ).
  2. By the “multiplication” property above, then, it follows that
  3. (mod ).

Therefore, by the definition of congruence, differs from by a multiple of . Since both integers are positive, this means that they share the same tens and units digits. Those digits are and , respectively.

Problem #3

Can you find a number that is both a multiple of but not a multiple of and a perfect square?

No, you cannot. Rewriting the question, we see that it asks us to find an integer that satisfies .

  • Taking mod on both sides, we find that . Now, all we are missing is proof that no matter what is, will never be a multiple of plus , so we work with cases:
  • This assures us that it is impossible to find such a number.

Summary of Useful Facts

Consider four integers and a positive integer such that and . In modular arithmetic, the following identities hold:

  • Addition: .
  • Subtraction: .
  • Multiplication: .
  • Division: , where is a positive integer that divides and .
  • Exponentiation: where is a positive integer.

Applications of Modular Arithmetic

Modular arithmetic is an extremely flexible problem solving tool. The following topics are just a few applications and extensions of its use:

  • Divisibility rules
  • Linear congruences

Resources

See also

  • Intermediate modular arithmetic
  • Olympiad modular arithmetic

An Introduction to Modular Arithmetic

The best way to introduce modular arithmetic is to think of the face of a clock.
3 Frequently Asked Questions About Modular Arithmetic

The numbers go from $1$ to $12$, but when you get to “$13$ o'clock”, it actually becomes $1$ o'clock again (think of how the $24$ hour clock numbering works). So $13$ becomes $1$, $14$ becomes $2$, and so on.

This can keep going, so when you get to “$25$ o'clock'', you are actually back round to where $1$ o'clock is on the clock face (and also where $13$ o'clock was too).

3 Frequently Asked Questions About Modular Arithmetic

So in this clock world, you only care where you are in relation to the numbers $1$ to $12$. In this world, $1, 13, 25, 37, ldots$ are all thought of as the same thing, as are $2, 14, 26, 38, ldots$ and so on.

What we are saying is “$13=1+$ some multiple of $12$”, and “$38=2+$ some multiple of $12$”, or, alternatively, “the remainder when you divide $13$ by $12$ is $1$” and “the remainder when you divide $38$ by 12 is 2''. The way we write this mathematically is $13equiv 1 ext{ mod } 12$, $38equiv 2 ext{ mod } 12$, and so on. This is read as “$13$ is congruent to $1$
mod (or modulo) $12$” and “$38$ is congruent to $2 ext{ mod } 12$”.

But you don't have to work only in mod $12$ (that's the technical term for it). For example, you could work mod $7$, or mod $46$ instead if you wanted to (just think of clocks numbered from $1$ to $7$ and $1$ to $46$ respectively; every time you get past the biggest number, you reset to $1$ again).

3 Frequently Asked Questions About Modular Arithmetic

Let's go back to the normal clock face with the numbers $1$ to $12$ on it for a moment.

Mathematicians usually prefer to put a $0$ where the $12$ would normally be, so that you would usually write (for example) $24equiv 0 ext{ mod } 12$ rather than $24equiv 12 ext{ mod } 12$, although both of these are correct.

That is, we think of a normal clock face as being
numbered from $0$ to $11$ instead. This makes sense: we'd normally say that $24$ leaves a remainder of $0$ when we divide by $12$, rather than saying it leaves a remainder of $12$ when we divide by $12$!

Let's be a bit more formal. In general, if you are working in mod $n$ (where $n$ is any whole number), we write $aequiv b ext{ mod } n$ if $a$ and $b$ leave the same remainder when you divide them by $n$. This is the same as saying that we write $aequiv b ext{ mod } n$ if $n$ divides $a-b$. (Look at what we did earlier to see that this definition fits with our
examples above.)

So far, we've only talked about notation. Now let's do some maths, and see how congruences (what we've described above) can make things a bit clearer.

Here are some useful properties. We can add congruences. That is, if $aequiv b ext{ mod } n$ and $cequiv d ext{ mod } n$, then $a+cequiv (b+d) ext{ mod } n$. Why is this? Well, $aequiv b ext{ mod } n$ means that $a=b+k n$, where $k$ is an integer.

Similarly, $cequiv d ext{ mod } n$ means that $c=d+l n$, where $l$ is an integer. So $a+c=(b+k n)+(d+l
n)=(b+d)+(k+l)n$, so $a+cequiv (b+d) ext{ mod } n$. For example, $17equiv 4 ext{ mod } 13$, and $42equiv 3 ext{ mod } 13$, so $17+42equiv 4+3equiv 7 ext{ mod } 13$.

Note that both of the congruences that we're adding are mod $n$, and so is the answer – we don't add the moduli.

Now you prove that if $aequiv b ext{ mod } n$ and $cequiv d ext{ mod }n$ then $a-cequiv (b-d) ext{ mod } n$. Also, prove that we can do something similar for multiplication: if $aequiv b ext{ mod }n$ and $cequiv d ext{ mod } n$, then $a cequiv b d ext{ mod } n$.

You can prove this in the same way that we used above for addition. Again, both of the
congruences that we're multiplying are mod $n$, and so is the answer – we don't multiply the moduli.

Can you come up with an example to disprove the claim that $aequiv b ext{ mod } n$ and $cequiv d ext{ mod } m$ means that $a c equiv bd ext{ mod } mn$?

Division is a bit more tricky: you have to be really careful. Here's an example of why. $10equiv 2 ext{ mod } 8$. But if we “divide both sides by 2”, we'd have $5equiv 1 ext{ mod } 8$, which is clearly nonsense! To get a true congruence, we'd have to divide the $8$ by $2$ as well: $5equiv 1 ext{ mod } 4$ is fine.

Why? Well, $aequiv b ext{ mod } n$ means
that $a=b+k n$ for some integer $n$. But now this is a normal equation, and if we're going to divide $a$ by something, then we have to divide all of the right-hand side by $2$ as well, including $k n$.

In general, it's best not to divide congruences; instead, think about what they really mean (rather than using the shorthand) and work from there.

Things are quite special if we work mod $p$, where $p$ is prime, because then each number that isn't 0 mod $p$ has what we call an inverse (or a multiplicative inverse , if we're being fancy). What that means is that for each $a
otequiv 0 ext{ mod } p$, there is a $b$ such that $a
bequiv 1 ext{ mod } p$.

Let's think about an example. We'll work mod $7$. Then really the only non-zero things are $1, 2, 3, 4, 5$ and $6$ (because every other whole number is equivalent to one of them or $0$). So let's find inverses for them. Well, $1$ is pretty easy: $1 imes 1equiv 1 ext{ mod } 7$.

What about $2$? $2 imes 4equiv 1 ext{ mod } 7$. So $4$ is the inverse of $2$. In
fact, we can also see from this that $2$ is the inverse of $4$ – so that's saved us some work! $3 imes 5equiv 1 ext{ mod } 7$, so $3$ and $5$ are inverses.

And finally, $6 imes 6equiv 1 ext{ mod } 7$, so $6$ is the inverse of itself. So yes, each of the non-zero elements mod $7$ has an inverse.

Try some primes out yourself: $11$ and $13$ are fairly small! If you're feeling confident, see
whether you can discover which numbers have inverses mod $4$, or mod $6$, or mod $8$. What about mod $15$? Do you notice any patterns?

To prove this, things are going to get a tiny bit more tricky, so I'm going to save the proof for the end and first give an example of using congruences to do useful mathematics.

Suppose we're given the number $11111111$ and someone asks us whether it's divisible by $3$. We could try to actually divide it. But you probably know a much easier method: we add up the digits and see whether that's divisible by $3$. There's a whole article about this sort of divisibility test here . Let's prove this using congruence notation.

Modular Arithmetic

Practice makes perfect, and that's exactly what this lesson is about; practice in modular arithmetic.

Modular arithmetic is sometimes called clock arithmetic, because the rules in modular arithmetic are the same rules that apply to telling the time.

In a clock, there are 12 hours, and once you get to 12:00, the next hour starts over at 1:00. In modular arithmetic, 12 would be called the modulus, and it's the number we start over at.

As a quick review, rmodn is equal to the remainder when we divide r by n. Addition, subtraction, and multiplication in modular arithmetic obey two basic rules.

  1. If a + b = c, then (a + b)modn is congruent to cmodn.
  2. If amodn is congruent to dmodn and bmodn is congruent to emodn, then (a + b)modn is congruent to dmodn + emodn.

In each of these rules, the plus sign can be replaced by a subtraction or multiplication sign. These rules state that we can first perform the operation and then find that number modn, or we can find each of the numbers modn and then perform the operation on them.

It's important to note that when dealing with subtraction, you may get negative numbers. When this happens, you add multiples of the modulus n until you get a number between 0 and n – 1. This is demonstrated in our second example.

These rules are much easier to see in action, so let's go through a couple of examples now to make these rules a little less confusing.

Basic Examples

Use the rules of modular arithmetic to solve the following problems.

1.) As in our initial clock example, let's work in modulus 12. Assume it is 7:00, and we want to know what time it will be 10 hours from now.

Solution:

Basically, this is asking us to find (7 + 10)mod12. To perform this operation, we first add 7 + 10 to get 17, so (7 + 10)mod12 is congruent to 17mod12. Next, we find 17mod12.

To find 17mod12, we find the remainder when 17 is divided by 12, which is 5. Therefore, (7 + 10)mod12 is congruent to 5mod12. This tells us that if it is 7:00, then 10 hours from now, it will be 5:00.

The following image shows the work that's described in a nice compact form.

Work For Example 1

3 Frequently Asked Questions About Modular Arithmetic

2.) Working in modulus 5, find (73 – 64)mod5.

Solution:

If we subtract first, we have 73 – 64 = 9, so (73 – 64)mod5 is congruent to 9mod5. Now we just need to find the remainder when 9 is divided by 5, which is 4. Therefore, (73 – 64)mod5 is congruent to 4mod5.

We can also first find that 73mod5 is congruent to 3mod5 and that 64mod5 is congruent to 4mod5. By our rules, we have that (73 – 64)mod5 is congruent to 3mod5 – 4mod5 which is congruent to -1mod5.

We have a negative number, so we add multiples of 5 until we get a number between 0 and 4. If we add 5 to -1, we get 4, which falls in our range, so this is our answer.

We see that once again, we get that (73 – 64)mod5 is congruent to 4mod5.

All of the work is demonstrated in the following image.

Work For Example 2

3 Frequently Asked Questions About Modular Arithmetic

3.) Working in modulus 17, find (18*20)mod17.

Solution:

Modular Arithmetic | Brilliant Math & Science Wiki

Is there a positive integer nnn for which n7−77 n^7 – 77 n7−77 is a Fibonacci number?

If ppp is a prime of the form 7k+1 7k + 1 7k+1, then there are k+1 k + 1 k+1 seventh powers (where the +1 accounts for 0). This gives a fighting chance of the residues being distinct from the Fibonacci residues. So, we try the smallest prime of the form 7k+1 7k+17k+1, which is 29.

We can check that n7≡0,1,12,17,28(mod29)n^7 equiv 0, 1, 12, 17, 28 pmod {29}n7≡0,1,12,17,28(mod29), which gives us

n7−77≡9,10,11,22,27(mod29). n^7 – 77 equiv 9, 10, 11, 22, 27 pmod {29}.n7−77≡9,10,11,22,27(mod29).

When looking at the remainder of the Fibonacci numbers taken modulo 29, we obtain the repeating sequence

1,1,2,3,5,8,13,21,5,26,2,28,1,0,…. 1, 1, 2, 3, 5, 8, 13, 21, 5, 26, 2, 28, 1, 0 , ldots. 1,1,2,3,5,8,13,21,5,26,2,28,1,0,….

A quick check shows us that no number appears in both sequences, and thus the answer is no. □_ square □​

Be the first to comment

Leave a Reply

Your email address will not be published.


*