Math 110 Homework 1 Solutions

1 math 110 Homework 1 SolutionsJanuary 15, 20151. (a) Define the phrasemdividesn.(b) Given integersmandn, state the definition of thegreatest common divisorofmandn.(c) Suppose thatmandnare two integers such thatm|n. Find gcd(m, n), and prove your :(a) The integermdividesnif there exists an integerrsuch thatn=mr.(b) The greatest common divisor is the largest positive integerdwhich divides bothmandn. Thismeans that (i)d|mandd|n, and (ii) for any integercsuch thatc|mandc|n, we haved c.(c) The greatest common divisor is|m|. For suppose a positive integeradividedm. Then by definitionthere exists an integerrsuch thatm=ra. By hypothesis thatm|n, there also exists an integerssuchthatms=n. Thenn=ms= (ra)s= (rs)awhich is the definition ofa|n. Therefore, any divisor ofmis automatically a divisor ofn. Hence thegreatest positive integer which divides bothmandnis the largest positive integer which dividesm,which is|m|.

2 2. (a) Find the greatest common divisor of 1064 and 856.(b) Find integersxandyso that 1064x+ 856y=gcd(1064,856).Solution:(a) Use the Euclidean algorithm:1064 = 856 1 + 208856 = 208 4 + 24208 = 24 8 + 1624 = 16 1 + 816 = 8 2 + 0 Therefore the greatest common divisor is 8.(b) Now substitute:8 = 24 16= 24 (208 24 8)= 208 + 24 9= 208 + (856 208 4) 9= 856 9 208 37= 856 9 (1064 856) 37= 37 1064 + 46 856 Therefore one solution is to takex= 37 andy= Complete our proof that the Euclidean algorithm computes the gcd, by showing fora, b, q, r Zwitha=bq+rthen gcd(a, b) =gcd(b, r).Hint:Show that any common divisor ofaandbis also a common divisor ofbandr, and vice versa. Ifthe set of common divisors ofaandbis the same as the set of common divisors ofbandr, then bothmust have the same greatest common :As the hint suggests, we will show that the set of common divisors foraandbis the sameas the set of common divisors that an integerndivides bothaandb.

3 The hypothesisndividesaandbimplies there areintegerssandtsuch thata=nsandb=nt. Thenr=a bq=ns ntq=n(s tq).Thereforen| thatndividesbandr. Then there aresandtwithb=snandr=tn. Substitutinga=bq+r=snq+tn=n(sq+t)which means Prove that ifa Zsuch thata >1, thenafactors as a product of positive primes, and this factorizationis unique up to the order of the :This result is proven on page 65 of the textbook. You re welcome to read this proof, but be sure towrite up your solution in your own words. Remember that we have already proved in class the followingresult: Ifpis prime andpdivides a product of integersab, thenp|aorp| :See the proof on page In this problem, we will give a classical proof of the infinitude of primes.(a) Prove that for anyn Z, gcd(n, n+ 1) = 1. Conclude that if a primepdividesn, thenpcannotdividen+ 1.(b) Write a proof that there are infinitely many prime numbers, as follows.

4 Assume that there wereonly finitely many primesp1, p2, .. , pN. Consider the number (p1p2 pN+ 1), and use Part (a)to reach a :(a) Letnbe an integer. Supposea|nanda|(n+ 1). Thenas=nandat=n+ 1 for somes, t Z. But 1 = (n+ 1) n=at as=a(t s) thereforeadivides 1. Therefore the only commondivisors ofnandn+ 1 are 1 and 1. In particular, a prime cannot divide bothnandn+ 1.(b) Now suppose there are only finitely many primesp1, p2, .. , pN. The numberM= (p1p2 pN+ 1)must have a prime factor, which will be one of the primes listed, saypi. But then we would havepi|Mandpi|p1p2 pN, contradicting the first part of this question. Therefore the assumption there arefinitely many primes is Given integersa, b, for what integersddoes the equationax+by=dhave integer Solutions (x, y)?Justify your :The equation has a solution if and onlydis a multiple of the greatest common divisor the equation had a solution (x, y).

5 Then ifn|aandn|b,ndividesax+by=d. In particular,takingnto be gcd(a, b),nmust , supposedis a multiple of gcd(a, b), sayd=rgcd(a, b) The extended Euclidean algorithmproducesx andy such thatax +by = gcd(a, b).Page 2 Multipyling this expression byr, we seea(x r) +b(y r) = gcd(a, b)r= (a) We saw in class that gcd(28,80) = 4, and that the equation 80u+ 28v= 4 has solutionu= 1andv= 3. There are, however, other Solutions (u, v). Describe the set of all integer Solutions to80u+ 28v= :If we increase or decreaseu= 1 by adding a multiple of284= 7, what canwe do tov= 3 to compensate?(b) We proved that ifa, b Zand gcd(a, b) =d, then there exists a solutionu, v Ztoau+bv= one solution, describe the set of all integer Solutions (u, v).Solution:(a) Because 80 7 28 20 = 0, if we add 7 touwe can decreasevby 20 to leave the entiresum unchanged. This suggests the set of all Solutions will be{( 1 + 7t,3 20t) :t Z}.

6 We will provethis in general in the second part.(b) We show that{(u0+tbd, v0 tad) :t Z}is the set of all Solutions toau+bv= prove this, observe thata(u0+tbd)+b(v0 tad)=au0+bv0+tabd tabd= all of these are let (u, v) be any solution. Then0 = (au+bv) (au0+bv0)0 =a(u u0) +b(v v0)a(u u0) = b(v v0)ad(u u0) = bd(v v0)The integeraddivides the right-hand side of the equation, but it is relatively prime tobd(this was provenon the quiz). Henceadit must divide (v v0). There is therefore an integertsuch that (v v0) = shows thatu u0= tbd. Therefore all Solutions are of the desired (a) Leta, n Z,n >0. Define thecongruence class ofamodulon, and describe the setZ/nZ.(b) Explain in your own words what it means to say that addition and multiplication of congruenceclasses modulonare well-defined .(c) Ifa b(modn) andk|n, musta b(modk)? Justify your :(a) The congruence class is the set of all integers which have the same remainder asawhendivided byn.

7 Equivalently, it is{b Z:n|(a b)}={a+kn:k Z}By definition,Z/nZis the set of all such congruence classes. There is an equivalence class for eachinteger from 0 ton 1.(b) There is an obvious way to add congruence classes: pick an element from each (called a representa-tive), and add them or multiply them. These operations are well defined if the congruence class of theresult does not depend on which element was chosen.(c) The conditiona b(modn) means thatn|(a b). Ifk|n, thenk|(a b) as well, soa b(modk).Page 39. Prove thatahas a multiplicative inverse (modn) if and only if gcd(a, n) = :Suppose thatahas a multiplicative inverse (modn): there existsb Zsuch thatab 1(modn). Letd= gcd(a, n). Then by 8(c) asd|nwe haveab 1 (modd). But this meansd|(ab 1),while alsod|a|ab. Therefored= 1 by 5(a).Conversely, if gcd(a, n) = 1 there is an integer solution (x, y) such thatax+ny= this equation modulon, we seeax 1 (modn).

8 10. Find a multiplicative inverse for 27 (mod 80).Solution:Use the extended Euclidean algorithm to solve 27x+ 80y= 1 as in problem 2. It givesx= 3, y= 1 as a solution. Therefore 3 (mod 80) is a multiplicative (Optional Challenge Question)Prove that ifpis prime, then for anya, b, n Zwithn >0,(a+b)pn apn+bpn(modp).This result is affectionately known as The Freshman s Dream .Solution:We first prove this forn= 1 using the binomial theorem. Write(a+b)p=ap+(p1)ap 1b+(p2)ap 2b2+..+bpHowever, for 1 m p 1,(pm)is a multiple ofp. To see this, use the definition(pm)=(p)!m!(p m)!andnotepcannot dividem! or (p m)! as all terms in these products are less thanp. Therefore all of theterms except the first and last are zero modulop, so(a+b)p ap+bp(modp).For generaln, use induction (ie (a+b)p2 (ap+bp)p ap2+bp2(modp)).12.(Optional Challenge Question)Letp(x) be a polynomial with integer coefficients.

9 A real numberzis arootofpifp(z) = 0. A congruence class [a] modulonis arootofpifp(a) 0 (modn). Apolynomialp(x) of degreedhas at mostddistinct real roots.(a) Find a composite numbernand a degreedpolynomialp(x) with integer coefficients such that morethanddistinct congruence classes modulonare roots ofp(x).(b) Prove that ifq Zis prime, andp(x) is a degreedpolynomial with integer coefficients, then atmostdcongruence classes moduloqare roots ofp(x). (This question is tricky!)Solution:Taken= 6 andp(x) = (x 2)(x 3). Thenx= 2,3 are obvious Solutions , butx= 0,5 arealso Solutions . This has do with the fact that 2 is a zero divisor: 2 3 0 (mod 6).The second part is an important fact written up in many books on abstract algebra. See for exampleProposition 17 of Chapter 9 of Dummit and (Optional Challenge Question)LetQ[x] denote the set of polynomialsf(x) with rational coef-ficients.

10 The goal of this question is to adapt our theory of divisibility to polynomials. Note that apolynomial is calledmonicif its leading coefficient is 4(a) What should it mean for a polynomialf(x) todividea polynomialg(x)? Define the greatestcommon denominator off(x) andg(x). (This should be a monic polynomial that is greatest inthe sense of having highest degree). What is the analogue of a prime number?(b) Prove that iff(x),g(x) are nonzero polynomials inQ[x], then there are polynomialsu(x) andv(x) such thatf(x)u(x) +g(x)v(x) = gcd(f(x), g(x)). You can adapt our proof from class ofthe analogous statement for integers, replacing integer inequalities with inequalities involving thepolynomials :This is a standard fact written up in many books on abstract algebra. See for exampleTheorem 3 of Chapter 9 of Dummit and Foote (which uses extensively).