We will start with definitions. First of all, and most basically, we will go over the definition of congruence in a modulo. We define \(a\equiv b \pmod{m}\) to mean that \(a-b\) is divisible by \(m\). We say this as \(a\) is congruent or equivalent to \(b\) in \(\pmod{m}\). In other words, it means that \(a\) and \(b\) have the same remainder when divided by \(m\). For example, \(10\equiv 4\equiv 1 \pmod{3}\) because 10, 4, and 1 all have a remainder of 1 when divided by 3. We will talk about multiplication, division, addition, subtraction, and exponentiation in the lesson. Note that we let \(-a\equiv m-a\pmod{m}\) as well. We call \(m\) the modulus.
Sample Problem 1. If some number of people are separated into rows of 10, there are 3 left over. How many people are left over if 3 more people are arranged into the rows of 10? What does this have to do with the definition we just discussed?
In this problem, it is clear that we aren't doing anything to the rows of 10, but just adding 3 more people to the people left over. Thus, we have 6 people left over. This seems to be common sense, and it is. Let's see how this applies to modular arithmetic. First, we will start by rewriting the problem in terms of the terminology we just saw. We will let the number of people be \(a\). Thus, we see that \(a\equiv 3 \pmod{10}\). Rewriting what we found out about adding in 3 people, we see that \(a+3\equiv 3+3 \equiv 6 \pmod{10}\). Now, this is no proof that addition works as normal in modular arithmetic, but it should be fairly clear from thinking about how we solved this problem that you can add anything to both sides of an equivalence.
Sample Problem 2. Does multiplication work like it normally does in modular arithmetic? In other words, can you multiply both sides of a congruence by the same thing in modular arithmetic? How about exponentiation?
We can fairly easily see that multiplication does indeed work as normal in modular arithmetic. Too prove this we just need to remember that multiplication is just repeated addition. Because we just saw that addition works in the previous problem. Using similar reasoning, we can see that exponentiation works because it is just repeated multiplication.
Sample Problem 3. Does division work in modular arithmetic?
You might think that the answer is yes, but having fractions sometimes result from divisions should give you a pause. After all, the very definition of modular arithmetic is based on working with solely integers. The answer to the question ends up being, yes, kind of, and weirdly. Lets look at a few examples to see how we think division would work. Let's say that we have \(7a\equiv 7\pmod{49}\). If we divide both sides of the congruence by 7, we get \(a\equiv 1\pmod{49}\). While \(a\equiv 1\pmod{49}\) may appear to work at first, and it is a solution, there are other solutions that work, such as \(a\equiv 8\pmod{49}\). Thus, unlike the other operations we saw, \(a\equiv b \pmod{m}\) does not imply \(\frac{a}{c}\equiv \frac{b}{c} \pmod{m}\)(at least not always) even though \(\frac{a}{c}\equiv \frac{b}{c} \pmod{m}\) does imply \(a\equiv b \pmod{m}\). Also, be careful in that dividing doesn't always produce a true statement. For example, \(21\equiv 7 \pmod{7}\), but \(3\not\equiv 1 \pmod{m}\). In addition, division seems weird without being able to do it to every number (we can't get fractions), so er can conclude that division, in the traditional sense, does not work in modular arithmetic.
We did see that one of the divisions produced a true statement, and if we want to solve equations similar \(3x\equiv 6 \pmod{9}\), we will need to be able to "divide." Lets try to think about what division does in order to try to come up with something that acts similarly. First of all, let's look at \(7a\equiv 7\pmod{49}\) means in algebra. using our earlier definitions. Thinking about how it means that both sides of the congruence have the same remainder, we can rewrite our equation as 7a=7+49y (y is integral, but not necessarily positive). Thus, when we divide this equation by 7, we get a=1+7y. In other words, by converting back to modular notation, we get \(a\equiv 1\pmod{7}\). Generalizing what we just saw, we get one form of "division" in modular arithmetic: \(a\equiv b\pmod{m}\) implies\(\frac{a}{c} \equiv \frac{b}{c}\pmod{\frac{m}{c}}\) if \(c\)is a divisor of \(a\), \(b\), \(c\) (otherwise we get fractions and fractions don't work with remainders and modular arithmetic).
Now that we have defined "division" in some cases, what will we do if all of the numbers don't share a common divisor? For example, how do we find all of the solutions to \(14a\equiv 5\pmod{18}\) or \(5a\equiv 6\pmod{9}\).
We will look at cases similar to the former example first; we will look at cases of \(a\equiv b\pmod{m}\) where \(a\) and \(m\) have a common divisor that \(a\) does not have. If this is the case, then we can rewrite the congruence as \(q\cdot r\cdot a\equiv b\pmod{q\cdot y}\) where \(q\), \(r\), and \(y\) are constants and \(q\) is not a divisor of \(b\). We will rewrite this with plain algebra as as we did before to get \(q\cdot r\cdot a= b+f(q\cdot y)\implies q\cdot r\cdot a - f(q\cdot y)=q(r\cdot a - f\cdot y)=b\). However, this is a contradiction because we defined \(q\) and \(b\) such that \(q\) is not a divisor of \(b\). Thus, if the coefficient of the variable and the modulo share a common divisor that the other number in our congruence doesn't, the congruence has no solution.
Next, we will look at \(a\equiv b\pmod{m}\) where \(a\) and \(m\) are relatively prime. In this case, we could try writing out the equations in pure algebraic form, but no solution seems to pop out to us as it did previously when we put the equation in that form (try doing this and thinking about it yourself). Let's try to take a step back and try to think about what we are really trying to accomplish with this "division" we want to define. We want to find a way to make the coefficient of our variable 1 so that we know what values of our variable make our equation hold true. We already know that multiplication works like normal in modular arithmetic, so we want to think if there is some value that we can multiply both sides by to make the desired coefficient congruent to 1. As you will prove in the exercises, it turns out that when the coefficient of the variable is relatively prime to the modulus, there is always such a value. For an integer \(n\), the number \(i\) such that \(ni\equiv 1 \pmod{m}\) is called the inverse of \(n\) in \(\pmod{m}\) and we write \(n^-1=i\) while working in \(\pmod{m}\). You will also find an algorithmic method to obtain any number's inverse in proving the existence of the inverse in the exercise. This method will be expanded upon in the Diophantine Equations lesson. However, for the AMC 10, the best method of finding inverses is usually just to guess.
Note that taking an nth root is similar to division in that there are often multiple solutions, however there is no nice way to find the nth roots other than guess and check.
We did see that one of the divisions produced a true statement, and if we want to solve equations similar \(3x\equiv 6 \pmod{9}\), we will need to be able to "divide." Lets try to think about what division does in order to try to come up with something that acts similarly. First of all, let's look at \(7a\equiv 7\pmod{49}\) means in algebra. using our earlier definitions. Thinking about how it means that both sides of the congruence have the same remainder, we can rewrite our equation as 7a=7+49y (y is integral, but not necessarily positive). Thus, when we divide this equation by 7, we get a=1+7y. In other words, by converting back to modular notation, we get \(a\equiv 1\pmod{7}\). Generalizing what we just saw, we get one form of "division" in modular arithmetic: \(a\equiv b\pmod{m}\) implies\(\frac{a}{c} \equiv \frac{b}{c}\pmod{\frac{m}{c}}\) if \(c\)is a divisor of \(a\), \(b\), \(c\) (otherwise we get fractions and fractions don't work with remainders and modular arithmetic).
Now that we have defined "division" in some cases, what will we do if all of the numbers don't share a common divisor? For example, how do we find all of the solutions to \(14a\equiv 5\pmod{18}\) or \(5a\equiv 6\pmod{9}\).
We will look at cases similar to the former example first; we will look at cases of \(a\equiv b\pmod{m}\) where \(a\) and \(m\) have a common divisor that \(a\) does not have. If this is the case, then we can rewrite the congruence as \(q\cdot r\cdot a\equiv b\pmod{q\cdot y}\) where \(q\), \(r\), and \(y\) are constants and \(q\) is not a divisor of \(b\). We will rewrite this with plain algebra as as we did before to get \(q\cdot r\cdot a= b+f(q\cdot y)\implies q\cdot r\cdot a - f(q\cdot y)=q(r\cdot a - f\cdot y)=b\). However, this is a contradiction because we defined \(q\) and \(b\) such that \(q\) is not a divisor of \(b\). Thus, if the coefficient of the variable and the modulo share a common divisor that the other number in our congruence doesn't, the congruence has no solution.
Next, we will look at \(a\equiv b\pmod{m}\) where \(a\) and \(m\) are relatively prime. In this case, we could try writing out the equations in pure algebraic form, but no solution seems to pop out to us as it did previously when we put the equation in that form (try doing this and thinking about it yourself). Let's try to take a step back and try to think about what we are really trying to accomplish with this "division" we want to define. We want to find a way to make the coefficient of our variable 1 so that we know what values of our variable make our equation hold true. We already know that multiplication works like normal in modular arithmetic, so we want to think if there is some value that we can multiply both sides by to make the desired coefficient congruent to 1. As you will prove in the exercises, it turns out that when the coefficient of the variable is relatively prime to the modulus, there is always such a value. For an integer \(n\), the number \(i\) such that \(ni\equiv 1 \pmod{m}\) is called the inverse of \(n\) in \(\pmod{m}\) and we write \(n^-1=i\) while working in \(\pmod{m}\). You will also find an algorithmic method to obtain any number's inverse in proving the existence of the inverse in the exercise. This method will be expanded upon in the Diophantine Equations lesson. However, for the AMC 10, the best method of finding inverses is usually just to guess.
Note that taking an nth root is similar to division in that there are often multiple solutions, however there is no nice way to find the nth roots other than guess and check.
Exercises
- Prove that there exists an inverse of \(n\) in \(\pmod{m}\) where \(\gcd(m,n)=1\) by showing an algorithm to find the inverse (Hint: what does gcd(m,n)=1 remind you of? How can you rephrase the inverse of a number using a purely algebraic form to relate it?).
- Find the solutions to \(32x\equiv 20\pmod{52}\).
Solution 1
First of all, note that finding an inverse is the same as solving the modular congruence \(i\cdot n\equiv1 \pmod{m}\), or in algebra, \(i\cdot n=x\cdot m + 1 \leftrightarrow i\cdot n -x\cdot m=1\). Recall exercise 2 from the Euclidean Algorithm that we can use the Euclidean Algorithm going backward to express 1 in the form that gives solutions to this equation when \(n\) and \(m\) are relatively prime as given (exercise 2 was a specific example, but can be easily general). If you don't understand this exactly, we will fully explain it in the Diophantine Equations lesson.
Solution 2
We will start by dividing the whole congruence by 4 to get \(8x\equiv 5\pmod{13}\). Next, using the Euclidean Algorithm or by guessing and checking, we get that 8 has an inverse of 5 in \(\pmod{13}\). Thus, multiply both sides of the congruence by 5, we get \(x\equiv 25\equiv 12 \pmod{13}\).