Cryptography Reference
In-Depth Information
FIGURE 4.4
Definition
Note that the solution to ax 1 (mod m ) exists only when a is relatively prime to m ,
since ( a , m ) must divide 1. When such solutions exist, there is only one incongruent solu-
tion modulo m . A solution to such a congruence is called an inverse of a modulo m , and
we write such an inverse as a .
E XAMPLES .
x
x
• 19 is an inverse of 4 modulo 25, since
19 (mod 25) solves 4
1 (mod 25). (Verify.)
Thus, we write 4
19 (mod 25).
x
x
• A solution to 7
1 (mod 8) is
7 (mod 8). Thus, 7 is its own inverse modulo 8, or
we can write 7
7 (mod 8). This is easily checked, since 7
7
7
7
49
1 (mod
8).
• Now, consider the congruence 9
x
1 (mod 15). Note that 9 has no inverse modulo 15,
since 9 and 15 are not relatively prime.
EXERCISES
1.
Find all integer solutions to the following linear diophantine equations, if any exist:
a.
42
x
+ 30
y
= 20
Search WWH ::




Custom Search