Divisibility Shortcut
Our main tools are decimal expansion of positive integers and some rules about the “remainder” when a number is divided by 11.
All mentions of the remainder are referring to division by 11.
Remainder Rules
Consider two numbers a = 11×q+r and b=11×k+m. The quotients of a and b upon division by 11 are q and k. And the remainders are r and m. What happens to the quotients and the remainders when I multiply a and b?
Observe that the remainder¹ of the final answer is the product of the remainders of a and b.
This reasoning can be extended to prove a rule for powers. How does the remainder of a raised to some power relate to the remainder of a?
Decimal Expansion
Since 10 can be written as 11+(-1), we will think of -1 as the “remainder” here¹. Applying Rule 2, we can reason that the remainder of 10³ = (-1)³. Using Rule 1, we can reason that the remainder of 2×(10)³=2×remainder of 10³ (the remainder of 2 upon division by 11 is 2).
Since all numbers greater than zero and less than 11 are indivisible by 11, no single term in the decimal expansion above is divisible by 11. Each term will have some remainder which adds to the “remainder” of 12345 as a whole.
Our objective here is to check if 12345 is divisible by 11 or not. In other words, we need to check if the remainder of 12345 upon division by 11 is 0 or not since any number divisible by 11 can be written as 11n + 0.
Since we are only concerned with the remainders, lets substitute the remainder of 10 in place of 10 in the decimal expansion of 12345.
If this combined remainder is equal to 0, then 12345 is divisible by 11 since a number is divisible by 11 if and only if its remainder upon division by 11 is 0.
If adding up all the individual remainders gives us a number greater than 11, we would then check if it is divisible by 11 by repeating the same process until we get to a single digit. This is the final remainder. If it equals 0, only then will the whole number be divisible by 11.
So, in summary, to check if any number is divisible by 11, we take the alternating sum(a sum in which the sign alternates between positive and negative) of its digits starting from the ones digit. For 123456789, this process would yield
Hence, 123456789 is not divisible by 11.
Multiplying Palindromes with 1s
A palindrome is a sequence of characters which reads the same forwards and backwards e.g. abccba and 12211221.
Multiplying a palindrome with 1s results in another palindrome(there is an if, which we will discuss later).
Lets consider 1221×11111
Writing this differently,
Notice that I have labelled each term in the sum as a row. I have made the number of digits of all rows equal by adding zeroes on the left. The counting starts from zero because I want the row number to equal the number of zeroes to the left of each row. Consequently, the last row has n zeroes (this is Rule 3).
There is a “symmetry” here and observation reveals why this is a palindrome. But why exactly should all expression of the form Palindrome×1s equal another palindrome? For the sake of generalization, let the last row’s number be n.
Since the number of digits is the same for all rows and every row has four common digits: 1, 2, 2 and 1, the number of remaining digits is also the same. The remaining digits are all zeroes, so the number of zeroes is the same for all rows (this is Rule 4). Because the last row has n zeroes(Rule 3) and every row has equal number of zeroes(Rule 4), all rows have n zeroes (this is Rule 5).
In the example above focus on Row 0 and Row 4. If I read Row 0 backwards, it will become Row 4. The same is true for Row 1 and Row 3. In general, this is true for any Row x and Row n-x. Hence, if I add Row x and Row n-x, what will I get? A palindrome! e.g.
Pairing and adding all rows in this way, we get palindromes which have the same number of digits. If I add palindromes of the same number of digits together, it makes sense that they will be palindromes.
If there are odd number of rows, then the middle row will remain unpaired. Such a row must already be a palindrome. Why? Since this row is at the midpoint of the nth and 0th rows, its number is n/2. Recall our observation that the number of zeroes to the left are equal to the label of the row. Hence, this term has n/2 zeroes to the left. We know that the zeroes must add up to n(Rule 5). So this term must have n/2 zeroes to the right. The center part is already a palindrome i.e. the one we multiplied by the 1s. Thus, the whole number is a palindrome.
In summary, we add pairs of Row x and Row n-x which are all palindromes of the same length(adding zeroes to the left if necessary). Then we add those palindromes together to get our final palindrome.
We have actually assumed that this process does not involve adding two digits whose sum exceeds 9, which would break the “symmetry”. The argument about the sum of palindromes of same number of digits is dependent on the absence of this condition. For example, 1881 + 1221 = 3102. Notice how the operation of adding to a number greater than 9 affects two digits at a time which is specifically why the “symmetry” is broken.
YOU DON’T NEED TO UNDERSTAND WHAT FOLLOWS.
¹ If the product exceeds 11, the actual remainder will be the remainder of r×m. The same goes for r raised to the power of n.
² For those who are familiar with modular arithmetic: -1 is actually not the remainder. The remainder is actually 10, but Since 10 is congruent to -1 modulo 11, treating it as a remainder will yield no incorrect result.
