Terms: TODO!
Modular arithmetic
We can visualize the integers Z as a two-sided infinite sequence of numbers:
⋯→−3→−2→−1→0→1→2→3→⋯
The basic idea of modular arithmetic is to take this sequence and turn it into a cycle:
The above figure represents one of the most common examples of modular arithmetic: arithmetic on a clock. 5 hours after 11 o’clock is not 16 o’clock but rather 4 o’clock. As such, starting at 11 in the figure and following the arrows 5 times lands us on 4 instead of 16.
The only difference is that we have chosen to use 0 to represent 12 o’clock rather than 12.
Warning: this section is relatively dense and arcane!
Fix n≥2, the size of our cycle. Let M be a set of size n of elements {0ˉ,1ˉ,…,n−1}. These elements represent the numbers on our cycle.
This gives rise to a natural operation ⋅ˉ:{0,…,n−1}→M which takes 0 to 0ˉ and 1 to 1ˉ, etc. We extend this operation onto Z∖{0,…,n−1} as xˉ:=mod(x,n). For instance, if we fix n=3, we have:
−2−10ˉ1ˉ2ˉ3ˉ4ˉ5ˉ=1ˉ=2ˉ=0ˉ=1ˉ=2ˉ=0ˉ=1ˉ=2ˉ
Define addition as aˉ+bˉ:=a+b. This gives, for instance, for n=7 that 4ˉ+6ˉ=4+6=10=mod(10,7)=3ˉ.
Define multiplication similarly.
For given n, the set M is usually denoted Z/n or Z/nZ.
(Z/n,+) is a
group
(Z/n,⋅) is not a
group (since
0ˉ has no inverse), but
can be modified to form one.
