Are there any two integers m and n such that m2 = 3n + 2? In other words, is there an integer m such that if you take m2 and divide by 3, the remainder is 2?
Look at the first 10 square numbers and their remainders when divided by 3:
| Square number | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 |
| Remainder when divided by 3 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
It appears that the remainders follow a pattern, and also that they do not contain any 2's. It's easy to see why this is the case if you consider that every integer m can be written either as 3k, 3k+1, or 3k+2 for some integer k (depending on whether the remainder is 0, 1, or 2 when you divide m by 3). Then when you take these different possibilities and square them:
| m | m2 | Remainder when divided by 3 |
| 3k | 9k2 | 0, since 9 is divisible by 3 |
| 3k+1 | 9k2 + 6k + 1 | 1, since 9k2 and 6k are divisible by 3 |
| 3k+2 | 9k2 + 12k + 4 | 1, since 9k2 and 12k are divisible by 3, and 4 divided by 3 has remainder 1 |
This explains why the remainders follow the (1, 1, 0) cycle, and also why they do not contain any 2's.
This problem is an example of modular arithmetic -- in examining all possible integers, we
looked only at their remainder when divided by 3. For our purposes, the numbers 2, 5, 14, for example,
all had the same important property: they can all be written as 3k+2, i.e. their remainder when divided
by 3 is 2. In terms of modular
arithmetic, we would say that 2, 5, and 14 are equivalent modulo 3 or equivalent mod 3,
written:
2 º 5 º 14 mod 3
These statements are sometimes written incorrectly using the equals sign, e.g. "2 = 5 mod 3". It's usually clear from the context what the writer meant, but technically this usage is incorrect; the correct symbol is the equivalence symbol, " º ".
In fact, it helps to keep in mind what we mean by this symbol: it's not merely that 2, 5, and 14 are numbers that have some common propertly; in the mod 3 universe, "2", "5" and "14" are all different ways of writing the same number -- or rather, they all represent the same class of numbers, the numbers that are equivalent to 2 mod 3. We call this a residue class. The number we divide by before taking the remainder -- in this case, 3 -- is called the modulus.
What we showed above is that for any number m that has remainder 2 when divided by 3, the number
m2 has remainder 1 when divided by 3. In mod 3 arithmetic we would write:
22 º 1 mod 3
It's important to understand exactly what that statement means. You probably already knew that if you take the number 2 and square it, the result (4) has remainder 1 when divided by 3. But the equation above is making a stronger statement than that. It says that any number that is equivalent to 2 mod 3, has a square that is equivalent to 1 mod 3. That property is true for that entire class of numbers, and that class of numbers is represented in the equation by its smallest positive member, the number 2.
On the other hand, when actually working out problems in modular arithmetic, it's easiest just to work with an actual number, e.g. 2, and forget about the fact that it's representing an "entire class of numbers". For example, in figuring out 23 mod 3, we compute that 23 = 8, and 8 º 2 mod 3, so 23 º 2 mod 3.
Similarly, in figuring out 143 mod 3, we could first replace 14 with 2 (because in mod 3 arithmetic, they are "the same number"), and then compute 23 º 2 mod 3.
|
Note: When we say that 2, 5, and 14 represent "the same number" in the mod 3 universe, and
that you can replace any one of them with any other, that
only applies when they are written in the base: for example, 517 º 1417 mod 3.
That does not apply when they are written in the exponent -- for example, you cannot assume that
25 º 214 mod 3, and in fact that statement is wrong.
The reason is a bit tricky to understand, but basically: when 14 is written in the base, it really means "the class of all numbers equivalent to 14 mod 3" (and hence also means "the class of all numbers equivalent to 2 mod 3"). But when 14 is written in the exponent, it actually means what 14 always means when written in an exponent -- i.e. "multiply this number by itself 14 times". And that's not the same thing as multiplying a number by itself 5 times, or 2 times, so you cannot interchange 2, 5, and 14 when they're written in the exponent. |
Each negative integer is also equivalent to some positive integer mod 3 -- but be careful when working these out. For example, -5 is not equivalent to 2 mod 3. -5 is equivalent to 1 mod 3 -- because the nearest multiple of 3 below -5 is the number -6, and -5 is 1 greater than -6.
This is easier to visualize by looking at this table, which shows all the multiples of 3 in bold:
| ... | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
The numbers which are equivalent to 1 mod 3, are just those numbers that are 1 greater than
a multiple of 3, shown in bold here:
| ... | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
Like the multiples of 3, the numbers equivalent to 1 mod 3 are, of course, spaced evenly apart. But the important thing to notice is that the negative numbers in this class (-2, -5, etc.) are not the same as the positive numbers in this class (1, 4, 7, etc.).
The numbers that exist in mod M arithmetic are 0, 1, 2, 3, ... M-1. For example, in mod 5 arithmetic, the different numbers are represented by 0, 1, 2, 3, and 4. But 5 is not considered a separate number because 5 º 0 mod 5. (Both 5 and 0 have the same remainder when divided by 5: the remainder is 0.)
In mod 5 arithmetic, 4 + 4 º 3 mod 5, because of course 4 + 4 = 8, and if you divide 8 by 5, the remainder is 3. In general, addition and subtraction problems can be solved the same way.
Multiplication is straightforward as well. 4*3 º 2 mod 5, because 4*3 = 12, and 12 º 2 mod 5.
In all such cases, if you are adding, subtracting, or multiplying numbers that are larger than the modulus M, you can replace them with a smaller equivalent number before carrying out the addition, subtraction, or multiplication. For example, when working out 14*18 mod 5, we could compute that 14*18 = 252 and 252 º 2 mod 5. But it's easier to see that 14 º 4 mod 5, and 18 º 3 mod 5, and 4*3 = 12 and 12 º 2 mod 5.
Sometimes it can simplify your calculations in modular arithmetic to replace one
number with a smaller negative number. For example, suppose you wanted
to compute 33*32 mod 35. You could work out that 33*32 = 1056 and that 1056
has remainder 6 when divided by 35. But notice that:
33 º -2 mod 35
32 º -3 mod 35
Therefore,
33*32 º (-2)*(-3) º 6 mod 35
which is much easier to work out by hand.
Division is not as straightforward. Going back to the very basics: what does "division" mean in normal arithmetic? When we say 12 divided by 4 equals 3, we mean that there is a number 3 such that 3*4 = 12.
But you run into problems extending this to modular arithmetic. Suppose you are working in mod 10 and you want to compute 4 divided by 2. In other words, find a number x such that 2*x º 4 mod 10. The obvious answer, x=2, fits the equation. But there is another number, 7, such that 2*7 º 14 º 4 mod 10. So division is not uniquely defined, because there are two numbers that can multiply by 2 to give 4.
Suppose you had worked out on paper that 3269 x 423 = 1382785 and wanted to check your work. Immediately, you could see that if the last digit of the first number is 9, and the last digit of the second number is 3, then since 9 x 3 = 27, the last digit of their product must be 7. So the result above must be wrong.
This is an example of mod 10 arithmetic -- you are using the fact that if A*B = C, then A*B º C mod 10. In other words, if A*B = C, then if you take the remainder of A divided by 10 and take the remainder of B divided by 10 (in this case, 9 and 3), multiply them (27) and again take the remainder divided by 10 (7), the result should equal the remainder when C is divided by 10. If not, then the result you got for C is wrong.
However, mod 10 arithmetic obviously isn't very useful for checking your work, because it can only catch errors in the last digit. Mod 9 arithmetic is a little more work, but is far more useful because it checks the correctness of the entire answer, and is usually right.
Statement 1: For each positive integer A, if B is the sum of the digits in A,
then A and B have the same remainder when divided by 9. In other words,
A º [sum of digits in A] mod 9
For example: 761 º 5 mod 9. And if you add up the digits of 761, 7+6+1 = 14, and 14 º 5 mod 9, the same result.
Why it works: First observe that of the numbers 0, 9, 99, 999, 9999, 99999 etc., each of them is perfectly divisible by 9, so they are all equivalent to 0 mod 9. So if we add 1 to each of those numbers and get the numbers 1, 10, 100, 1000, 10000, etc., each of those numbers must be equivalent to 1 mod 9. i.e. the remainder of 1000000000 when divided by 9 is 1 (because 1000000000 is 1 greater than 999999999).
So the number 4329 for example could be written as:
(4 * 1000) + (3 * 100) + (2 * 10) + 9
But remember in modular arithmetic, we can substitute any numbers that are equivalent to each
other (as long as we're not substituting them in the exponent). So for each of 1000, 100, and 10,
we can substitute just 1, because they are all equivalent to 1. So:
(4 * 1000) + (3 * 100) + (2 * 10) + 9 º 4 + 3 + 2 + 9 mod 9
Here, the value on the left is the original number A, and the value on the right is the sum of the digits of A.
Algorithm to find the remainder of a positive number when divided by 9:
For example, to find 829 mod 9, we find 8 + 2 + 9 = 19. Then take the digits of 19 and add them: 1 + 9 = 10. Then take the digits of 10 and add them: 1 + 0 = 1. So the remainder of 829 º 1 mod 9.
The reason this works is that each time you add up the digits of a number and take the result, you are preserving the value of the number mod 9. So if you repeat this process until you're left with a 1-digit number, the value mod 9 will still be the same.
So, suppose you had worked out on paper that 3269 * 425 = 1389325, and you wanted to check the result using mod 9 arithmetic:
The results in bold, "4", match, so mod 9 checking did not find any errors.
If mod 9 checking doesn't find an error, that doesn't guarantee the answer is correct. If we had transposed two digits and written 1398325 instead of 1389325, mod 9 checking would have found the same value for the sum of the digits and would not have detected a problem with the answer. However, usually if you make an error in working out the problem, the value of the answer mod 9 will be some random value, and there is only a 1 in 9 chance that the random value will accidentally be the "correct" value such that mod 9 checking doesn't catch the error.
A well-known mathematical magic trick works as follows:
The key to this trick is mod 9 arithmetic. We know from previous results that the value of a number
mod 9 depends on the sum of its digits. Since X and Y contain the same digits, the are both
equilvant to the same value n mod 9. This means that
X - Y º n - n º 0 mod 9
In other words, Z is divisible by 9.
Since Z is divisible by 9, then the sum of its digits must also be divisible by 9. So when your friend reads out the digits, add them up and find the missing digit that is needed to make the sum divisible by 9.
For example: your friend picks 23985 and 85293. Their difference is 61308. Your friend crosses out the 1 and reads out the digits "3, 0, 8, 6". You add these up to get 17. The next multiple of 9 is 18, so the sum of the digits must be 18 and therefore the missing digit must be 1.
You run into a problem, though, if the digits that your friend reads to you add up to a multiple of 9, because then the missing digit could be 0 or 9. For example, if your friend had crossed out the 0 in 61308 and read out 3, 8, 1, 6, those add up to 18, so a missing digit of 0 or 9 would both give a result whose total is divisible by 9. When mathematician Arthur Benjamin performed this trick on the Paul Daniels magic show in England, Paul Daniels did in fact cross out a zero in his result, so Arthur told him to "concentrate" on the missing number and then complained that it felt like Paul was just "thinking of nothing", to which Paul laughed and said he was indeed "thinking of nothing", so Arthur figured out the missing digit was 0. (I don't know what he would have done if the missing digit actually had been 9, since then the joke really would have bombed!) The usual way to deal with this though is to say that your friend is not allowed to cross out the digit 0.
Here's another version with a little more flair:
Suppose you wanted to find the value of 12346 mod 10 -- in other words, the last digit of the number 12346. First, remember that even in mod 10, you cannot replace the exponent with its mod 10 equivalent, i.e. you cannot substitute 6 for 346.
You can, however, replace the base with its mod 10 equivalent. So 12346 º 2346 mod 10.
The key to the next step is that powers of 2 follow a cycle in mod 10. We know that:
21 º 2 mod 10
22 º 4 mod 10
23 º 8 mod 10
24 º 6 mod 10 (because 24 = 16, and 16 º 6 mod 10)
After this, the values of 2n mod 10 begin to repeat themselves. Since
24 º 6 mod 10, that means
25
º 24*2 (using the usual laws of exponents)
º 6*2 (replacing 24 with 6 since we showed they were equivalent)
º 12
º 2 mod 10
And since 25 º 2 mod 10, we're back to the first value we started with for 21. Then 26º 2*2 º 4 mod 10, which is the same as the value for 22, and so on. The values of 2n mod 10 follow a cycle, as you can see in the bottom row of the following table:
| Number in 2n form | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 210 | 211 | 212 | ... |
| Value | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | ... |
| Mod 10 equivalent (i.e., remainder when divided by 10) | 2 | 4 | 8 | 6 | 2 | 4 | 8 | 6 | 2 | 4 | 8 | 6 | ... |
There's actually a straightforward logical argument why the numbers an mod b must repeat themselves in a cycle for successive values of n, for any pair of numbers a and b:
So, back to the original problem: finding 2346 mod 10. In the repeating table above, we showed
that for all n divisible by 4,
2n º 6 mod 10. Therefore, 2344 º 6 mod 10
since 344 is divisible by 4. So
2346
º 2344*22 (by usual laws of exponents)
º 6*22 (since we showed 2344 º 6 mod 10)
º 24 º 4 mod 10
Note that to solve this problem, we did in fact do modular arithmetic with the exponent -- we know that the values of 2n repeated themselves every 4 values, so what we cared about was the remainder when 346 was divided by 4. But even though our original problem was in mod 10, when we simplified the exponent, we looked at its value mod 4, not mod 10. So in general, when finding an mod b for large values of n, you will often do modular arithmetic with the exponent n, but the modulus is not b. Instead, the modulus is the length of the cycle that it takes for values of an mod b to repeat themselves.
Sometimes the repeating cycle does not include the number that you started with. Consider the bottom row of this table, which shows the values of 2n mod 12:
| Number in 2n form | 21 | 22 | 23 | 24 | 25 | 26 | 27 | ... |
| Value | 2 | 4 | 8 | 16 | 32 | 64 | 128 | ... |
| Mod 12 equivalent (i.e., remainder when divided by 12) | 2 | 4 | 8 | 4 | 8 | 4 | 8 | ... |
In the bottom row, once the {4, 8} cycle begins, it repeats forever, but the number 2 is never seen again after the first occurrence. However, this pattern can still be used to find values of 2n mod 12 for large values of n, since the pattern always holds after the first exception, 21. You can still observe that for all n other than 1, 2n º 4 mod 12 if n is even, and 8 mod 12 if n is odd.
And of course if an º 0 mod b for any value of n, then
for any larger exponent m > n, am º 0 mod b as well. For
example, consider the values of 6n mod 24:
| Number in 2n form | 61 | 62 | 63 | 64 | 65 | ... |
| Value | 6 | 36 | 216 | 1296 | 7776 | ... |
| Mod 24 equivalent (i.e., remainder when divided by 24) | 6 | 12 | 0 | 0 | 0 | ... |
Once you hit 63 º 0 mod 24, the bottom row will always be 0 for any exponent greater than 3. The reason of course is that each value is obtained by multiplying the previous value by 6, and 0 multiplied by anything is always 0.
Sometimes, the previous method will require too many steps to be practical. For example, suppose you want to find the value of 717 mod 34.
You could write out a table to find when the values of 7n mod 34 begin to repeat themselves:
| Number in 7n form | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 710 | 711 | 712 | 713 | 714 | 715 | 716 | 717 |
| value mod 34 | 7 | 15 | 3 | 21 | 11 | 9 | 29 | 33 | 27 | 19 | 31 | 13 | 23 | 25 | 5 | 1 | 7 |
To obtain each value, we take the previous value, multiply by 7, and find the remainder mod 34. However, we have to go all the way to 717 before we see a repeat value. And by the time we find 717 we've solved the problem, so looking for a repeating cycle didn't even save us any work!
There is a shorter method which, for reasons I haven't been able to track down, is known as the "Russian peasant algorithm". Observe that the exponent, 17, is close to 16 = 24. So if we can calculate 716 mod 34, we can easily calculate 717 mod 34, by multiplying it by another 7.
To find 716 mod 34, we can start with 7 mod 34 and then square it repeatedly, keeping in mind the familiar law of exponents that abc = (ab)c:
72 º 49 º 15 mod 34
74 º (72)2 º 152 º 225 º 21 mod 34 (by substituting the value 72 º 15 mod 34 that we obtained in the previous step)
78 º (74)2 º 212 º 441 º 33 mod 34 (by substituting the value 74 º 21 mod 34 that we obtained in the previous step)
Here we use a technique that we mentioned earlier: replace a number with a smaller negative number that is equivalent. In this case, 33 º -1 mod 34, so:
78 º 33 º (-1) mod 34
which means:
716 º (78)2 º (-1)2 º 1 mod 34 (by substituting the value 78 º -1 mod 34 that we obtained in the previous step)
and now, using 716 to get 717:
717 º 716*7 º 1*7 º 7 mod 34
Using this method, there were only 5 steps where we had to multiply two numbers and divide by 34. If
we had blindly attempted to solve the problem by finding a repeating cycle for 7n, it would
have taken 16 steps.
You can use this method to find values when the exponent is a product of powers of 2 and 3 as well, or close to one. For example, suppose you wanted to compute 749 mod 34. You might be distracted by noticing that 49 = 72, but that's actually irrelevant. What's helpful is that 49 = 24*3 + 1, which means these steps would be fastest (note that in each step, you are only using values obtained in previous steps):
Often it is a matter of guesswork to find the fastest route to compute a given exponent. For example, to compute 756 mod 34, this route would be efficient:
So, when finding an mod b for large values of n, the Russian peasant algorithm is useful when: