RI Chapter 4 Modular Arithmetic

RAFFLES INSTITUTION H3 Mathematics (9820) ____________________ Chapter 4: Modular Arithmetic Page 1 of 9 Chapter 4: Modular Arithmetic SYLLABUS INCLUDES Students will learn to prove properties and results, and solve non-routine problems involving: Modulo arithmetic CONTENT 1 Introduction to Modulo Arithmetic 2 The Method of Infinite Descent 1 Introduction to Modulo Arithmetic Another approach to divisibility questions is through the arithmetic of remainders, or the theory of congruences or modular arithmetic as it is now commonly known. The concept, and the notation that makes it such a powerful tool, was once again introduced by Gauss, in his Disquisitiones Arithmeticae; this monumental work, which appeared in 1801 when Gauss was 24 years old, laid the foundations of modern number theory. In his first chapter, Gauss introduces the concept of congruence and the notation that m akes it such a powerful technique (he explains later that he was induced to use the symbol  because of the close analogy with algebraic equality). According to Gauss, “If a number n measures the difference between two numbers a and b, then a and b are said to be congruent to n; if not, incongruent.” Putting this into the form of a definition, we have Definition 1.1 Let n be a fixed positive integer. Two integers a and b are said to be congruent modulo n, denoted by (mod )a b n if n divides the difference a – b; that is, provided that a – b = kn for some integer k. Let us have a concrete idea. Consider the case n = 2. It is easy to check that 17 1 (mod 2), 31 1 (mod 2), 26 0 (mod 2)   In fact, you should see that what modulo 2 does is to split the integers into 2 sets, the odd integers, which are all congruent to 1 modulo 2, and the even integers, which are all congruent to 0 modulo 2.

Raffles Institution H3 Mathematics __________________________________________________________________________________ ________________ Chapter 4: Modular Arithmetic Page 2 of 9 To further fix our idea, let us look at modulo 5. 17 2 (mod 5), 31 1 (mod 5), 26 4 (mod 5)  −  since 17 – 2 = 3(5), 31 – 1 = 6(5) and –26 – 4 = –6(5). When | ( )n a b − , we say that a is incongruent to b modulo n , and in this case we write (mod )a b n . For example, 26 7 (mod 5) . Recall the Division Algorithm, which states that: Given integers a and n, with 0n , there exist unique integers q and r satisfying , 0a qn r r b= +   The integers q and r are called, respectively, the quotient and remainder in the division of a by n. Then, by the definition of congruence, (mod )a r n . Because there are n choices for r, we see that every integer is congruent modulo n to exactly one of the values 0, 1, 2, …, n – 1; in particular, 0 (mod )an if and only if n | a. The set of n integers {0, 1, 2, …, n – 1} is called the set of least nonnegative residues modulo n. In general, a co