3 Greatest Common Divisor 17

Contents

• Introduction 1
• Divisibility 9
• Greatest Common Divisor 17
• Primes 29
• Congruences 37
• Special Congruences 43
• Primitive Roots 49
• Cryptography 55
• Quadratic Residues 61

10 Applications of Quadratic Residues 69 11 Diophantine Equations 75 12 Further Diophantine Equations 79 13 Continued Fractions 87 14 Continued Fraction Expansions of Quadratic Irrationals 97 15 Arithmetic Functions 105 16 Large Primes 121 17 Analytic Number Theory 127 18 Elliptic Curves 135 References 151 (Introduction to Number Theory, 2e Anthony Vazzana) (Solution Manual all Chapters) 1 / 4

Chapter 1 Introduction 1.1 (a+b) 3 = (a+b) 2 (a+b) = (a 2

• 2ab+b

2 )(a+b) (by Example 1.1) = (a 2

• 2ab+b

2 )a+ (a 2

• 2ab+b

2 )b (distributive law) =a(a 2

• 2ab+b

2

• +b(a

2

• 2ab+b

2

• (commutative law)

=aa 2 +a(2ab+b 2

• +ba

2 +b(2ab+b 2

• (distributive law)

=aa 2 +a(2ab) +ab 2 +ba 2 +b(2ab) +bb 2 (distributive law) =a 3

• 2a

2 b+ab 2 +a 2 b+ 2ab 2 +b 3 (commutative law) =a 3

• 3a

2 b+ 3ab 2 +b 3 1.2(a) Suppose thata < b. Thena+x=b, for some natural numberx.Addingcto both sides of this equation, we obtain

(a+x) +c=b+c:

Using the associativity and commutativity of addition, we may rewrite this as (a+c) +x=b+c; and soa+c < b+c. Now suppose thata+c < b+c. Then a+c+x=b+cfor some natural numberx. By cancelation, we see thata+x=b, and soa < b.(b) Suppose thata < b. Thena+x=b, for some natural numberx.Multiplying both sides of this equation byc, we obtain

(a+x)c=bc:

Using the distributivity, we may rewrite this as ac+xc=bc; and soac < bc. Now suppose thatac < bc. Clearly,a6=bsince that would implyac < ac. Ifb < a, then by what we have proved already,bc < ac, which would be a contradiction. Thus, by the trichotomy law,a < b.

1 2 / 4

21 Introduction 1.3Suppose thatab= 1. Ifa6= 1, then by the trichotomy law,a >1.Using the preceding exercise, we have 1 =ab >(1)b=b. Thus we have a contradiction, and soa= 1. Likewise,b= 1.

1.4Suppose thata < b. Thena+c=b, for some natural numberc. Hence a 2

• 2ac+c

2 =b 2 , and soa 2 < b 2 .Suppose thata 2 < b 2 . By the trichotomy law, exactly one of the follow-

ing statements is true:a=b,a < b, orb < a. Ifa=b, thena

2 =b 2 , which is false. Ifb < a, then by the foregoing argument,b 2 < a 2 , which is false. Thereforea < b.y1.5All of the properties of natural numbers given in this section hold forZ.The multiplicative cancelation property (ac=bcimpliesa=b) holds whenc6= 0. (Note that some of the properties regarding inequalities from the exercises above do not hold.) In addition, the setZhas an identity element \0," which satises the propertya+ 0 =afor all integersa. Each element also has an additive inverse. That is, given an integera, there exists a numberbsuch thata+b= 0.

1.6Given a cancelation property forZ, ifab= 0 anda6= 0, thenab=a0 implies thatb= 0.

1.7We denea < bwhenba >0.

1.8Withn= 1 the statement simply asserts that 1 = 1 2 , which is cer- tainly true. Now suppose that the statement holds for a numbern1.Applying this hypothesis to then+ 1 case, we have

• + 3 + 5 + + (2n1) + (2(n+ 1)1) =n

2

• (2n+ 21) = (n+ 1)

2

:

Thus, the statement holds in then+ 1 case as well, and so by the principle of mathematical induction it holds for alln1.

1.9In then= 1 case the statement holds as 1 2 =

(1)(1 + 1)(2(1) + 1)

6

:

Now suppose that for somen, 1 2

• 2

2

• 3

2

• +n

2 = n(n+ 1)(2n+ 1) 6

:

Adding (n+ 1) 2 to both sides, we obtain 3 / 4

3 1 2

• 2

2

• 3

2

• +n

2

• (n+ 1)

2 = n(n+ 1)(2n+ 1) 6

• (n+ 1)

2 = (n+ 1)(n(2n+ 1) + 6(n+ 1)) 6 = (n+ 1)(2n 2

• 7n+ 6)

6 = (n+ 1)(n+ 2)(2(n+ 1) + 1) 6

:

Thus, the statement holds in then+ 1 case as well, and so by the principle of mathematical induction, it holds for alln1.

1.10The formula holds forn= 0, since 2

= 2 1

• Assume that the formula

holds for somen0. Then n+1 X k=0 2 k = 2 n+1

• + 2

n+1 = 22 n+1

• = 2

n+2

1:

Hence, the formula holds for alln0.

1.11The statement clearly holds whenn= 0. We note that it also holds forn= 1. Now suppose that it holds for some natural numbern1.We will show that it also holds for the numbern+ 1. Starting with our inductive hypothesis thatn <2 n , we have 2n <2 n+1

:

Now sincen1, we know that 2nn+ 1, and so it follows that n+ 1<2 n+1 . Thus, the statement holds in then+ 1 case as well, and so by the principle of mathematical induction, it holds for alln0.

1.12The inequality clearly holds whenn= 1. Suppose that it holds for some natural numbern1. Then (1 +x) n+1 = (1 +x) n (1 +x) (1 +nx)(1 +x) (since 1 + x0) = 1 + (n+ 1)x+nx 2

1 + (n+ 1)x:

Hence, the inequality holds for alln1.

1.13We see that the formula holds forn= 1, since 2 1

• (1)

1 = 1 =a1, and forn= 2, since 2 2

• (1)

2 = 5 =a2.

• / 4