Smallest positive integer problem.

Question

I had trouble solving a number theory problem in the "Art of Problem Solving - Alcumus" page:

Suppose that $\overline{abcd}$ is a four-digit integer with no digits equal to zero such that $\overline{ab}$, $\overline{bc}$, and $\overline{cd}$ are distinct integers that each divide into $\overline{abcd}$. Find the smallest possible value of $\overline{abcd}$.

I initially tried to express the info I'm being given into something I could work with like this:

Since $\overline{ab}\mid \overline{abcd}=1000a+100b+10c+d=100\overline{ab}+\overline{cd}$ then $\overline{ab}\mid \overline{cd}$ and since $\overline{cd}\mid \overline{abcd}=100\overline{ab}+\overline{cd}$ then $\overline{cd}\mid 100\overline{ab}$.

Then I proceeded by splitting the problem into two cases, inspired from the last relation: whether the $\gcd(100,\overline{ab})=1$ or not.

If the $\gcd(100,\overline{ab})=1$ then we can say that since $\overline{cd}\mid 100\overline{ab}$ we have either $\overline{cd}\mid 100$ or $\overline{cd}\mid \overline{ab}$. So when $\overline{cd}\mid 100$, taking into consideration that $c,d$ are integers from $1$ to $9$, the only possible values for $c$ and $d$ I could deduce are $(c,d)=(2,5)$, but then don't forget that $\overline{ab}\mid \overline{cd}$, so $\overline{ab}\mid 25$ which yields $(a,b)=(2,5)$, contradiction because $\overline{ab}$ and $\overline{cd}$ must be distinct. When $\overline{cd}\mid \overline{ab}$, we also have that $\overline{ab}\mid \overline{cd}$, which means $\overline{ab}=\overline{cd}$, again, contradiction for the same reason.

So I assumed my thought process was correct here, I went on to check the other case when the $\gcd(100,\overline{ab})$ is not $1$ and found the smallest integer solution to be $(a,b,c,d)=(1,4,2,8)$ which was incorrect. The right answer is the number $1155$, something I was very confused by since the $\gcd(100,11)=1$, so I am asking you for some insight into what I am doing wrong, as well as into whether the number $1428$ is indeed the smallest integer such that the $\gcd(100,\overline{ab})$ isn't $1$ or I've messed up twice in the same problem. Number theory isn't taught in the schools of my country Greece, but it's my favourite math topic and I'm trying to get better at it alone, so thank you in advance.

Answer 1

We have $n=1000a + 100b+10c+d$ where $a,b,c,d$ are non-zero digits. We have $$10a+b,10b+c, 10c+d\mid n$$ One can re-write these requiremenets, $$\begin{align}10a+b&\mid 10c+d \tag1\label1 \\ 10b+c&\mid 1000a+d \tag2\label2 \\ 10c+d &\mid 1000a+100b\tag3\label3 \\ a,b,c,d &\in [1,9] \cap \mathbb Z \tag4\label4\end{align}$$ We have from $\eqref1$ that $10c+d=(10a+b)k$ for some positive integer $k$. We have from $\eqref3$ that $10c+d\mid 100(10a+b) \iff k\mid 100$. Since $10c+d<100$ and $10<10a+b$ we have $k <\frac{100}{10a+b} < 10$. Thus $k\in \{1,2,4,5\}$. Thus we divide into cases:

Case $1$: $k=1$; not allowed since then $\overline{ab}=\overline{cd}$; contradiction.

Case $2$: $k=5$. Thus $c=5a$ and $d=5b$. But because of constraint $\eqref4$ $(a,b,c,d)=(1,1,5,5)$. All that remains is to check whether $\eqref 2$ is satisfied here and indeed we have $15\mid 1005$. Further $\overline{ab}, \overline{bc}, \overline{cd}$ are all distinct. Thus we have a solution $n=1155$ here.

Case $3$: $k=2$; then $10c+d=2(10a+b)$. Then we have $c=2a$ and $d=2b$. Either $a=1$ or $a>1$. If $a>1$ the the solutions we find here are not minimal because then $\overline{abcd}>1155$. If $a=1$ then $c=2$. For finding a minimal solution (if possible) we must have $b\le 1$. So $b=1$ and $d=2$. So a possible solution could be $(a,b,c,d):(1,1,2,2)$. But here $\eqref 2$ is not satisfied. So no solution less than $1155$ is found here.

Case $4$: $k=4$; then $c=4a$ and $d=4b$; for a minimal $n$ we need, similar to the previous case, $a=1$ and $b=1$ which offers a possible $n=1144$ but one readily checks $\eqref 2$ is not satisfied here.

We conclude the minimal $$\boxed{n=\color{orange}{1155}}$$