So far, we have introduced the basics of modular arithmetic as far as simple operations and solving 1 variable linear equations goes. We will now look at how modular arithmetic can be used in harder problems which have a less obvious use or solution.
Sample Problem 1. If a class is arranged into rows of 10 people, there are 3 people left over. If the same class is arranged into rows of 13 people, there are 8 people left over. What is the minimum number of people that could be in the class?
For this problem, you could solve it fairly easily by guessing and checking. However, we will instead find a way to use modular arithmetic to systemically find a solution so that when working with more constraints (more than just the 2 given) and guessing becomes harder, you will have a way to solve the problem. In addition, it would be nice if we could find all of the solutions. To start, we will let the number of people in the class be \(p\). Thus, writing the information we have using modular arithmetic, we have \(a\equiv 3 \pmod{10}\) and \(a\equiv 8 \pmod{13}\). It doesn't immediately appear obvious what to do hear, so lets think about what ideas we may have. Let's think about what we would do if we anted to guess and check to find the solution to this problem. We would probably start with 3 and check if it satisfies the \(\pmod{13}\) condition (or start with 8 and check the \(\pmod{10} condition, it doesn't really matter\)). Because this doesn't work, we would repeatedly add 10 to the 3 to keep the \(\pmod{10}\) condition satsified and continually check if the number we get satisfies the \(\pmod{13}\) condition until we found a number that did. In other words, we would have tested numbers in the form of \(a=3+10x\) to see if they are congruent to \(8\pmod{13}\). Well, we already know how to solve linear congurences, so why don't we just plug in the restriction \(a=3+10x\) into our \(a\equiv 8\pmod{13}\)? We can, and it will get us exactly to where we wanted doing pretty much the same thing as we did when guessing and checking just without the guessing and checking. To finish of this problem, we plug our new expression in for a to get \(10x+3\equiv 8\pmod{13}\). We then subtract 3 from both sides to get \(10x\equiv 5\pmod{13}\), and because 10 and 13 are relatively prime we can find the inverse of 10 in \(\pmod{13}\) by guessing if the numbers are small or using the Euclidean Algorithm (usually better for big numbers) to get \(40x\equiv 20\pmod{13}\implies x\equiv 7\pmod{13}\). Now, be careful not to just assume the smallest value we could get is 7, because that would be wrong. Remember that we are trying to minimize \(a\) not \(x\). From here, we can write \(x=7+13x\) from our modular equation, and plugging this into \(a=10x+3\), we get \(a=130x+73\), or writing this in modular form, we get that our solutions are integers that satisfy \(a\equiv 73 \pmod{130}\) (note that \(\pmod{130}\) makes sense because it doesn't change the value of a number in \(\pmod{10}\) or \(\pmod{13}\) to add 130). Thus, our answer is 73.
By looking at the process that we just discovered we would use to solve a system of two linear congruence's, we can think about what we can conclude from trying to generalize it. Using our knowledge of inverses of a number in a modulo existing if and only if the inter is relatively prime to the modulo, you should be able to see that by using our previous process we can find a solution to any system of 2 linear congruences as long as the moduli of the two congruence are relativity primed. In addition, the solution will be with a modulus equal to the product of the moduli of the two congruences. This fact (not the solution process) is called the Chinese Remainder Theorem.
By looking at the process that we just discovered we would use to solve a system of two linear congruence's, we can think about what we can conclude from trying to generalize it. Using our knowledge of inverses of a number in a modulo existing if and only if the inter is relatively prime to the modulo, you should be able to see that by using our previous process we can find a solution to any system of 2 linear congruences as long as the moduli of the two congruence are relativity primed. In addition, the solution will be with a modulus equal to the product of the moduli of the two congruences. This fact (not the solution process) is called the Chinese Remainder Theorem.
Sample Problem 2. How would we solve a system of three linear congruences using the process we just made? How about a system of more than three linear congruences? How does the Chinese Remainder Theorem work with more than 2 congruences?
Thinking about how we solve a system of more than two linear equations, we can conclude that we can just solve the congruences by taking 2 at a time. In other words, we take any two congruences, solve them to find one congruence that represents the solutions. We then take the new congruences and a another congruence, solve those two congruences, and so on until we have only one congruence left that satisfies all of our original ones. Thus, we can fairly easily generalize the Chinese remainder therefrom by applying it to each system of two congruences that we work through to see that we will get a solution if the moduli of all of the congruences are relatively prime, and in that case the modulus of the solution will be the product of all of the moduli of our individual congruences. Now, solving all of these congruences using this method may seem very tedious, and it is. Thus, you won't have to solve any systems with a bunch of congruences on the AMC 10 (or else you're probably doing the problem wrong).
Sample Problem 3. Find the units digit of \(3^{123}\). How can you relate this to modular arithmetic.
You probably know how to solve this problem without modular arithmetic. You would probably start by writing out the sequences of the units digits starting with \(3^1\) to get 3, 9, 7, 1. Thus,you would probably think that we can keep on subtracting fours from the exponent (dividing by \(3^4\), which has a units digit of 1) to get that \(3^{123}\) has the same units digit \(3^3\), so our answer is 7 (we could also see this as saying that 123 has a remainder of 3 when divided by 4).
Next, we will relate this to modular arithmetic. Thinking how to express a units digit, we realize that the units digit of a number is equivalent to that number \(\pmod{10}\). Thinking about what we doing in terms of modular arithmetic again, we see that we found \(3^4\equiv 1\pmod{10}\) as the lowest exponent of 3 that is congruent to 1 in \(\pmod{10}\), so thus we factored out \(3^4\) from \(3^{123}\) repeatedly. Now, this may not initially, but we can generalize this beyond the units digit of a number. We call the smallest number \(o\) such that \(n^0\equiv 1\pmod{m}\) the order of n \(\pmod{m}\). The concept of the order of a number in a mod will pop up again in higher level number theory that is not necessary for the AMC 10, but we will give a brief introduction to these ideas in the exercises.
Next, we will relate this to modular arithmetic. Thinking how to express a units digit, we realize that the units digit of a number is equivalent to that number \(\pmod{10}\). Thinking about what we doing in terms of modular arithmetic again, we see that we found \(3^4\equiv 1\pmod{10}\) as the lowest exponent of 3 that is congruent to 1 in \(\pmod{10}\), so thus we factored out \(3^4\) from \(3^{123}\) repeatedly. Now, this may not initially, but we can generalize this beyond the units digit of a number. We call the smallest number \(o\) such that \(n^0\equiv 1\pmod{m}\) the order of n \(\pmod{m}\). The concept of the order of a number in a mod will pop up again in higher level number theory that is not necessary for the AMC 10, but we will give a brief introduction to these ideas in the exercises.
Example
- Show that, for integers x, y, and z such that x is relatively prime to m and \(x\not\equiv y \pmod{m}\), \(xz\not\equiv xy \pmod{m}\).
- Use the previous statement to come up with an alternate proof for the Chinese Remainder Theorem.
- We call the number of integers less than \(n\) that are relatively prime \(n\) \(\phi(n)\). Prove that \(a^\phi(m)\equiv 1\pmod{m}\) for \(a\) relatively prime to \(m\).
Solution 1
We will prove this by showing that \(xz\equiv xy \pmod{m}\) for x relatively prime to m implies\(z\equiv y \pmod{m}\) (the contrapositive of a statement is logically equivalent to the statement). To prove this all that we have to to is remember that x has an inverse in \(\pmod{m}\) because x and m are relatively prime, so we get \(xz\equiv xy \pmod{m}\implies x^{-1}xz\equiv x^{-1}xy \pmod{m}\implies z\equiv y \pmod{m}\) as desired.
Solution 2
We wish to prove that there is a solution to the system \(x\equib b\pmod{m}\), \(x\equiv c\pmod{t}\) for m relatively prime to t. We will rewrite the first condition as \(x=b+y\cdot m\) for some integer y. Next, note that using the previous exercise, we can see that \(y\cdot m\) changes value \(\pmod{t}\) whenever y changes in value. In other words, as y ranges over all residues in \(\pmod{t}\), the value of \(y\cdot m\) same twice. Thus, we can conclude that the value of \(y\cdot m\) must also range over all residues \(\pmod{m}\). Thus, for some value of y, \(y\cdot m\) will assume the value of \(c-b\), thus showing that we do indeed have one solution that is less than \(m\cdot t\) (the greatest residue \(pmod{t}\) is t-1). Thus, any remaining solutions must be the one solution that we found plus a multiple of \(m\cdot t\)(as the number we add must be a multiple of both moduli).
solution 3
First of all, note that when two numbers that are both relatively prime to the modulus are multiplied, the result must also be relatively prime to the modulus (if this isn't clear try writing it out in non-modular notation and use a proof by contradiction). Thus, if take the set of integers relatively prime to and less than modulus \(m\),multiply each by a, and take the remainder of each when divided by \(m\), we simply get a rearrangement of the set of numbers relatively prime to and less than m (by exercise 1, no two distinct integers can produce results congruent \pmod{m} when multiplied by a, but, as we said earlier, each product must also produce a residue relatively prime to the modulus). Thus, we have \((ar_1)(ar_2)\ldots (ar_{\phi(m)})\equiv r_1r_2\ldots r_{\phi(n)\pmod{m}) where each \(r_i\) is a distinct residue \(\pmod{m}) that is relatively prime to m. However, because \(r_i\) is relatively prime to m, it also has an inverse. Thus, multiplying by each side by in the inverse of each \(r_i\) we get \(a^\phi{m}\equiv 1\pmod{m}\). Note that this isn't necessarily the order of a, as there could be a smaller power congruent to 1, but the order must be a divisor of \(\phi(m)\) (try to prove this).