# The positive integer $k$ has the property that for all $m \in \mathbb{N}$, $k \mid m \implies k \mid m_r$. Show that $k \mid 99$.

Question from Engel's book Problem solving strategies.

The positive integer $$k$$ has the property that for all $$m \in \mathbb{N}$$, $$k \mid m \implies k \mid m_r$$, where $$m_r$$ is the reflection of $$m$$, i.e. if $$m=1234$$ then $$m_r = 4321$$. Show that $$k \mid 99$$.

I start with a small case, say $$k$$ divides some 2 digit number $$ab$$. Then $$k$$ divides $$ba$$ also. Since $$ab = 10a+b$$ and $$ba=10b+a$$, I eliminate $$a$$ to get $$k \mid -99b$$. $$b$$ is a 1 digit number, so I think I need to use this fact somehow, but I am stuck here.

For the 3 digit case, let the number be $$abc$$. By similar reasoning, I get that $$k$$ divides $$99a-99b = 99(a-b)$$. Again, a-b is small, so maybe I can brute force this.

I have considered trying to show that $$k$$ must be a palindrome? Since $$k \mid k$$, we have $$k \mid k_r$$, and maybe try to get something? Thanks for the help!

• Note: $k$ divides itself...... Jul 3 '19 at 5:39
• Are you familiar with the old "magic" trick that if you have $abc - cba = def$ then $def+fed = 1089$? Can you generalize that? Jul 3 '19 at 6:03
• Thats a very cool trick! But I think it doesn't generalize that well. For 5 digits number $abcde$, if think you need $a>e$ and $b>d$. Jul 3 '19 at 7:29
• For example, 54321 - 12345 = 41976. 41976 + 67914 = 109890. But 51234 - 43215 = 8019, and 8019 + 9108 = 17127. Jul 3 '19 at 7:31
• I think $k$ cannot have last digit $2,4,5,6,8$. For e.g. if $k$ has last digit 8, we know that no multiple of $k$ has last digit 1. Then we just pick a multiple of $k$ that begins with $1$ to get a contradiction. E.g. if $k=28$, then pick $m=28 \times 6=168$. $k$ divides $168$ but not $861$. Jul 3 '19 at 7:34

Let's just look at the divisibility rules for 3, 9, and 11. If 3 or 9 divides a number's sum of its digits then it's divides the number. If 11 divides the number you get from the alternating sum of its digits, then 11 divides the number.

Let's enumerate the digits of $$m$$ with subscripts so that $$m_1$$ is the first digit and $$m_n$$ is the last where $$m$$ is an $$n$$ digit long number.

The sum of the digits is $$S=\sum_{i=1} ^n m_i$$, and the alternating sum $$S_a=\sum_{i=1} ^n (-1)^{n+1}m_i$$.

If $$\ 9 \ | \ S$$, then $$\ 9\ | \ m_r \$$ just by the law of communicative addition.

Similarly if $$\ 11\ |\ S_a$$, then $$\ 11 \ | \ m_r$$ . The reason being that if $$n$$ is odd the same digits will be negative in the sum $$S_a$$ regardless of the order being reversed, and if $$n$$ is even then the sum will be opposite in parity but the same magnitude.

Ex: Odd $$n$$: the number $$94572$$

$$m_r: 94572 \to 27549$$

$$9-4+5-7+2=2-7+5-4+9$$

Ex: Even $$n$$:the number $$9457$$

$$m_r: 9457 \to 7549$$

$$9-4+5-7 = - (7-5+4-9)$$

• But just because you can find numbers that that $k$ can divide that are multiples of $9$ and $11$ (and you can do that for any $k$ whether they have to property or not) doesn't mean that $k$ divides $9*11$. Jul 3 '19 at 21:38
• @fleablood what do you mean exactly? I'll change it if shown wrong for sure , especially with a counter example Jul 3 '19 at 21:59
• @fleablood IF $k$ divides $m$ and $m_r$ simultaneously then $k$ must have $9$ and or $11$ as a factor Jul 3 '19 at 22:04
• Yes,, but having $9$ and $11$ as factors doesn't mean those are the only factors. Suppose $k = 63=7*9$ then $63\not \mid 9$. You must prove $k$ has no other factors. And if you do prove that, you must prove that $k = 3^m 11^n$ then $m \le 2$ and $n \le 1$ Jul 3 '19 at 22:22
• @fleablood I get what you're saying. But 63 wouldn't then divide $m$ or $m_r$ and the implication holds because the predicate isn't met. But to prove that only 9 and 11 work to me would involve some linear algebra and basically more time. Hopefully I can edit this later Jul 4 '19 at 0:14

HINT

Write $$k = \sum_{i=0}^{r_k}10^ix_i$$ where $$x_i \in \{0,...,9\}$$.

Since $$k | k \implies k | k_r$$, we have

$$\sum_{i=0}^{r_k}10^ix_i \quad \biggr{|} \quad\sum_{i=0}^{r_k}10^ix_{(r_k-i)},$$ $$\implies \lambda\sum_{i=0}^{r_k}10^ix_i = \sum_{i=0}^{r_k}10^ix_{(r_k-i)},$$ $$\implies 0 = \sum_{i=0}^{r_k}10^i(x_{(r_k-i)}-\lambda x_i),$$ $$\implies 0 = x_{(r_k-i)}-\lambda x_i \quad \forall i.$$

We therefore have that $$k$$ is a palindrome.