We wrote last week on modular arithmetic, the arithmetic of remainders. Here we will examine a few other aspects of this huge subject. Modular arithmetic was advanced by Gauss in his Disquisitiones Arithmeticae. In this system, number wrap around when they reach a point known as the modulus. Numbers that differ by a multiple of the modulus are called congruent. Thus 4, 11 and 18 are all congruent modulo 7.
Addition table for numbers modulo 12.
If two numbers a and b leave the same remainder when divided by 10, they are said to be congruent modulo 10, written a ≡ b mod 10. More generally, if the remainder upon division by m is the same, we write a ≡ b mod m. In general, a ≡ b mod m means that ( a – b ) is divisible by m or is a multiple of m.
Congruence is an equivalence relation, that is, congruence of any two numbers is:
-
Reflexive: a ≡ a mod m
-
Symmetric: a ≡ b mod m implies b ≡ a mod m
-
Transitive: a ≡ b mod m and b ≡ c mod m imply a ≡ c mod m
Arithmetic modulo 12 is useful for measuring time, and also occurs in music theory. The set of numbers { 0, 1, 2, … , 11 } forms a group under modular addition, which we denote by Z/12Z. The addition table for this group is shown above. But the applications are far wider, so we look at modular arithmetic in a more abstract setting.
When computing modulo m, it is usually convenient to treat m as 0 so the values are { 0, 1, 2, … , m – 1 }. We can add and multiply numbers modulo m, giving the result modulo m. It is simple to show that if ( a ≡ a’ mod m ) and ( b ≡ b’ mod m ) then
( a + b ≡ a’ + b‘ mod m ) and ( a b ≡ a’ b’ mod m )
In particular, if a ≡ b mod m, then a = Am + b so
a2 = ( Am + b )2 = [ ( A2m + 2AB ) m + b2 ] ≡ b2 mod m
that is, a2 ≡ b2 mod m.
Groups, Rings and Fields
The integers Z form an Abelian group under addition. They may also be multiplied, giving the structure called a ring. Addition and multiplication may be combined, but the multiplicative inverse of an integer is not an integer (excepting 1). The introduction of a modulus m leads to the separation of the ring of integers into m subsets, which can de denoted by representative elements, the numbers { 0, 1, 2, … , m-1 }. This set is also written Z / mZ using the notation for the cosets of the subgroup of multiples of m. We saw above that if two numbers are congruent to two others, their sums and products are also congruent, so Z / mZ is also a ring. If m is a prime number, multiplication is invertable and Z / mZ is a finite field.
Application of modular Arithmetic: Last Digit of a Square
Is there a square number ending in 2? We list the first ten squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. There is no digit 2 at the end of any of these! We notice that the final digits are 1, 4, 9, 6, 5, 6, 9, 4, 1, 0. Now note thet 112 = 121 and 122 = 144 and 132 = 169. Is the sequence of final digits 1, 4, 9, … repeating? Yes: suppose N = 10p + q where p and q are each less than 10. The square is
N 2 = (10p + q )2 = 100 p2 + 20 pq + q2 = 10 ( 10 p2 + 2 pq ) + q2
which has the same final digit as q2.
The conclusion is that no square ends in 2. Indeed, the same is true for final digits 3, 7 and 8: no square ends in any of these digits.
Application of modular Arithmetic: Divisibility by 9
There is a simple test for divisibility by 9. Let us take the number 12345678. Is it divisible by 9? we write
12345678 = 1.107 + 2.106 + 3.105 + 4.104 + 5.103 + 6.102 + 7 .10 + 8
But, since 10 ≡ 1 mod 9 we have 102 ≡ 1 mod 9, 103 ≡ 1 mod 9 and in general 10k ≡ 1 mod 9, so
12345678 ≡ (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 ) mod 9
Thus, the number 12345678 is divisible by 9 if the sum of its digits is a multiple of 9. Indeed, this sum is 36, so the number 12345678 is indeed divisible by 9. Clearly, this holds generally: a number is divisible by 9 if the sum of its digits is a multiple of 9.
Source
Ben Green: Modular Arithmetic. Sec. III.8 in The Princeton Companion to Mathematics, Ed. Timothy Gowers. Princeton Univ. Press. 2008.
ThatsMaths 