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

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.

• So check numbers like 18999999 and 19899999 and 19989999 and so on. – Gerry Myerson Nov 20 '18 at 8:15
• You get divisibility by $9$ for free so you only need be concerned about checking for $7$ – Mark Bennet Nov 20 '18 at 8:44

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.

• Is that the smallest such number? [no criticism of your answer intended... but OP originally asked for smallest.] (+1 on answer.) – coffeemath Nov 20 '18 at 9:01
• Sorry @coffeemath , I had a typo. – Akash Roy Nov 20 '18 at 10:18
• Yes, it's the smallest. And I explained why. There can't be one with 7 digits, so the smallest has eight or more. This has 8 so it is in the smallest group. the smallest digit it can begin with is 1 so this is the smallest of the smallest. If number starts with 1 and has 8 digits and adds to $63$ then is must have 6 nines and one 8. So smallest number would be $19,999,999 - 10^k$ where $10^k\equiv 5 \mod 7$. The only such option for $0\le k \le 7$ is $k=5$. So this is the only solution with 8 digits begining with $1$. And no smaller number is a solution. – fleablood Nov 20 '18 at 17:05

(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.

• @coffeemath: Sorry for the typo. Thank you for reporting it. – Christian Blatter Nov 20 '18 at 10:15

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$$.

• The modular argument is not hard. The numbers are all of the form $19,999,999 - 10^k$ so we need $19,999,999 - 10^k \equiv 0 \mod 7$ or $10^k \equiv 5 \mod 7$. As $10$ and $7$ is relativley prime and $7$ is prime the $10^k; 0\le k < 7$ are distinct modulo $7$ and $10^5$ is the only one that works. – fleablood Nov 20 '18 at 17:28
• @fleablood, are you saying, more generally, that if $10$ and $p$ are relatively prime (with $p$ a prime), then $10^k$ for $0\le k\lt p$ are distinct modulo $p$? It's true that $10$ is a primitive root mod $7$, but not because it's relatively prime to $7$. – Barry Cipra Nov 20 '18 at 22:46
• Yeah, I guess I worded it incorrectly. $10\equiv 3$ is a primitive root is what I meant. – fleablood Nov 20 '18 at 23:08

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.

• Instead of the mysterious sum_digits(i) you could write python code: sum(int(d) for d in str(i)) – Paul Evans Nov 20 '18 at 16:01
• You can also save time by starting at 9999990 and incrementing by 63, eliminating the need to test i%63==0. – Kyle Kanos Nov 20 '18 at 19:47
• Yes! That's more optimized. Thanx for advice. – FightWithCode Nov 21 '18 at 13:20