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 collection of n integers 12, ,..., na a a , is said to form a complete set of residues modulo n if every integer is congruent modulo n to one and only one of the ak. To put it in another way, 12, ,..., na a a are congruent modulo n to 0, 1, 2, …, n – 1, taken in some order. For instance 26, 31, –1, 14, 11, 1, 9 constitute a complete set of residues modulo 7. One first important theorem provides a useful characterization of congruence modulo n in terms of remainders upon division by n. Theorem 1.1 For arbitrary integers a and b, (mod )a b n if and only if a and b leave the same nonnegative remainder when divided by n. Proof Example 1 Since the integers 26 and 31 can be expressed in the form 26 = 5(5) + 1 and 31 = 6(5) + 1 with the same remainder 1, Theorem 1.1 tells us that 26 31 (mod 5) . Conversely, the congruence 11 31 (mod 7)− implies that 11 and –31 have the same remainder when divided by 7.

Raffles Institution H3 Mathematics __________________________________________________________________________________ ________________ Chapter 4: Modular Arithmetic Page 3 of 9 Congruences may be viewed as a generalised form of equality, in the sense that its behaviour with respect to addition and multiplication is similar to that of ordinary equality. Some of the elementary properties of equality that carry over to congruences are shown in the following theorem. Theorem 1.2 Let n > 1 be fixed and a, b, c, d be arbitrary integers. Then the following properties hold: (a) (mod )a a n . (b) If (mod )a b n , then (mod )b a n . (c) If (mod )a b n and (mod )b c n then (mod )a c n . (d) If (mod )a b n and (mod )c d n , then (mod )a c b d n+  + and (mod )ac bd n . (e) If (mod )a b n , then (mod )a c b c n+  + and (mod )ac bc n . (f) If (mod )a b n , then (mod )kka b n for any positive integer k.

Raffles Institution H3 Mathematics __________________________________________________________________________________ ________________ Chapter 4: Modular Arithmetic Page 4 of 9 Before we go any further, let us see how the above properties can help us with carrying out certain types of computations. Example 2 Show that 41 divides 220 – 1. Example 3 Find the remainder when 1! + 2! + … + 99! + 100! is divided by 12. In Theorem 1.2, we saw that if (mod )a b n , then (mod )ac bc n . Is the converse true? Theorem 1.3 If (mod )ac bc n , then (mod )n dab , where d = gcd(c, n). Proof Theorem 1.3 is especially useful when c and n are coprime. Basically, with this additional condition, we are able to carry out ‘cancellation’ without a change in modulus: Corollary 1.1 If (mod )ac bc n and gcd(c, n) = 1, then (mod )a b n . A special case of the corollary is when n is a prime p. In this case, Corollary 1.2 If (mod )ac bc p and c is not a multiple of p, then (mod )a b p . Example 4 If 0 (mod )ab n , is it true that 0 (mod )an or 0 (mod )bn ? What if n is a prime number?

Raffles Institution H3 Mathematics __________________________________________________________________________________ ________________ Chapter 4: Modular Arithmetic Page 5 of 9 2 The Method of Infinite Descent Recall in Chapter 1 we have briefly talked about the Method of Infinite Descent introduced by Pierre de Fermat. Armed with tools from number theory (in particular congruences), let us look at a few Diophantine equations, and attempt to solve them. A Diophantine equation is an equation in which only integer solutions are allowed. When we tried to show that 2 is irrational, the equation we looked at, 2 n2 = m2, is a Diophantine equation since we are only interested in integer solutions. Example 5 Show that the equation 2 2 2 2x y z xyz+ + = has no integral solutions except x = y = z = 0. Example 6 Show that the equation 3 3 3240x y z+ + = has no integral solutions except x = y = z = 0. Perhaps the most renowned Diophantine Equation is that in the statement of Fermat’s Last Theorem. The theorem states that no three positive integers a, b and c satisfy the equation n n na b c+= for any positive integer strictly greater than 2.

Raffles Institution H3 Mathematics __________________________________________________________________________________ ________________ Chapter 4: Modular Arithmetic Page 6 of 9 This theorem was first conjectured by Pierre de Fermat in 1637 in the margin of a copy of Arithmetica where he claimed he had a proof that was too large to fit in the margin. The first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995, after 358 years of effort by mathematicians. The unsolved problem stimulated the development of algebraic number theory in the 19 th century and the proof of the