There is a positive integer $N$. $N$ is made up of only two distinct digits- $2$ and $3$. $N+18$ is divisible by $37$. What is the minunum amount of times the number $2$ can appear in $N$? I'm pretty sure the answer is only one time. But how can I prove this?

  • $\begingroup$ are there any better tags I could use? $\endgroup$ – Joao Dec 3 '14 at 22:22
  • $\begingroup$ I'm afraid I don't share your optimism; the smallest count of twos I managed to come up was three. $\endgroup$ – Peter Košinár Dec 3 '14 at 22:33
  • $\begingroup$ @PeterKošinár but is it possible to prove that the smallest amount of two's is 3? $\endgroup$ – Joao Dec 3 '14 at 22:39
  • $\begingroup$ Note that $1000\equiv 1 \mod 37$ so you can reduce the problem to analysing the sum of digits (with some cases to check). $\endgroup$ – Mark Bennet Dec 3 '14 at 23:01
  • $\begingroup$ @MarkBennet Thanks. That should be an answer. $\endgroup$ – Joao Dec 3 '14 at 23:08

Let's start with a simple observation:

The number $37$ plays very nicely with powers of $10$... The value $10^m$ can only have three possible remainders modulo $37$: $1$, $10$ and $26$. If $N+18$ is divisible by $37$, $N$ must be congruent to $19$ modulo $37$. This observation will be quite useful in subsequent thoughts.

The number $N=2323323$ satisfies the given conditions and contains three twos. In order to show that we cannot satisfy the conditions given with fewer twos, we need to consider three cases:

  • Numbers consisting solely of digit $3$: An $m$-digit number of this form is equal to $$\frac{3}{9}(10^m-1)=\frac{1}{3}(10^m-1)$$ Using the observation mentioned above, we find that such numbers produce remainders $0$, $3$ and $33$ modulo $37$; none of which is equal to the desired $19$.
  • Numbers having exactly one occurrence of $2$: They can be obtained by the numbers in the preceding group by subtracting number of the form $10^k$ with $k\leq m$. The observation allows us to quickly conclude that the only remainders of such numbers modulo $37$ are $2$, $7$, $11$, $14$, $23$, $27$, $30$, $32$ and $36$.
  • Numbers having exactly two occurrences of $2$ are just as easy to deal with; there are just more remainders to cover... but still no $19$ among them.
  • $\begingroup$ How did you come up with $N=2323323$ or any N with three digits 2 to begin with? $\endgroup$ – Myath Dec 5 '14 at 21:37
  • $\begingroup$ Being lazy, I just ran a simple computer search :-) It can be done by hand quite easily too, though: Make a table consisting of four rows and $37$ columns (each column corresponding to one remainder modulo $37$). Mark cells $0$, $3$ and $33$ in the first row (those can be produced with no twos). Connect each marked cell in the first row with three cells in the second row; those $1$, $10$ and $26$ positions to the left of it (wrapping around from left to right if necessary). Do the same for third and fourth row. The path from cell $19$ in the last row tells you how to build your number. $\endgroup$ – Peter Košinár Dec 5 '14 at 21:52

Just another observation since I'm late to the party.

We can also use an algorithm for divisibility, which is to group the digits by threes from the right, and add them, repeating the process until we have a three digit number. If that's divisible by 37 then so is the original number.

If the number is of the form $33...333$, then the number $+18$ is $33...351$. The grouping sums form a pattern:

$$351, 354, 384, 684, 687, 717, 18, 21, 51, 351, ...$$

As none of these are divisible by $37$, there must be at least one $2$.

From there, it would remain to show that introducing one $2$, and then two $2$s, wouldn't produce any numbers divisible by $37$ either, and then it becomes a matter of searching.

You might be able to see that each $2$ rolls back the digit in the same place it lies in the group of three. Then, $687-21=666$, which is two $2$'s in the tens place, and one $2$ in the ones place.

Hence, not only does $3323322$ work, but also $2323323$ and $3322323$!


Let $k$ be the minimal possible number of $2$'s. Let $N$ be a minimal number of the given form with $k$ $2$'s. Since $333\cdot 10^n \equiv 0\pmod{ 37}$, $N$ does not contain three consecutive $3$'s. Thus only finitely many candidates need to be checked with less than three $2$'s. In fact, if $N$ has only $3$'s, then $N\equiv 0, 3,$ or $33\pmod{37}$. If there is one digit $2$ somewhere, then $1,10,$ or $26$ is subtracted depending on its position; and the same for a possible second $2$ occuring. We need to achieve $19\pmod{37}$. Obviously, zero $2$'s don't work. If we add $1,10,26$ to $19$, we get $$20,29,8 $$ which is a set disjoint from $\{0,3,33\}$. All sums of two nombers in $\{1,10,26\}$ plus $19$ are $$21, 30, 9, 2,18, 34.$$ again no match with $0,3,33$. We conclude $k>2$. From $3323322$ we learn that $k=3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.