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

Theorem 1 Let a Z*_n. Then a^-1 exists in Z*_n.

Proof: Let a

Z*_n and consider the function f_a(x) = ax mod n. f_a is easily shown to be a one-one mapping from Z*_n to Z*_n. Hence, f_a is also onto, so for some x

Z*_n, f_a(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 d∣b then ax ≡ b (mod n) has d solutions x₀,…,x_d-1, where

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

(2)

and = ( 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 d∣b, so there are no solutions if d ~ ∣ b.

Now suppose d∣b. Since () and () are relatively prime, 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)
d = 1 + kn
d for some k by the definition of , so substituting for (a)
d 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 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₀ < x₁ < … < x_d-1 and x_d-1 - x₀ = n
d (d - 1) < n. __