June 17, 2022
Anna loves multiples of 11, but her friend Jane is not quite so keen. One day, Anna is flipping idly through the yellow pages (remember those?), which is full of 10-digit numbers. She notices that every 10-digit number seems to have an interesting property: It is either a multiple of 11, or it can be made a multiple of 11 by changing a single digit. For example, there are several ways to make the 10-digit number 5551234567 into a multiple of 11, such as changing the first digit to 4.
This gets the two friends wondering: Does every counting number have this property? Either prove it’s true for every number, or find the smallest counting number that is not a multiple of 11 and cannot be made a multiple of 11 by changing one digit.
Every counting number either is a multiple of 11 or can be made to be a multiple of 11 by changing one of its digits (in base 10).
Explanation:
This is a general proof of the following statement:
Every counting number either is a multiple of 11 or can be made to be a multiple of 11 by changing one of its digits (in base-10).
Without loss of generality (WLOG), let us assume all counting numbers have a leading digit of 0, which it can be changed. This is not needed for certain variations of the proof, but with this assumption the proof is equally valid and more streamlined.
First, let's do some groundwork on modulo arithmetic.
Consider a whole number \(n\) and divide it by 11: we obtain another integer, \(r\), representing the remainder of the division. Together with the quotient, \(q\), we have \(11q + r = n\). For \(r\) to be a valid remainder, it must be between 0 and 10, inclusive. Therefore, in modulo arithmetic, we can say that \(n \equiv r \mod 11\). In modulo arithmetic, this means that \(n\) is actually equivalent to \(r\) in field-11, i.e. a new universe where only 11 distinct numbers exist, and we are using the remainder when divided by 11 to represent those 11 distinct numbers. Therefore, all counting numbers form a "ring" of size 11, and as soon as you go from 0, 1, 2, ..., 10, you go back to 0 and continue with 1, 2, 3, ..., 10, 1, 2, 3, etc. We can actually go negative here. As the counting numbers form a ring of size 11, that means that for the number "-1" in the field of 11, it is actually equivalent to \(-1 + 11 = 10\).
This means we can equivalently say that the 11 distinct numbers that make up the field of 11 is: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5. For example: \(10 \equiv -1\), \(12 \equiv 1\), \(14 \equiv -2\) \(\mod 11\). This is a much clearer way of representing numbers in the field of 11 because to obtain the sum of two numbers that add to 11, for example, we look at the equivalence of the first number, and we construct a second number such that it is the negative of the first number in its equivalent field-11 representation (a sort of antimatter annihilating matter, if you will). For example, 67 + ? gives you a multiple of 11? Well, \(67 \equiv 1\), and so we simply need to find a number equivalent to -1 in field-11, say 21, and indeed: \(67 + 21 = 88\) which is divisible by 11.
Other than the field, modulo arithmetic works exactly the way "regular" arithmetic works in terms of addition and multiplication. This is important to note for the next section.
Now consider the number \(1 = 10^0\). Clearly, it is equivalent to 1 \(\mod 11\), i.e. itself. The number 10, however, is equivalent to -1. What about higher powers of 10? Well, \(100 = 10 \times 10\), and since 10 is equivalent to -1, 100 is equivalent to \(-1 \times -1 = 1\). Similarly, \(1000 = 100 \times 10\) which is equivalent to \(1 \times -1\) getting back to -1 again. Keep going, and we have the following rule:
\(N = 10^m \equiv (-1)^m \mod 11\) for \(m = 0, 1, 2, \dots\) That is, even powers of 10 is equivalent to 1, while odd powers is equivalent to -1. A number is equivalent to itself times multiples of 100 , mod 11.
Consider a number with \(N\) digits. WLOG let \(N\) be even, such that if the number of digits is odd, add a leading 0. In base-10, \(N = \sum_{k=0}^{N-1} d_k 10^k\). Here \(d_k\) is the \(k\)th digit of \(N\).
Let's consider the first two digits of \(N\). If we increase the value of the ones digit by 1, we increment its equivalent value by 1 mod 11 since the ones digit is multiplied by \(1 = 10^0\), an even power of 10 that is equivalent to 1 mod 11. On the other hand, if we raise the value of the tens digit by 1, we decrease its equivalent value by 1 mod 11 since the tens digit is multiplied by \(10 = 10^1\), an odd power of 10 that is equivalent to -1 mod 11. So with those two digits, we can let that number of be equivalent to one of the 11 distinct numbers in field-11: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 by changing at most one digit. The reason is because the circular distance between any two numbers in the above set, when placed on a "circular" number line in field-11 is no more than 5. We can always go from one number to the second one in either direction by incrementing/decreasing either the ones digit or the tens digit. Each digit manipulation is going a different direction on that circular number line because \(N = 10^m \equiv (-1)^m \mod 11\) for \(m = 0, 1, 2, \dots\).
The detailed strategy (to supplement the proof) is as follows:
It is shown that a number mod 11 is equivalent to itself multiplied by 100 and multiples of 100. That means we can simply look at the first \(N-2\) digits of our number, figure out its modulo in field-11, and make the leading two digits equivalent to the negative of that number and we are done. If we only have 1 leading digit, make the leading digit a 0 in our assumption. This combined with the shown fact that we can change at most one digit in a two digit number to reach any desired number in field-11 completes our proof.
Let's use the one in the puzzle. The number \(5551234567\) has the first 8 digits being \(51234567 \equiv -1 \mod 11\). Therefore, we need to have the leading two digits, \(55\), changed such that it is equivalent to the negative of (-1), which is 1. The number 55 is equivalent to 0, and our target is 1, which is a distance of 1 going to the right. We can achieve this by increasing the "ones" digit of 55 by 1, i.e making 56, or equivalently as the puzzle suggested, decreasing the tens digit by 1 to obtain 45. Both cases work: \(5651234567/11 = 513748597\) and \(4551234567/11 = 413748597\).