+0

0
266
2

Lizzie came up with a divisibility test for a certain number : m not equal to 1

Break a positive integer n into two-digit chunks, starting from the ones place. (For example, the number 354764 would break into the two-digit chunks 64,47,35)

Find the alternating sum of these two-digit numbers, by adding the first number, subtracting the second, adding the third, and so on. (In our example, this alternating sum would be 64-47+35=52)

Find m and show that this is indeed a divisibility test for m (by showing that n is divisible by m if and only if the result of this process is divisible by m).

Jun 6, 2021

#1
+288
+2

The value of m is 101.
In proof, first note that $100^0 \equiv 1 \pmod{101}$.
Also, for $i\ge0$, we have $100^{i+1} = 100\cdot 100^i \equiv (101-1)(100^i) \equiv -(100^i) \pmod{101}$.

Let $n=d_kd_{k-1}\ldots d_1 d_0$ be a positive integer written in base-10,
where $d_i$ is a number (written in base-10) and $0\le d_i \le 99$
for all $0\le i\le k$.
For example, if $n=354764$ then $k=2$, $d_2 = 35$, $d_1=47$, and
$d_0=64$. We have
$$n = \sum_{0\le i\le k} d_i \equiv \sum_{\substack{0\le i\le k\\ i\rm{\ even}}} d_i + \sum_{\substack{0\le i\le k\\ i\rm{\ odd}}} d_i \equiv \sum_{\substack{0\le i\le k\\ i\rm{\ even}}} d_i - \sum_{\substack{0\le i\le k\\ i\rm{\ odd}}} d_i \pmod{101}.$$

Jun 7, 2021
#2
+288
+1

The last line should be $n = \sum_{0\le i\le k} d_i\cdot (100)^i \equiv \cdots$ instead.

Jun 12, 2021