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

294 PROPERTIES OF THE INTEGERS [CHAP. 11

11.46. InZ 11 , find: (a)−2,−5,−9,−10; (b) 2/7, 3/7, 5/7, 8/7, 10/7, 1/7.

(a) Note−a=m−asince(m−a)+a=0. Therefore:

− 2 = 11 − 2 = 9 , − 5 = 11 − 5 = 6 , − 9 = 11 − 9 = 2 , − 10 = 11 − 10 = 1

(b) By definitiona/bis the integercsuch thatbc=a. Since we are dividing by 7, first compute the multiplication

table for 7 inZ 11 as in Fig. 11-10. Now find the number inside the table, and the answer will be above this

number. Thus:

Fig. 11-10

2 / 7 = 5 , 3 / 7 = 2 , 5 / 7 = 7 , 8 / 7 = 9 , 10 / 7 = 3 , 1 / 7 = 8

Note that 7−^1 =8 since 7(8)=8(7)=1.

11.47. ConsiderZpwherepis a prime. Prove:

(a)Ifab=acanda=0, thenb=c;

(b)Ifab=0, thena=0orb=0.

(a)Ifab=acinZp, thenab≡ac(modp). Sincea=0, gcd(a, p)=1. By Theorem 11.23 we can cancel the

a’s to obtainb≡c(modp). Thereforeb=cinZp.

(b)Ifab=0inZp, thenab=0 (mod p). Therefore,pdivides the productab. Sincepis a prime,p|aorp|b;

that is,a≡0 (modp)orb≡0 (modp). Thusa=0orb=0inZp.

11.48. Considera=0inZmwhere gcd(a, m)=1. Show thatahas a multiplicative inverse inZm.

Sincea=0 and gcd(a, m)=1, there exists integersxandysuch thatax+my=1orax− 1 =my. Thus

mdividesax−1 and henceax=1 (modm). Reducexmodulomto an elementx′inZm. Thenax′=1inZm.

11.49. Finda−^1 inZmwhere: (a)a=37 andm=249; (b)a=15 andm=234.

(a) First findd=gcd (37,249) obtainingd=1. Then, as in Example 11.6, findxandysuch thatax+my=1.

This yieldsx=−74 andy=14. That is,

− 74 ( 37 )+ 11 ( 249 )=1so− 74 ( 37 )≡ 1 (mod 249)

Addm=249 to−74 to obtain− 74 + 249 =175. Thus( 175 )( 37 )≡1 (mod 249).

Accordingly,a−^1 =175 inZ 249.

(b) First findd=gcd (15, 234) obtainingd=3. Thusd=1, and hence 15 has no multiplicative inverse inZ 234.

11.50. For the following polynomials overZ 7 find: (a)f(x)+g(x)and (b)f (x)h(x).

f(x)= 6 x^3 − 5 x^2 + 2 x− 4 , g(x)= 5 x^3 + 2 x^2 + 6 x− 1 , h(x)= 3 x^2 − 2 x− 5

Perform the operations as if the polynomials were over the integersZ, and then reduce the coefficients modulo 7.

(a) We get:f(x)+g(x) = 11 x^3 − 3 x^2 + 8 x− 5 = 4 x^3 − 3 x^2 +x− 5 = 4 x^3 + 4 x^2 +x+ 2

(b) First find the productf (x)h(x)as in Fig. 11-11. Then, reducing modulo 7, we obtain:(g)

f (x)h(x) = 4 x^5 − 6 x^4 + 2 x^2 − 2 x+ 6 = 4 x^5 +x^4 + 2 x^2 + 5 x+ 6