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 t