Solution Manual for A Friendly Introduction to Number Theory, 4th Edition

Page 1 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 1 preview image

SOLUTIONSMANUALAFRIENDLYINTRODUCTIONTONUMBERTHEORYFOURTHEDITIONJoseph SilvermanBrown University

Page 2 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 2 preview image

Page 3 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 3 preview image

Table of ContentsChapter 1What is Number Theory?1Chapter 2Pythagorean Triples5Chapter 3Pythagorean Triples and the Unit Circle11Chapter 4Sums of Higher Powers and Fermat’s Last Theorem16Chapter 5Divisibility and the Greatest Common Divisor19Chapter 6Linear Equations and the Greatest Common Divisor25Chapter 7Factorization and the Fundamental Theorem of Arithmetic30Chapter 8Congruences35Chapter 9Congruences, Powers, and Fermat’s Little Theorem40Chapter 10Congruences, Powers, and Euler’s Formula43Chapter 11Euler’s Phi Function and the Chinese Remainder Theorem46Chapter 12Prime Numbers55Chapter 13Counting Primes60Chapter 14Mersenne Primes65Chapter 15Mersenne Primes and Perfect Numbers68Chapter 16Powers Modulomand Successive Squaring75Chapter 17ComputingkthRoots Modulom78Chapter 18Powers, Roots, and “Unbreakable” Codes81Chapter 19Primality Testing and Carmichael Numbers84Chapter 20Squares Modulop88Chapter 21Is –1 a Square Modulop? Is 2?91Chapter 22Quadratic Reciprocity95Chapter 23Which Primes are Sums of Two Squares?108Chapter 24Which Numbers are Sums of Two Squares?113Chapter 25As Easy as One, Two, Three116Chapter 26Euler’s Phi Function and Sums of Divisors122Chapter 27Powers Modulopand Primitive Roots126Chapter 28Primitive Roots and Indices135Chapter 29The EquationX4+Y4=Z4138Chapter 30Square–Triangular Numbers Revisited143Chapter 31Pell’s Equation147Chapter 32Diophantine Approximation152Chapter 33Diophantine Approximation and Pell’s Equation156Chapter 34Number Theory and Imaginary Numbers159Chapter 35The Gaussian Integers and Unique Factorization163Chapter 36Irrational Numbers and Transcendental Numbers168Chapter 37Binomial Coefficients and Pascal’s Triangle176Chapter 38Fibonacci’s Rabbits and Linear Recurrence Sequences180Chapter 39Oh, What a Beautiful Function190Chapter 40Cubic Curves and Elliptic Curves195Chapter 41Elliptic Curves with Few Rational Points200Chapter 42Points on Elliptic Curves Modulop205Chapter 43Torsion Collections Modulopand Bad Primes211Chapter 44Defect Bounds and Modularity Patterns215

Page 4 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 4 preview image

Chapter 45The Topsy-Turvy World of Continued Fractions [online]219Chapter 46Continued Fractions, Square Roots, and Pell’s Equation [online]227Chapter 47Generating Functions [online]232Chapter 48Sums of Powers [online]240

Page 5 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 5 preview image

Chapter 1What Is Number Theory?Exercises1.1.The first two numbers that are both squares and triangles are1and36.Find thenext one and, if possible, the one after that. Can you figure out an efficient way to findtriangular–square numbers? Do you think that there are infinitely many?Solution to Exercise 1.1.The first three triangular–square numbers are 36, 1225, and 41616.Triangular–squarenumbers are given by pairs(m, n)satisfyingm(m+ 1)/2 =n2. The first few pairs are(8,6),(49,35),(288,204),(1681,1189), and(9800,6930).The pattern for generatingthese pairs is quite subtle.We will give a complete description of all triangular–squarenumbers in Chapter 28, but for now it would be impressive to merely notice empiricallythat if(m, n)gives a triangular–square number, then so does(3m+ 4n+ 1,2m+ 3n+ 1).Starting with(1,1)and applying this rule repeatedly will actually give all triangular–squarenumbers.1.2.Try adding up the first few odd numbers and see if the numbers you get satisfy somesort of pattern.Once you find the pattern, express it as a formula.Give a geometricverification that your formula is correct.Solution to Exercise 1.2.The sum of the firstnodd numbers is always a square. The formula is1 + 3 + 5 + 7 +· · ·+ (2n−1) =n2.The following pictures illustrate the first few cases, and they make it clear how the generalcase works.331355533513577775557335713571 + 3 = 41 + 3 + 5 = 91 + 3 + 5 + 7 = 161

Page 6 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 6 preview image

[Chap. 1]What Is Number Theory?21.3.The consecutive odd numbers 3, 5, and 7 are all primes. Are there infinitely manysuch “prime triplets”? That is, are there infinitely many prime numberspsuch thatp+ 2andp+ 4are also primes?Solution to Exercise 1.3.The only prime triplet is 3, 5, 7. The reason is that for any three odd numbers, at least oneof them must be divisible by 3. So in order for them all to be prime, one of them mustequal 3. It is conjectured that there are infinitely many primespsuch thatp+ 2andp+ 6are prime, but this has not been proved. Similarly, it is conjectured that there are infinitelymany primespsuch thatp+ 4andp+ 6are prime, but again no one has a proof.1.4.It is generally believed that infinitely many primes have the formN2+ 1, althoughno one knows for sure.(a)Do you think that there are infinitely many primes of the formN2−1?(b)Do you think that there are infinitely many primes of the formN2−2?(c)How about of the formN2−3? How aboutN2−4?(d)Which values ofado you think give infinitely many primes of the formN2−a?Solution to Exercise 1.4.First we accumulate some data, which we list in a table. Looking at the table, we see thatN2−1andN2−4are almost never equal to primes, whileN2−2andN2−3seem tobe primes reasonably often.NN2−1N2−2N2−3N2−42321038 = 2376 = 2·35415 = 3·514 = 2·71312 = 22·3524 = 23·32322 = 2·1121 = 3·7635 = 5·734 = 2·1733 = 3·1132 = 25748 = 24·34746 = 2·2345 = 32·5863 = 32·762 = 2·316160 = 22·3·5980 = 24·57978 = 2·3·1377 = 7·111099 = 32·1198 = 2·729796 = 25·311120 = 23·3·5119 = 7·17118 = 2·59117 = 32·1312143 = 11·13142 = 2·71141 = 3·47140 = 22·5·713168 = 23·3·7167166 = 2·83165 = 3·5·1114195 = 3·5·13194 = 2·97193192 = 26·315224 = 25·7223222 = 2·3·37221 = 13·17Looking at the even values ofNin theN2−1column, we might notice that22−1is a multiple of3, that42−1is a multiple of5, that62−1is a multiple of7, and so on.2

Page 7 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 7 preview image

[Chap. 1]What Is Number Theory?3Having observed this, we see that the same pattern holds for the oddN’s. Thus32−1isa multiple of4and52−1is a multiple of6and so on. So we might guess thatN2−1is always a multiple ofN+ 1. This is indeed true, and it can be proved true by the wellknown algebraic formulaN2−1 = (N−1)(N+ 1).SoN2−1will never be prime ifN≥2.TheN2−4column is similarly explained by the formulaN2−4 = (N−2)(N+ 2).More generally, ifais a perfect square, saya=b2, then there will not be infinitely manyprimes of the formN2−a, sinceN2−a=N2−b2= (N−b)(N+b).On the other hand, it is believed that there are infinitely many primes of the formN2−2and infinitely many primes of the formN2−3. Generally, ifais not a perfectsquare, it is believed that there are infinitely many primes of the formN2−a. But no onehas yet proved any of these conjectures.1.5.The following two lines indicate another way to derive the formula for the sum of thefirstnintegers by rearranging the terms in the sum. Fill in the details.1 + 2 + 3 +· · ·+n= (1 +n) + (2 + (n−1)) + (3 + (n−2)) +· · ·= (1 +n) + (1 +n) + (1 +n) +· · ·.How many copies ofn+ 1are in there in the second line? You may need to consider thecases of oddnand evennseparately. If that’s not clear, first try writing it out explicitly forn= 6andn= 7.Solution to Exercise 1.5.Suppose first thatnis even. Then we getn/2copies of1 +n, so the total isn2 (1 +n) =n2+n2.Next suppose thatnis odd. Then we getn−12copies of1 +nand also the middletermn+12which hasn’t yet been counted. To illustrate withn= 9, we group the terms as1 + 2 +· · ·+ 9 = (1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5,so there are4copies of10, plus the extra 5 that’s left over. For generaln, we getn−12(1 +n) +n+ 12=n2−12+n+ 12=n2+n2.3

Page 8 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 8 preview image

[Chap. 1]What Is Number Theory?4Another similar way to do this problem that doesn’t involve splitting into cases is tosimply take two copies of each term. Thus2(1 + 2 +· · ·+n) = (1 + 2 +· · ·+n) + (1 + 2 +· · ·+n)= (1 + 2 +· · ·+n) + (n+· · ·+ 2 + 1)= (1 +n) + (2 +n−1) + (3 +n−2) +· · ·+ (n+ 1)= (1 +n) + (1 +n) +· · ·+ (1 +n)︸︷︷︸ncopies ofn+ 1=n(1 +n) =n2+nThus the twice the sum1+2+· · ·+nequaln2+n, and now divide by2to get the answer.1.6.For each of the following statements, fill in the blank with an easy-to-check crite-rion:(a)Mis a triangular number if and only ifis an odd square.(b)Nis an odd square if and only ifis a triangular number.(c)Prove that your criteria in (a) and (b) are correct.Solution to Exercise 1.6.(a)Mis a triangular number if and only if1 + 8Mis an odd square.(b)Nis an odd square if and only if(N−1)/8is a triangular number. (Note that ifNisan odd square, thenN2−1is divisible by8, since(2k+1)2= 4k(k+1)+1, and4k(k+1)is a multiple of8.)(c)IfMis triangular, thenM=m(m+1)/2, so1+8M= 1+4m+4m2= (1+2m)2.Conversely, if1 + 8Mis an odd square, say1 + 8M= (1 + 2k)2, then solving forMgivesM= (k+k2)/2, soMis triangular.Next supposeNis an odd square, sayN= (2k+ 1)2. Then as noted above,(N−1)/8 =k(k+1)/2, so(N−1)/8is triangular. Conversely, if(N−1)/8is trianglular, then(N−1)/8 = (m2+m)/2for somem, so solving forNwe find thatN= 1+4m+4m2=(1 + 2m)2, soNis a square.4

Page 9 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 9 preview image

Chapter 2Pythagorean TriplesExercises2.1. (a)We showed that in any primitive Pythagorean triple(a, b, c), eitheraorbis even.Use the same sort of argument to show that eitheraorbmust be a multiple of3.(b)By examining the above list of primitive Pythagorean triples, make a guess aboutwhena,b, orcis a multiple of5. Try to show that your guess is correct.Solution to Exercise 2.1.(a) Ifais not a multiple of3, it must equal either3x+ 1or3x+ 2. Similarly, ifbis nota multiple of3, it must equal3y+ 1or3y+ 2. There are four possibilities fora2+b2,namelya2+b2= (3x+ 1)2+ (3y+ 1)2= 9x2+ 6x+ 1 + 9y2+ 6y+ 1= 3(3x2+ 2x+ 3y2+ 2y) + 2,a2+b2= (3x+ 1)2+ (3y+ 2)2= 9x2+ 6x+ 1 + 9y2+ 12y+ 4= 3(3x2+ 2x+ 3y2+ 4y+ 1) + 2,a2+b2= (3x+ 2)2+ (3y+ 1)2= 9x2+ 12x+ 4 + 9y2+ 6y+ 1= 3(3x2+ 4x+ 3y2+ 2y+ 1) + 2,a2+b2= (3x+ 2)2+ (3y+ 2)2= 9x2+ 12x+ 4 + 9y2+ 12y+ 4= 3(3x2+ 4x+ 3y2+ 4y+ 2) + 2.So ifaandbare not multiples of3, thenc2=a2+b2looks like2more than a multipleof3. But regardless of whethercis3zor3z+1or3z+2, the numbersc2cannot be2morethan a multiple of3. This is true because(3z)2= 3·3z,(3z+ 1)2= 3(3z2+ 2z) + 1,(3z+ 2)2= 3(3z2+ 4z+ 1) + 1.5

Page 10 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 10 preview image

[Chap. 2]Pythagorean Triples6(b)The table suggests that in every primitive Pythagorean triple, exactly one ofa,b, orcis a multiple of5. To verify this, we use the Pythagorean Triples Theorem to writeaandbasa=standb=12(s2−t2). If eithersortis a multiple of5, thenais a multiple of5and we’re done. Otherwiseslooks likes= 5S+iandtlooks like5T+jwithiandjbeing integers in the set{1,2,3,4}. Next we observe that2b=s2−t2= (5S+i)2−(5T+j)2= 25(S2−T2) + 10(Si−T j) +i2−j2.Ifi2−j2is a multiple of5, thenbis a multiple of5, and again we’re done. Looking atthe16possibilities for the pair(i, j), we see that this accounts for8of them, leaving thepossibilities(i, j) = (1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),or(4,3).Now for each of these remaining possibilities, we need to check that2c=s2+t2= (5S+i)2+ (5T+j)2= 25(S2+T2) + 10(Si+T j) +i2+j2is a multiple of5, which means checking thati2+j2is a multiple of5. This is easilyaccomplished:12+ 22= 5 12+ 32= 1021+ 12= 5 22+ 42= 20(2.1)31+ 12= 1032+ 42= 2542+ 22= 2042+ 32= 25.(2.2).2.2.A nonzero integerdis said todividean integermifm=dkfor some numberk.Show that ifddivides bothmandn, thendalso dividesm−nandm+n.Solution to Exercise 2.2.Bothmandnare divisible byd, som=dkandn=dk′. Thusm±n=dk±dk′=d(k±k′), som+nandm−nare divisible byd.2.3.For each of the following questions, begin by compiling some data; next examine thedata and formulate a conjecture; and finally try to prove that your conjecture is correct. (Butdon’t worry if you can’t solve every part of this problem; some parts are quite difficult.)(a)Which odd numbersacan appear in a primitive Pythagorean triple(a, b, c)?(b)Which even numbersbcan appear in a primitive Pythagorean triple(a, b, c)?(c)Which numbersccan appear in a primitive Pythagorean triple(a, b, c)?Solution to Exercise 2.3.(a) Any odd number can appear as theain a primitive Pythagorean triple. To find such atriple, we can just taket=aands= 1in the Pythagorean Triples Theorem. This givesthe primitive Pythagorean triple(a,(a2−1)/2,(a2+ 1)/2).(b)Looking at the table, it seems first thatbmust be a multiple of4, and second thatevery multiple of4seems to be possible. We know thatblooks likeb= (s2−t2)/2with6

Page 11 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 11 preview image

[Chap. 2]Pythagorean Triples7sandtodd. This means we can writes= 2m+ 1andt= 2n+ 1. Multiplying things outgivesb= (2m+ 1)2−(2n+ 1)22= 2m2+ 2m−2n2−2n= 2m(m+ 1)−2n(n+ 1).Can you see thatm(m+ 1)andn(n+ 1)must both be even, regardless of the value ofmandn? Sobmust be divisible by4.On the other hand, ifbis divisible by4, then we can write it asb= 2rBfor someodd numberBand somer≥2.Then we can try to find values ofsandtsuch that(s2−t2)/2 =b. We factor this as(s−t)(s+t) = 2b= 2r+1B.Now boths−tands+tmust be even (sincesandtare odd), so we might trys−t= 2rands+t= 2B.Solving forsandtgivess= 2r−1+Bandt=−2r−1+B. Notice thatsandtare odd,sinceBis odd andr≥2. Thena=st=B2−22r−2,b=s2−t22= 2rB,c=s2+t22=B2+ 22r−2.This gives a primitive Pythagorean triple with the right value ofbprovided thatB >2r−1.On the other hand, ifB <2r−1, then we can just takea= 22r−2−B2instead.(c)This part is quite difficult to prove, and it’s not even that easy to make the correctconjecture.It turns out that an odd numbercappears as the hypotenuse of a primitivePythagorean triple if and only if every prime dividingcleaves a remainder of1whendivided by4.Thuscappears if it is divisible by the primes5,13,17,29,37, . . ., but itdoes not appear if it is divisible by any of the primes3,7,11,19,23, . . .. We will provethis in Chapter 25. Note that it is not enough thatcitself leave a remainder of1whendivided by4. For example, neither9nor21can appear as the hypotenuse of a primitivePythagorean triple.2.4.In our list of examples are the two primitive Pythagorean triples332+ 562= 652and162+ 632= 652.Find at least one more example of two primitive Pythagorean triples with the same valueofc. Can you find three primitive Pythagorean triples with the samec? Can you find morethan three?7

Page 12 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 12 preview image

[Chap. 2]Pythagorean Triples8Solution to Exercise 2.4.The next example isc= 5·17 = 85. Thus852= 132+ 842= 362+ 772.A general rule is that ifc=p1p2· · ·pris a product ofrdistinct odd primes which all leavea remainder of1when divided by4, thencappears as the hypotenuse in2r−1primitivePythagorean triples.(This is counting(a, b, c)and(b, a, c)as the same triple.)So forexample,c= 5·13·17 = 1105appears in 4 triples,11052= 5762+ 9432= 7442+ 8172= 2642+ 10732= 472+ 11042.But it would be difficult to prove the general rule using only the material we have developedso far.2.5.In Chapter 1 we saw that thenthtriangular numberTnis given by the formulaTn= 1 + 2 + 3 +· · ·+n=n(n+ 1)2.The first few triangular numbers are1,3,6, and10. In the list of the first few Pythagoreantriples(a, b, c), we find(3,4,5),(5,12,13),(7,24,25), and(9,40,41). Notice that in eachcase, the value ofbis four times a triangular number.(a)Find a primitive Pythagorean triple(a, b, c)withb= 4T5. Do the same forb= 4T6and forb= 4T7.(b)Do you think that for every triangular numberTn, there is a primitive Pythagoreantriple(a, b, c)withb= 4Tn? If you believe that this is true, then prove it. Otherwise,find some triangular number for which it is not true.Solution to Exercise 2.5.(a)T5= 15and(11,60,61).T6= 21and(13,84,85).T7= 28and(15,112,113).(b)The primitive Pythagorean triples withbeven are given byb= (s2−t2)/2,s > t≥1,sandtodd integers, andgcd(s, t) = 1. Sincesis odd, we can write it ass= 2n+ 1,and we can taket= 1. (The examples suggest that we wantc=b+ 1, which means weneed to taket= 1.) Thenb=s2−t22= (2n+ 1)2−12= 2n2+ 2n= 4n2+n2= 4Tn.So for every triangular numberTn, there is a Pythagorean triple(2n+ 1,4Tn,4Tn+ 1).(Thanks to Mike McConnell and his class for suggesting this problem.)2.6.If you look at the table of primitive Pythagorean triples in this chapter, you will seemany triples in whichcis 2 greater thana. For example, the triples(3,4,5),(15,8,17),(35,12,37), and(63,16,65)all have this property.(a)Find two more primitive Pythagorean triples(a, b, c)havingc=a+ 2.8

Page 13 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 13 preview image

[Chap. 2]Pythagorean Triples9(b)Find a primitive Pythagorean triple(a, b, c)havingc=a+ 2andc >1000.(c)Try to find a formula that describes all primitive Pythagorean triples(a, b, c)havingc=a+ 2.Solution to Exercise 2.6.The next few primitive Pythagorean triples withc=a+ 2are(99,20,101),(143,24,145),(195,28,197),(255,32,257),(323,36,325),(399,40,401).One way to find them is to notice that thebvalues are going up by4each time.Aneven better way is to use the Pythagorean Triples Theorem. This says thata=standc= (s2+t2)/2. We wantc−a= 2, so we sets2+t22−st= 2and try to solve forsandt. Multiplying by2givess2+t2−2st= 4,(s−t)2= 4,s−t=±2.The Pythagorean Triples Theorem also says to takes > t, so we need to haves−t= 2.Further,sandtare supposed to be odd. If we substitutes=t+ 2into the formulas fora, b, c, we get a general formula for all primitive Pythagorean triples withc=a+ 2. Thusa=st= (t+ 2)t=t2+ 2t,b=s2−t22= (t+ 2)2−t22= 2t+ 2,c=s2+t22= (t+ 2)2+t22=t2+ 2t+ 2.We will get all PPT’s withc=a+ 2by takingt= 1,3,5,7, . . .in these formulas. Forexample, to get one withc >1000, we just need to choosetlarge enough to maket2+2t+2>1000. The leasttwhich will work ist= 31, which gives the PPT(1023,64,1025).The next few withc >1000are(1155,68,1157),(1295,72,1297),(1443,76,1445),obtained by settingt= 33,35, and37respectively.2.7.For each primitive Pythagorean triple(a, b, c)in the table in this chapter, compute thequantity2c−2a. Do these values seem to have some special form? Try to prove that yourobservation is true for all primitive Pythagorean triples.Solution to Exercise 2.7.First we compute2c−2afor the PPT’s in the Chapter 2 table.a35791521354563b4122440820122816c513254117293753652c−2a416366441641649

Page 14 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 14 preview image

[Chap. 2]Pythagorean Triples10all the differences2c−2aseem to be perfect squares. We can show that this is alwaysthe case by using the Pythagorean Triples Theorem, which says thata=standc=(s2+t2)/2. Then2c−2a= (s2+t2)−2st= (s−t)2,so2c−2ais always a perfect square.2.8.Letmandnbe numbers that differ by2, and write the sum1m+1nas a fraction inlowest terms. For example,12+14=34and13+15=815.(a)Compute the next three examples.(b)Examine the numerators and denominators of the fractions in (a) and compare themwith the table of Pythagorean triples on page 18. Formulate a conjecture about suchfractions.(c)Prove that your conjecture is correct.Solution to Exercise 2.8.(a)14 + 16 =512,15 + 17 = 1235,16 + 18 =724.(b) It appears that the numerator and denominator are always the sides of a (primitive)Pythagorean triple.(c) This is easy to prove. Thus1N+1N+ 2 =2N+ 2N2+ 2N .The fraction is in lowest terms ifNis odd, otherwise we need to divide numerator and de-nominator by2. But in any case, the numerator and denominator are part of a Pythagoreantriple, since(2N+ 2)2+ (N2+ 2N)2=N4+ 4N3+ 8N2+ 8N+ 4 = (N2+ 2N+ 2)2.Once one suspects thatN4+ 4N3+ 8N2+ 8N+ 4should be a square, it’s not hard tofactor it. Thus if it’s a square, it must look like(N2+AN±2)for some value ofA. Nowjust multiply out and solve forA, then check that your answer works.2.9. (a)Read about the Babylonian number system and write a short description, includ-ing the symbols for the numbers1to10and the multiples of10from20to50.(b)Read about the Babylonian tablet calledPlimpton 322and write a brief report, in-cluding its approximate date of origin.(c)The second and third columns of Plimpton 322 give pairs of integers(a, c)havingthe property thatc2−a2is a perfect square. Convert some of these pairs from Baby-lonian numbers to decimal numbers and compute the value ofbso that(a, b, c)is aPythagorean triple.Solution to Exercise 2.9.There is a good article in wikipedia on Plimpton 322. Another nice source for this materialiswww.math.ubc.ca/˜cass/courses/m446-03/pl322/pl322.html10

Page 15 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 15 preview image

Chapter 3Pythagorean Triplesand the Unit CircleExercises3.1.As we have just seen, we get every Pythagorean triple(a, b, c)withbeven from theformula(a, b, c) = (u2−v2,2uv, u2+v2)by substituting in different integers foruandv. For example,(u, v) = (2,1)gives thesmallest triple(3,4,5).(a)Ifuandvhave a common factor, explain why(a, b, c)will not be a primitive Pytha-gorean triple.(b)Find an example of integersu > v >0that do not have a common factor, yet thePythagorean triple(u2−v2,2uv, u2+v2)is not primitive.(c)Make a table of the Pythagorean triples that arise when you substitute in all valuesofuandvwith1≤v < u≤10.(d)Using your table from (c), find some simple conditions onuandvthat ensure thatthe Pythagorean triple(u2−v2,2uv, u2+v2)is primitive.(e)Prove that your conditions in (d) really work.Solution to Exercise 3.1.(a) Ifu=dUandv=dV, thena,b, andcwill all be divisible byd2, so the triple will notbe primitive.(b)Take(u, v) = (3,1). Then(a, b, c) = (8,6,10)is not primitive.11

Page 16 of 16

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 16 preview image

[Chap. 3]Pythagorean Triples and the Unit Circle12(c)u\v1234567892(3,4,5)3(8,6,10)(5,12,13)4(15,8,17)(12,16,20)(7,24,25)5(24,10,26)(21,20,29)(16,30,34)(9,40,41)6(35,12,37)(32,24,40)(27,36,45)(20,48,52)(11,60,61)7(48,14,50)(45,28,53)(40,42,58)(33,56,65)(24,70,74)(13,84,85)8(63,16,65)(60,32,68)(55,48,73)(48,64,80)(39,80,89)(28,96,100)(15,112,113)9(80,18,82)(77,36,85)(72,54,90)(65,72,97)(56,90,106)(45,108,117)(32,126,130) (17,144,145)10(99,20,101) (96,40,104) (91,60,109) (84,80,116) (75,100,125)(64,120,136) (51,140,149) (36,160,164) (19,180,181)(d) (u2−v2,2uv, u2+v2)will be primitive if and only ifu > vanduandvhave nocommon factor and one ofuorvis even.(e)If bothuandvare odd, then all three numbers are even, so the triple is not primitive.We already saw that ifuandvhave a common factor, then the triple is not primitive. Andwe do not allow nonpositive numbers in primitive triples, so we can’t haveu≤v. Thisproves one direction.To prove the other direction, suppose that the triple is not primitive, so there is anumberd≥2that divides all three terms. Thenddivides the sums(u2−v2) + (u2+v2) = 2u2and(u2−v2)−(u2+v2) = 2v2,so eitherd= 2or elseddivides bothuandv. In the latter case we are done, sinceuandvhave a common factor. On the other hand, ifd= 2anduandvhave no common factor,then at least one of them is odd, so the fact that2dividesu2−v2tells us that they are bothodd.3.2. (a)Use the lines through the point(1,1)to describe all the points on the circlex2+y2= 2whose coordinates are rational numbers.(b)What goes wrong if you try to apply the same procedure to find all the points on thecirclex2+y2= 3with rational coordinates?Solution to Exercise 3.2.(a) LetCbe the circlex2+y2= 2. Take the lineLwith slopemthrough(1,1), wheremis a rational number. The equation ofLisy−1 =m(x−1),soy=mx−m+ 1.To find the intersectionL∩C, we substitute and solve:x2+ (mx−m+ 1)2= 2(m2+ 1)x2−2(m2−m)x+ (m−1)2= 2(m2+ 1)x2−2(m2−m)x+ (m2−2m−1) = 012

Preview Mode

This document has 249 pages. Sign in to access the full document!

Report

Learning Tools

Writing Tools

Browse Resources

Solution Manual for A Friendly Introduction to Number Theory, 4th Edition - Page 1

Study Now!

Document Details

Related Documents

Precalculus - Polynomial and Rational Functions

Precalculus - Functions

Precalculus - Exponential and Logarithmic Functions

Math Word Problems - Translating Expressions

Math Word Problems - Equations

Algebra II – Word Problems

Algebra II – Sequences and Series

Algebra II - Segments Lines and Inequalities

Algebra II - Relations and Functions

Algebra II - Rational Expressions

Company

Explore

Study Tools