5.1 Congruences
In order to motivate the discussion, let us consider the following two problems.Show that an integer is divisible by 9 if and only if the sum of its digits is divisible by 9
Solution. If a number \(x\) is expressed in the form \(x_nx_{n-1}\cdots x_0\) this really means the number is equal to \(x_n\times10^{n}+\cdots + x_1\times10+x_0\). Now \(10^n=9k_n+1\) for some \(k_n\) so \(x=(9k_n+1)x_n+\cdots +(9k_1+1)x_1+x_0\). We can rearrange this as \(9(k_nx_n+\cdots +k_1x_1)+x_n+\cdots + x_0\), so by the remainder theorem \(x\) has the same remainder on division by \(9\) as does \(x_n+\cdots + x_0\).
Is \(22051946\) a perfect square ?
We could solve this by computing \(\sqrt{22051946}\) and determining whether it is an integer, or alternatively by squaring various integers and seeing whether \(22051946\) occurs.
There is a much simpler way of seeing that this number cannot be a perfect square.
In Example 3.6 of Chapter 3 we showed that a perfect square must leave a remainder \(0\) or \(1\) when divided by \(4\).
By looking at its last two digits, we see that \[22051946=220519\times 100+46=220519\times 25\times 4+46\] leaves the same remainder as \(46\), and since \(46=11\times 4+2\) this remainder is \(2\). It follows that \(22051946\) is NOT a perfect square.
Show that the last decimal digit of a perfect square cannot be \(2, 3, 7\) or \(8\). Is \(3190491\) a perfect square ?
Let \(n\) be a positive integer, and let \(a\) and \(b\) be any integers. We say that \(a\) is congruent to \(b\text{ mod }(n)\), or \(a\) is a residue of \(b\text{ mod }(n)\), and we write \[a\equiv b\text{ mod }(n)\,,\] if \(a\) and \(b\) leave the same remainder when divided by \(n\). The number \(n\) is referred to as the modulus and the arithmetic of congruences, which we shall describe shortly, is called modular arithmetic.
To calculate residues, we use the Remainder Theorem (Theorem 3.4) to put \(a=qn+r\) with \(0\leq r<n\), and \(b=q'n+r'\) with \(0\leq r'<n\), and then we say that \(a\equiv b\text{ mod }(n)\) if and only if \(r=r'\).
We will often write simply \(a\equiv b\) if it is clear what the value of the modulus \(n\) is.
- \(100\equiv 10\equiv 1\text{ mod }(9)\) in Example 5.1
- \(22051946\equiv 46\equiv 2\text{ mod }(4)\) in Example 5.2.
Show that \(392\equiv1\text{ mod }(23)\).
As you may expect, we will use the notation \(a\not\equiv b\text{ mod }(n)\) to denote that \(a\) and \(b\) are not congruent \(\text{mod }(n)\), in other words if they leave different remainders when divided by \(n\).
Casting out nines
Our first example in this chapter can now be reformulated in the following way:
We can use this fact to solve the following problem.
Show that rearranging the digits of a power of \(2\) cannot yield another power of \(2\). (Here we do not allow rearrangements which bring \(0\) to the front. )
Solution. If we rearrange the digits then the two numbers have the same digit sum and therefore are congruent mod \(9\). Now if we examine the table of powers of \(2\) we see that \(2^0\equiv 1\), \(2^1\equiv 2\), \(2^2\equiv 4\), \(2^3\equiv 8\), \(2^4\equiv 7\), \(2^5\equiv 5\), \(2^6\equiv 1\) and that this pattern then cycles with period 6. So if two powers of \(2\) are congruent mod \(9\) then they are of the form \(2^n\) and \(2^{n+6k}\) for some \(k\). It follows that one of them is at least \(64\) times bigger than the other so they cannot have the same number of digits.
A useful alternative definition of congruence \(\text{mod }(n)\)
For any fixed \(n\geq 1\) we have \(a\equiv b\text{ mod }(n)\) if and only if \(n\,|\,(a-b)\).
Proof. Using the Remainder Theorem we let \(a=qn+r\) and \(b=q'n+r'\) so that \[a-b=(q-q')n+(r-r')\] with \(-n<r-r'<n.\) If \(a\equiv b \text{ mod}~(n)\) then \(r=r'\), so that \(r-r'=0\) and hence \(a-b=(q-q')n\), which is divisible by \(n\). Conversely, if \(n\) divides \(a-b\) then it divides the difference \((a-b)-(q-q')n=r-r'\) and since the only integer strictly between \(-n\) and \(n\) which is divisible by \(n\) is \(0\), then \(r-r'=0\), which means \(r=r'\). Hence \(a\equiv b\text{ mod}~(n)\) as required.
For any \(n\ge 1\),
- \(a\equiv a\) for all integers \(a\);
- if \(a\equiv b\) then \(b\equiv a\);
- if \(a\equiv b\) and \(b\equiv c\) then \(a\equiv c\).
Proof. Let \(n\ge 1\).
- We have \(n|(a-a)\) for all \(a\).
- If \(n|(a-b)\) then clearly \(n|(b-a)\).
- If \(n|(a-b)\) and \(n|(b-c)\) then \(n|\left((a-b)+(b-c)\right)=a-c\).