Determine all positive integers $d$ such that whenever $d$ divides a positive integer $n$, $d$ will also divide any integer obtained by rearranging the digits of $n$.
Problem
Source: Baltic Way 2011
Tags: number theory proposed, number theory
06.11.2011 16:39
WakeUp wrote: Determine all positive integers $d$ such that whenever $d$ divides a positive integer $n$, $d$ will also divide any integer obtained by rearranging the digits of $n$. Let $a=\overline{12x_1x_2...x_n}$ any multiple of $d$ beginning with $\overline{12}$ (which obviously exists) $d|a$ $\implies$ $d|b=\overline{x_1x_2...x_n21}$ and $d|c=\overline{x_1x_2...x_n12}$ and so $d|b-c=9$ and so $d\in\{1,3,9\}$ and obviously any three values fit. Hence the answer : $\boxed{d\in\{1,3,9\}}$
06.11.2011 20:22
Or, take a multiple $N$ of $d$, containing the digit $1$; then $d \mid 10N$. Arrange now as above the digits $\overline{10}$ and $\overline{01}$ at the end of two permutations of the digits of $10N$, otherwise coinciding. Then $d \mid 10 - 1 = 9$.
30.12.2021 21:20
We claim the only possible $d$ are $1,3,$ and $9.$ Let $a$ and $b$ be digits such that $a=b+1.$ Let $10^m\le d<10^{m+1}$ and consider $\overline{ab}10^{m+1}$ modulo $d.$ Notice it has residue $0\le r<d$ so $d\mid\overline{ab}10^{m+1}+d-r.$ But $$\overline{ab}10^{m+1}+d-r=\overline{abc_{m-1}c_{m-2}\dots c_{0}}$$as $0<d-r<10^{m+1}.$ Let $n=\overline{abc_{m-1}c_{m-2}\dots c_{0}}$ and note that $d\mid\overline{c_{m-1}c_{m-2}\dots c_{0}ab}$ and $d\mid\overline{c_{m-1}c_{m-2}\dots c_{0}ba}.$ Hence, $d\mid\overline{ab}-\overline{ba}=9.$ We can also check that $1,3,$ and $9$ are sufficient as they all divide the sum of the digits of $n.$ $\square$