Cryptography Reference
In-Depth Information
It is not obvious what the answer is, or indeed if there is an answer at all. One
rather crude way of finding a solution is to try out all of the numbers mod 7 until
we find out if there is an answer:
2
×
0
=
0mod 7
2
×
1
=
2mod 7
2
×
2
=
4mod 7
2
×
3
=
6mod 7
2
×
4
=
1mod 7
2
×
5
=
3mod 7
2
×
6
=
5mod 7
.
So the modular inverse of 2 is 4. In other words, 2
−
1
=
4mod 7. We can also
search for the multiplicative inverse of 6 modulo 10:
6
×
0
=
0mod 10
6
×
1
=
6mod 10
6
×
2
=
2mod 10
6
×
3
=
8mod 10
6
×
4
=
4mod 10
6
×
5
=
0mod 10
6
×
6
=
6mod 10
6
×
7
=
2mod 10
6
×
8
=
8mod 10
6
×
9
=
4mod 10
.
So, there is no multiple of 6 that is equal to 1 mod 10. Thus 6 does not have an
inverse mod 10. In other words, the modular inverse 6
−
1
mod 10 does not exist.
The previous examples raise the interesting question: when does a number have
a multiplicative inverse modulo another number? This is essentially the question:
when can we divide in modular arithmetic? It turns out that a number has an
inverse modulo another number precisely when the two numbers are coprime.
Thus, for example, gcd(2
,
7)
=
1, which means that 2 and 7 are coprime, and
thus 2
−
1
mod 7 exists. Similarly, gcd(5
1, which means that 5 and 17 are
coprime, and thus 5
−
1
mod 17 exists. On the other hand, gcd(6
,
17)
=
2, which
means that 6 and 10 are not coprime, and thus 6
−
1
mod 10 does not exist.
,
10)
=
