Chapter 8 Number Theory308
(e)If gcd.a;b/¤ 1 and gcd.b;c/¤ 1 , then gcd.a;c/¤ 1. true false(f)If an integer linear combination ofaandbequals 1,then so does some integer linear combination ofa^2 andb^2. true false
(g)If no integer linear combination ofaandbequals 2,then neither does any integer linear combination ofa^2 andb^2. true false
(h)Ifacbc .modn/andndoes not dividec,thenab .modn/. true false
(i)Assuminga;bhave inverses modulon,ifa ^1 b ^1 .modn/, thenab .modn/. true false
(j)Ifacbc .modn/andndoes not dividec,thenab .modn/. true false
(k)Ifab .mod .n//fora;b > 0, thencacb .modn/. true false(l)Ifab .modnm/, thenab .modn/. true false(m)If gcd.m;n/D 1 , then
Œab .modm/ANDab .modn/çiffŒab .modmn/ç true false
(n)If gcd.a;n/D 1 , thenan ^1 1 .modn/ true false(o)Ifa;b > 1, then[ahas a inverse modbiffbhas an inverse moda]. true false
Problem 8.69.
Find an integerk > 1such thatnandnkagree in their last three digits whenevern
is divisible by neither 2 nor 5.Hint:Euler’s theorem.
Problem 8.70.
(a)Explain why. 12/^482 has a multiplicative inverse modulo 175.(b)What is the value of .175/, where is Euler’s function?