Modular arithmetic and functions
Question: find numbers x such that ax=1 (modulo 11) for a=1,2,3,4,5,6,7,8,9,10.
This is an interesting question. The letters have been chosen to suggest that you are solving an equation for x: ax=1.
In normal arithmetic you would instantly say x=1/a, but of course if x has to be an integer then there is no solution.
The Greeks were very enthusiastic about integers, but realised that integers couldn't solve everything and that's how they came across the rationals. However, in modulo arithmetic this equation can have an integer solution, and that is what you find when you answer this question.
Modulo arithmetic features a lot in questions about functions and relations because it is an example of a function which maps from Z, the set of all integers, into a finite set S={0,1,2 .. n-1}.
The interesting thing about the map is that it preserves addition and multiplication, so that you can define these operations on S and they remain consistent. If we call the function m,
m(a) x m(b) = m(ab)
If you want to prove things about numbers mod n one way which will always work is to go back to the domain of normal integers.
If a number is b mod n then it is kn+b for some integer k.
You can also look at the "times table" modulo n. As S is a finite set you can enumerate every possible multiplication. For example, the times table mod 11 is as follows:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 0 | 2 | 4 | 6 | 8 | 10 | 1 | 3 | 5 | 7 | 9 |
| 3 | 0 | 3 | 6 | 9 | 1 | 4 | 7 | 10 | 2 | 5 | 8 |
| 4 | 0 | 4 | 8 | 1 | 5 | 9 | 2 | 6 | 10 | 3 | 7 |
| 5 | 0 | 5 | 10 | 4 | 9 | 3 | 8 | 2 | 7 | 1 | 6 |
| 6 | 0 | 6 | 1 | 7 | 2 | 8 | 3 | 9 | 4 | 10 | 5 |
| 7 | 0 | 7 | 3 | 10 | 6 | 2 | 9 | 5 | 1 | 8 | 4 |
| 8 | 0 | 8 | 5 | 2 | 10 | 7 | 4 | 1 | 9 | 6 | 3 |
| 9 | 0 | 9 | 7 | 5 | 3 | 1 | 10 | 8 | 6 | 4 | 2 |
| 10 | 0 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
In this table every number has a 1 somewhere in a row and column, and so every number has a multiplicative inverse. These are the numbers that the question is asking you to find. This is not always the case, it depends if the number has a common factor with n.
Another way of thinking about modular arithmetic is as arithmetic in base n (11 in this case) where you keep the units value and throw away the rest.
So for example, in base 11, 9x5=41. The 1 is what appears in the table above. The 4 is the k when we say that the number is of the form 11k+a, but we don't need it for modulo arithmetic.
Every column is actually a permutation of the numbers {0 .. N-1}. Some computer random number generators use this - they just pick a pair of mutually prime large numbers a and b, and each new random number is created by multiplying the last one by a mod b.