3.5. linear congruence .
Definition 3.5.1. A linear congruence is a congruence of the form ax ≡
b(mod m), where a, b, and m are fixed integers and m > 0. One may Algebra -homework-soft/multiplying-fractions/free-download-math--solving.html">solve for x
by finding an inverse of a modulo m, if an inverse exists.
Example 3.5.1. Solve the linear congruence
2x ≡ 7(mod 15) for x.
Solution: An inverse of 2 modulo 15 is 8. Thus
(8 · 2)x ≡8(7)(mod 15)
x ≡56(mod 15)
x ≡11(mod 15)
Discussion
Solving a linear congruence, ax ≡ b ( mod m), is very similar to solving an
ordinary
linear equation ax = b. We can solve for x in the linear equation by multiplying
through by the multiplicative inverse 1/a of a, provided a ≠ 0. In a similar
manner,
we can solve a linear congruence, ax ≡ b(mod m), provided a has a multiplicative
inverse a' modulo m. Then x ≡ a'ax ≡ a'b(mod m). To get a canonical choice for x,
we would reduce a 'b modulo m.
Caution. DO NOT express the solution to a linear congruence ax ≡ b(mod m) as
, as you would the solution to the linear equation ax = b. We have previously
cautioned against using fractional notation when doing integer arithmetic , but,
in the
world of integers modulo m, they are expressly forbidden.
3.6. Criterion for Invertibility mod m.
Theorem 3.6.1. Suppose a and m are integers and m > 1. Then a has an inverse
modulo m if and only if GCD(a,m) = 1. Moreover, if GCD(a,m) = 1, then a has a
unique inverse, a', with 0 ≤ a' < m.
Proof. GCD(a,m) = 1 if and only if there are integers s and t such that 1 =
as + mt. This is true if and only if there is an integer s such that 1 ≡ as(mod
m).
By definition, this is true if and only if a has an inverse, namely s, modulo m.
Discussion
Theorem 3.6.1 provides us with the conditions required for
inverses modulo m to
exist: For a to have an inverse modulo m, a and m must be relatively prime. The
proof of the “moreover” part is complete once you solve the following exercise.
Exercise 3.6.1. Prove that if ab ≡ 1(mod m) and b ≡ c(mod m), then ac ≡
1(mod m).
3.7. Example 3.7.1. We can use the Euclidean Algorithm and the division
algorithm
to find the “unique” inverse of a modulo m.
Example 3.7.1. Find the inverse of 8 modulo 35.
1. Apply the Euclidean Algorithm.
35 = 4(8) + 3
8 = 2(3) + 2
3 = 1(2) + 1
2 = 2(1) + 0
2. Find the linear combination of 8 and 35 that equals 1, the GCD.
1 = 3 − 1(2)
= [35 − 4(8)] − 1[8 − 2(3)]
= [35 − 4(8)] − 1[8 − 2[35 − 4(8)]]
= 3(35) − 13(8)
3. This gives
−13(8) ≡ 1(mod 35),
so an inverse of 8 modulo 35 is −13.
4. To find the inverse between 0 and 35 use the division algorithm
−13 = −1(35) + 22.
The unique inverse of 8 modulo 35 between 0 and 35 is 22.
5. Check: 8 · 22 = 176 = 5 · 35 + 1 ≡ 1 (mod 35)
3.8. Fermat’s Little Theorem.
Theorem 3.8.1. If p is a prime that does not divide the integer a, then
and
Example 3.8.1. Find 5158 mod 11.
Solution: Since 158 = 15(10) + 8, we have
by Fermat’s little theorem, applied to a = 515 and p = 11.
Now,
.
Thus 5158 mod 11 = 4.
Discussion
The problem of determining whether a given integer is a prime may be very
difficult. This fact is both interesting mathematically and useful in coding
theory.
Fermat’s little theorem provides some help in working with prime numbers and
provides
the basis for many probabilistic primality tests. We will not give a proof of
Fermat’s theorem, since it involves concepts from the theory of groups that
would
take us too far afield. An elementary proof can be found in Introduction to
Modern
Algebra, Fourth Edition, by McCoy and Janusz (Allyn and Bacon, 1987).
The converse of Fermat’s little theorem is not true. In particular, there are
composite
numbers n such that
These are called pseudoprimes. They are very rare, but 341 is a pseudoprime.
Fermat’s little theorem can be used to reduce the problem of finding the
remainder
of a large power modulo a prime. In Example 3.8.1, we use the fact that 515 and
11
are relatively prime and Fermat’s little theorem to get (515)10 ≡ 1(mod 11),
thereby
reducing 5158 to a smaller power of 5 modulo 11. One clearly has to be
comfortable
with the laws of exponents to carry out an exercise such as this.
3.9. RSA System. The RSA system is a public key
cryptosystem based on
modular exponentiation modulo the product of two large primes. This system,
named
after the researchers who introduced it: Rivest, Shamir, and Adleman, is a
public key
cryptosystem.
RSA Code
(1) Find p and q, large primes.
(2) Choose e so that e < pq and GCD(e, (p−1)(q −1)) = 1. e must be odd, but
not necessarily prime.
(3) Find d such that de ≡1(mod (p − 1)(q − 1)).
(4) Encryption function f(t) = te(mod pq).
(5) Decryption function f -1(c) = cd(mod pq).
The public keys are (p, q, e) and the private key is d.
Example 3.9.1. Here is the routine, using p = 61, q = 53, e = 17, and d = 2753.
1. The first prime number (destroy after computing e and d): p = 61
2. The second prime number (destroy after computing e and d): q = 53
3. Modulus (give this to others): pq = 3233
4. Public exponent (give this to others): e = 17
5. Private exponent (keep this secret): d = 2753
6. Your public key is (pq, e) = (3233, 17).
7. Your private key is d = 2753.
8. The encryption function is f(t) = (t17)(mod 3233).
9. The decryption function is : f -1(c) = (c2753)(mod 3233).
To encrypt the plaintext value 123, do this:
f(123) = (12317)(mod 3233) = 337587917446653715596592958817679803(mod 3233) =
855
To decrypt the ciphertext value 855, do this:
f -1(855) = (8552753)(mod 3233)
= (an incredibly huge number goes here) (mod 3233)
= 123
The large exponential expressions can be reduced modulo 3233 in a piecemeal
fashion, however, so that you don’t actually have to calculate these large
numbers.
