YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #6
Professor M. J. Fischer   February 18, 2013



 

Linear Congruence Equations

Let a,x ∈ Z* n. Recall that x is said to be an inverse of a modulo n if ax 1 (mod n). It is easily seen that the inverse, if it exists, is unique modulo n, for if ax 1 (mod n) and ay 1 (mod n), then x xay y (mod n). We denote this unique x, when it exists, by a-1 (mod n) (or simply a-1 when the modulus n is clear from context).

Theorem 1 Let a ∈ Z*n. Then a-1 exists in Z*n.

Proof: Let a ∈ Z*n and consider the function fa(x) = ax mod n. fa is easily shown to be a one-one mapping from Z*n to Z*n. Hence, fa is also onto, so for some x ∈ Z*n, fa(x) = 1. Then ax 1 (mod n), so x = a-1 (mod n). __

We showed in class how to use the Extended Euclidian algorithm to efficiently compute a-1 (mod n) given a and n.

Here we consider the solvability of the more general linear congruence equation:

ax ≡ b (mod n )
(1)

where a,b ∈ Z*n are constants, and x is a variable ranging over Z*n.

Theorem 2 Let a,b,n ∈ Z*n. Let d = gcd(a,n). If db then ax b (mod n) has d solutions x0,,xd-1, where

    (  )     (  )
x =   b- x +  n-  t
 t    d        d
(2)

and x = (a
d)-1 (mod (n
 d)). If d ~ n, then ax b (mod n) has no solutions.

Proof: Let d = gcd(a,n). Clearly if ax b (mod n), then db, so there are no solutions if d ~ b.

Now suppose db. Since (ad) and (nd) are relatively prime, x exists by Theorem 1. Multiplying both sides of (2) by a, we get

       (  )      (  )
axt = b a-  x+ n  a-  t
        d          d
(3)

where now we are working over the integers. But (a)
 dx = 1 + kn
 d for some k by the definition of x, so substituting for (a)
 dx in (3) yields

            (  )     (  )
axt = b+ kn   b- + n  a- t
              d       d
(4)

The quantities in parentheses are both integers, so it follows immediately that axt b (mod n) and hence xt is a solution of (1).

It remains to show that the d solutions above are distinct modulo n. But this is obvious since x0 < x1 < < xd-1 and xd-1 - x0 = n
d(d - 1) < n. __