Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

278 PROPERTIES OF THE INTEGERS [CHAP. 11

EXAMPLE 11.14

(a) Consider the modulusm=15. There are eight integers between 1 and 15 which are coprime to 15:

1 , 2 , 4 , 7 , 8 , 11 , 13 , 14

Thusφ( 15 )=8 and the above eight integers form a reduced residue system modulo 15.

(b) Consider any primep. All the numbers 1, 2 ,...,p−1 are coprime top; henceφ(p)=p−1.

Afunctionfwith domain the positive integersNis said to bemultiplicativeif, wheneveraandbare relatively

prime,

f(ab)=f(a)f(b)

The following theorem (proved in Problem 11.44) applies.

Theorem 11.25: Euler’s phi function is multiplicative. That is, ifaandbare relatively prime, then

φ(ab)=φ(a)φ(b)

11.9Congruence Equations

Apolynomial congruence equationor, simply, acongruence equation(in one unknownx) is an equation of

the form

anxn+an− 1 xn−^1 +...+a 1 x+a 0 ≡ 0 (modm) (11.2)

Such an equation is said to be ofdegree nifa≡0 (modm).

Supposes≡t(modm). Thensis a solution of (11.2) if and only iftis a solution of (11.2). Thus the

number of solutionsof (11.2) is defined to be the number of incongruent solutions or, equivalently, the number

of solutions in the set

{ 0 , 1 , 2 ,...,m− 1 }

Of course, these solutions can always be found by testing, that is, by substituting each of themnumbers into

(11.2) to see if it does indeed satisfy the equation.

Thecomplete set of solutionsof (11.2) is a maximum set of incongruent solutions whereas thegeneral

solutionof (11.2) is the set of all integral solutions of (11.2). The general solution of (11.2) can be found by

adding all the multiples of the modulusmto any complete set of solutions.

EXAMPLE 11.15Consider the equations:

(a)x^2 +x+ 1 ≡0 (mod 4), (b)x^2 + 3 ≡0 (mod 6), (c)x^2 − 1 ≡0 (mod 8)

Here we find the solutions by testing.