Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.

Question

TASK: Find the smallest positive integer divisible by 63 such that the sum of its digits is also divisible by 63.

MY WORK: Let the number be $A=\overline{x_n x_{n-1} x_{n-2} \cdots x_1 x_0}$. Since $63|(x_n+x_{n-1}+\cdots+x_1+x_0)$, we have that $x_n+x_{n-1}+\cdots+x_0\ge63\cdots(*)$ and since $x_0,x_1,\cdots,x_n$ are n+1 digits, we have that $x_n+x_{n-1}+\cdots+x_0\le9+9+\cdots+9=9(n+1)$ which then means that $9(n+1)\ge63\Leftrightarrow n+1\ge7$ i.e that the number $A$ has at least seven digits. If it has $7$ digits, all of them would have to be $9$ to satisfy the inequality $(*)$ which would mean that $A=9999999$. But then the condition $63|A$ would not be satisfied. So the number A doesn't have seven digits - it has at least eight digits.

However, I do not know where to go from here.

Answer 1

Assume the the number is $1$ with 6 $9$s and one $8$.

Now $19999999\equiv 5\pmod 7$

If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^k\equiv 5\mod 7$.

$10\equiv 3$

$100\equiv 30\equiv 2$

$1000\equiv 20\equiv 6$

$10,000\equiv 60\equiv 4$

$100,000 \equiv 40\equiv 5$

So $19,999,999-100,000=19,899,999\equiv 0\pmod 7$.

And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.

====

I thought I made it clear why this is the smallest.

No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0\le k \le 7$. For such a number to be divisible by $63$ we must have $10^k \equiv 5 \pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.

Answer 2

(This is essentially the same solution as @fleablood 's; but doubts were raised whether it is actually the smallest.)

Such a number has at least $8$ digits. Since the prescribed digit sum is $63$ we have to deduct exactly $9$ units from writing eight nines. Trying with $x_1=1$ as first digit, and all other nines, we have given away $8$ units, one more to go. Divisibility by $9$ is taken care of automatically. Now $19\,999\,999=5$ mod $7$; therefore we need to find a $k\in[0..6]$ with $10^k=5$ mod $7$, or we are bust with $x_1=1$. Fortunately $10^5=5$ mod $7$. It follows that $19\,899\,999$ is the smallest number with the required properties.

Answer 3

I also verify that the Number 19,899,999 is the smallest number that is divisible by 63 and Also its sum is divisible by 63. Here a program I wrote in Python 3. To find this out by brute forcing :

for i in range(9999990, 19900000, 63):
     sum_is = sum(int(d) for d in str(i))
     if sum_is%63==0:
             print(i)

Prints : 
19899999

Also this time I started from 9999990 because this number the last number divisible by 63 that has sum less than 63.

This can also be used to do the same with any number.

Just change the range and 63 as you want.

Hope this Helps!

[EDIT SUMMARY] For more Optimization and better Understanding. Added direct summing instead of sum_digits as request/suggested by @Paul Evans. Also added jump of 63 as Suggested by @Kyle Kanos.

Answer 4

The smallest number whose digits all sum to a multiple of $63$ is $9{,}999{,}999$. The next smallest is $18{,}999{,}999$, then $19{,}899{,}999$, then $19,989{,}999$, and so on. All of these are clearly divisible by $9$, so it suffices to check for divisibility by $7$. As it happens, the first two are not, but $19{,}899{,}999/7=2{,}842{,}857$ (and, just to doublecheck, $19{,}899{,}999/63=315{,}873$).

Remark: It's not a priori obvious that any of the numbers described here will turn out to be divisible by $7$. You could say we just got lucky. Or you could do a modular argument to show that luck had nothing to do with it. One thing is obvious: the smallest number sought for is certainly no greater than $777{,}777{,}777$.