8.13. References 307
(a)Show that ifpidoes not dividea, thena .m/1 .modpkii/:(b)Show that ifpijathenam .m/0 .modpiki/: (8.46)(c)Conclude (8.45) from the facts above.Hint:am am .m/Dam .m/.a .m/ 1/.
Exam Problems
Problem 8.66.
What is the remainder of 639601 divided by 220?
Problem 8.67.
Prove that ifk 1 andk 2 are relatively prime ton, then so isk 1 nk 2 ,
(a)... using the fact thatkis relatively prime toniffkhas an inverse modulon.Hint:Recall thatk 1 k 2 k 1 nk 2 .modn/.
(b)... using the fact thatkis relatively prime toniffkis cancellable modulon.(c)... using the Unique Factorization Theorem and the basic GCD properties such
as Lemma 8.2.1.
Problem 8.68.
Circletrueorfalsefor the statements below, andprovide counterexamplesfor
those that arefalse. Variables,a;b;c;m;nrange over the integers andm;n > 1.
(a)gcd.1Ca;1Cb/D 1 Cgcd.a;b/. true false(b)Ifab .modn/, thenp.a/p.b/ .modn/for any polynomialp.x/with integer coefficients. true false
(c)Ifajbcand gcd.a;b/D 1 , thenajc. true false(d)gcd.an;bn/D.gcd.a;b//n true false