YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 467b: Cryptography and Computer Security | Handout #6 | |

Professor M. J. Fischer | February 9, 2010 | |

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).

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:

| (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 d∣b then ax ≡ b (mod n) has d solutions x_{0},…,x_{d-1},
where

| (2) |

and = ()^{-1} (mod ()). If d ~ ∣ n, then ax ≡ b (mod n) has no solutions.

Now suppose d∣b. Since () and () are relatively prime, exists by Theorem 1. Multiplying both sides of (2) by a, we get

| (3) |

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

| (4) |

The quantities in parentheses are both integers, so it follows immediately that ax_{t} ≡ b (mod n) and hence
x_{t} is a solution of (1).

It remains to show that the d solutions above are distinct modulo n. But this is obvious since
x_{0} < x_{1} < … < x_{d-1} and x_{d-1} - x_{0} = (d - 1) < n. __