RI Chapter 3 Introduction to Divisibility

RAFFLES INSTITUTION H3 Mathematics (9820) ________________ Chapter 3: Introduction to Divisibility Page 1 of 14 Chapter 3: Introduction to Divisibility SYLLABUS INCLUDES Students will learn to prove properties and results, and solve non-routine problems involving: Primes, coprimes, divisibility, modulo arithmetic, greatest common divisor, division algorithm Students may use the following theorems and results in Numbers. (i) (The Fundamental Theorem of Arithmetic) Every integer n  1 can be expressed as a product of primes in a unique way apart from the order of the prime factors. (ii) There exist infinitely many primes. (iii) (Division Algorithm) Let a be an integer a nd b a positive integer. Then there exists unique integers q and r, with 0  r < b, such that a = bq + r. (iv) If a and b are positive integers, then their greatest common divisor (gcd) is a linear combination of a and b, that is, there exists integers s and t such that gcd(a, b) = sa + tb. CONTENT 1 Introduction 2 Divisibility 2.1 Division Algorithm 2.2 Greatest Common Divisor (GCD) 2.3 Prime and Composite Numbers 2.4 Lowest Common Multiple (LCM)

Raffles Institution H3 Mathematics _________________________________________________________________________________________ ________________ Chapter 3: Introduction to Divisibility Page 2 of 14 1 Introduction Johann Carl Friedrich Gauss , German mathematician, astronomer and physicist said “Die Mathematik ist die Königin der Wissenschaften und die Zahlentheorie ist die Königin der Mathematik,” which translated, means “ Mathematics is the queen of sciences and number theory is the queen of mathematics.” So perhaps it is appropriate that we begin our course with number theory. So what exactly is number theory? In short, it is the study of natural numbers and the integers . The theory of numbers is one of the oldest branches of mathematics, and can be traced back to the Greeks and ancient Egyptians. However, the first rudiments of an actual theory are generally credited to Pythagoras and his disciples. 2 Divisibility 2.1 Division Algorithm One theorem, the Division Algorithm, acts as the foundation stone upon which most of our results are built on. Theorem 2.1.1 (Division Algorithm) Given integers a and b, with 0b , there exist unique integers q and r satisfying , 0a qb r r b= +   The integers q and r are called, respectively, the quotient and remainder in the division of a by b. The proof of this result is not required for the H3 syllabus, but this result should be intuitive. For example, when we divide 17 by 5, we have a quotient of 3 and a remainder of 2. The theorem assures us that the quotient and remainder we speak of are unique. However, let us illustrate the division algorithm when we replace the r estriction that b must be positive by the simple requirement that 0b . For example, let us take 7b=− . Then, for the choices of 1, 2,61 and 59a= − − , we obtain the expressions 1 = 0(-7) +1 -2 = 1(-7) + 5 61 = (-8)(-7) + 5 -59 = 9(-7) + 4 We wish to focus our attention on the applications of the Division Algorithm, and not so much on the algorithm itself. As a first illustration, note that with b = 2, the possible remainders are r = 0 and r = 1. When r = 0, the intege r a has the form a = 2q and is called even; when r = 1, the integer a has the form a = 2q + 1 and is called odd. Now 2a is either of the form 2 2 2(2 ) 4aqq== or 2 2 2(2 1) 4( ) 1a q q q= + = + + . The point to be made here is that the square of an integer always leaves the remainder of 0 or 1 upon division by 4.

Raffles Institution H3 Mathematics _________________________________________________________________________________________ ________________ Chapter 3: Introduction to Divisibility Page 3 of 14 Example 2.1.1 Show that the square of any odd integer leaves a remainder of 1 when divided by 8. Example 2.1.2 Show that 2( 2) 3 aa + is an integer for all 1a . 2.2 Greatest Common Divisor (GCD) Of special significance is the case in which the remainder in the Division Algorithm turns out to be zero. Let us look at this case now. Definition 2.2.1 An integer b is said to be divisible by an integer 0a , which we denote by |ab , if there exists some integer c such that b = ac. We write a | b to indicate that b is not divisible by a. Thus, for example, −12 is divisible by 4, because −12 = 4(−3). However, 31 is not divisible by 3; since there is no integer c satisfying 31 = 3c. There are also other ways to say |ab than b is divisible by a. We can equivalently say that a is a divisor of b, that a is a factor of b, a divides b or b is a multiple of a. Do also note that whenever the notation |ab is employed, it is understood that a is different from zero. We also note that if a is a divisor of b, then b is also divisible by –a (why?), so that the divisors of an integer always occur in pairs. To find all the divisors of a given integer, it is sufficient to obtain the positive divisors and then adjoin them to the correspo nding negative integers. For this reason, we shall usually limit ourselves to a consideration of the positive divisors.

Raffles Institution H3 Mathematics _________________________________________________________________________________________ ________________ Chapter 3: Introduction to Divisibility Page 4 of 14 The following theorem is a list of results that follow from Definition 2.2.1. You should be able to prove them by yourself. Theorem 2.2.1 For integers a, b, c, the following hold: (a) |0a , 1| a , |aa . (b) |1a if and only if 1.a= (c) If |ab and |cd , then |ac bd . (d) If |ab and |bc , then |ac (transitivity). (e) |ab and |ba if and only if ab= . (f) If |ab and 0b , then ab . (g) If |ab and |ac , then | ( )a bx cy+ for arbitrary integers x and y. It is also worth pointing out that property (g) extends by induction to sums of more than two terms. That is, if | kab for k = 1, 2, …, n, then 1 1 2 2| ( ... ) nna b x b x b x+ + + for all integers ix . Example 2.2.1 Find all integers n such that 2 1| 1nn++ .

Raffles Institution H3 Mathematics _________________________________________________________________________________________ ________________ Chapter 3: Introduction to Divisibility Page 5 of 14 If a and b are arbitrary integers, then an integer d is said to the a common divisor of a and b if both |da and |db . Because 1 is a divisor of every integer, 1 is a common divisor of a and b. Hence the set of positive common divisors is nonempty . Now every integer divides zero, so that if a = b = 0, then every integer serves as a common divisor of a and b. In this instance, the set of positive common divisors of a and b is infinite. However, when at least one of a or b is nonzero, there are only a finite number of positive common divisors. Among these, there is a largest one, which will call the greatest common divisor of a and b. Definition 2.2.2 (Greatest Common Divisor) Let a and b be given integers, with at least one of them different from z ero. The greatest common divisor of a and b, which we denote by gcd( a, b), is the positive integer d satisfying the following: (a) |da and |db (b) If |ca and |cb , then cd . Example 2.2.2 Find (a) gcd(5, −5) (b) gcd(8, 17) (c) gcd(−8, −36) It is easy to compute the gcd of 2 numbers when they are small. What happens when they are large? We will discuss 2 methods in Section 2.3 and 2.4. 2.3 Prime and composite numbers Since number theory is about the study of numbers, it is perhaps important for us to look at what we call the building blocks of these numbers, which are the prime numbers. So what are prime numbers? Def