Modular Arithmetic

An introduction to the fundamentals
The Basics
Modular Arithmetic is an incredibly important aspect of practically all asymmetric cryptography. A common way to refer to it is as clock arithmetic - imagine it's eleven o'clock right now. Three hours later it'll be two o'clock, right? Well we do the same thing in modular arithmetic:
11+3=14≡2mod  1211 + 3 = 14 \equiv 2 \mod 1211+3=14≡2mod12
​Essentially we take the sum of 111111
 and 333
 and then divide by 121212
 and keep the remainder. Here, the 121212
 is called the modulus. The triple equals ≡\equiv≡
 denotes a congruence, and we say 141414
 is congruent to 222
 mod  12\mod 12mod12
.
We can think of this another way and say that two numbers aaa
 and bbb
 are congruent modulo mmm
 if their difference a−ba-ba−b
 is divisible by mmm
. For example, 262626
 and 222
 are congruent modulo 121212
 because  26−2=2426-2=2426−2=24
 which is divisible by 121212
.
Modular (Multiplicative) Inverses
In normal maths, every number has an inverse - another number that, when multiplied with them, equals 111
. In maths terms, we would say that for every number aaa
 there is another bbb
 where ab=1ab=1ab=1
. Generally, we can say that b=1ab=\frac{1}{a}b=a1​
 as that fits the equation - the inverse of 777
, for example, is 17\frac{1}{7}71​
.
In modular arithmetic, there are no fractions. Instead of finding bbb
 such that ab=1ab=1ab=1
, we instead find bbb
 such that ab≡1mod  mab \equiv 1 \mod mab≡1modm
. This means that for different values of mmm
 there are different inverses for aaa
. For example, the inverse of 3mod  53 \mod 53mod5
 is 222
, because 3⋅2=6≡1mod  53 \cdot 2 = 6 \equiv 1 \mod 53⋅2=6≡1mod5
. This inverse is called the modular multiplicative inverse. We can therefore say that 3−1≡2mod  53^{-1} \equiv 2 \mod 53−1≡2mod5
.
Yet not every number aaa
 has an inverse modulo mmm
 - for example, 222
 has no inverse modulo 666
. Why? This is because gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1
. Let's prove this in the general case and see why that is.
Proof 
Assume there is bbb
 such that a⋅b≡1mod  ma \cdot b \equiv 1 \mod ma⋅b≡1modm
. This would mean that there also exists ccc
 such that ab=cm+1ab = cm + 1ab=cm+1
 and therefore ab−cm=1ab - cm = 1ab−cm=1
. It follows therefore that both sides must be divisible by gcd(a,m)gcd(a,m)gcd(a,m)
, meaning gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1
.
As a result, if there is an inverse of aaa
 modulo mmm
, such an inverse can only exist if gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1
 □\square□
​
An Intuitive Approach
If you're struggling to visualise this proof, think back to the previous example of 222
 having no inverse modulo 666
. Why is this? Well, regardless of how much you multiply 222
 with, the sequence will go 0,2,4,0,2,4,...0, 2, 4, 0, 2, 4, ...0,2,4,0,2,4,...
 and loop around because it is a factor of 6.
Actually, the fact that a number it is not coprime with the modulus shows that it can never have an inverse. Again, why? Think about it this way: if they have a common factor, the remainder when one is divided by the other will also have that factor - and therefore not be 111
. If we choose 444
 rather than 222
, we can see this - if there is a common factor (as there is of 222
 in this case) there is no value xxx
 for which 4x4x4x
 will return 111
 modulo 666
. Any number you can multiply 444
 by will always give a remainder divisible by 222
 when divided by 6.
I suggest you spend some time reflecting on this fact, as it is a very important result.
Uses
The uses of modular multiplicative inverses are similar to those of regular inverses - as division. Normally, if we divide two numbers, we can treat the number being divided by as multiplying by its inverse.
8÷2=8⋅2−1=8⋅12=48 \div 2 = 8 \cdot 2^{-1} = 8 \cdot \frac{1}{2} = 48÷2=8⋅2−1=8⋅21​=4
​We can use the modular multiplicative inverse the same way - say we want to divide 333
 by 222
, modulo 777
:
3÷2≡3⋅2−1≡3⋅4≡12≡5mod  73 \div 2 \equiv 3 \cdot 2^{-1} \equiv 3 \cdot 4 \equiv 12 \equiv 5 \mod 7 \\
3÷2≡3⋅2−1≡3⋅4≡12≡5mod7
Note that 444
 is the inverse of 222
 as 2⋅4≡1mod  72 \cdot 4 \equiv 1 \mod 72⋅4≡1mod7
.
And just like that we realise that dividing 333
 by 222
 modulo 777
 gives us 555
.
Fundamentals - Previous
Divisibility, Factors and Euclid's Algorithms
Next - Fundamentals
Rings, Fields and Euler's Totient Function
Last modified 4mo ago