Find the least whole number only consisting of the digit 1 such that it is divisible by 3333...3.(100 3's)

Question

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333...3.(100 3's).

My approach: we see that 111 is divisible by 3. Hence 100 3's would divide 300 1's. Is my analogy correct?

Answer 1

Your intuition gives the right answer, but the answer is incomplete because an analogy does not give all of the details. Let's consider a more general problem:

When does $\underbrace{33\dots33}_{y-3s}$ divide $\underbrace{11\dots11}_{x-1s}$?

• We first observe that $\underbrace{33\dots33}_{y-3s}=3\times \underbrace{11\dots11}_{y-1s}$. Therefore, for the desired divisibility to hold, it must be that $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{x-1s}$. At this point, we know that $y\leq x$ since a larger positive number can't divide a smaller positive number.

• Now, consider $\underbrace{11\dots11}_{x-1s}-\underbrace{11\dots11}_{y-1s}=\underbrace{11\dots11}_{(x-y)-1s}\underbrace{00\dots00}_{y-0s}.$ We see that $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{x-1s}$ if and only if $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{(x-y)-1s}\underbrace{00\dots00}_{y-0s}$.

• We observe that $$ \underbrace{11\dots11}_{(x-y)-1s}\underbrace{00\dots00}_{y-0s}=\underbrace{11\dots11}_{(x-y)-1s}\times 10^{y}=\underbrace{11\dots11}_{(x-y)-1s}\times 5^y\times 2^y. $$ Since $\underbrace{11\dots11}_{y-1s}$ doesn't end in an even number or a $5$, the $2^y$ and $5^y$ are relatively prime to $\underbrace{11\dots11}_{y-1s}$. Therefore, $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{(x-y)-1s}\underbrace{00\dots00}_{y-0s}$ if and only if $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{(x-y)-1s}$.

• By continuing in this way (i.e., using induction), we see that we can keep subtracting $y$'s and $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{x-1s}$ if and only if $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{(x-ky)-1s}$ for any nonnegative integer $k$ which makes $x-ky$ nonnegative. If $x-ky$ is eventually $0$, then since every number divides $0$, we get that $\underbrace{11\dots11}_{y-1s}$ divides $\underbrace{11\dots11}_{x-1s}$. If $x-ky$ is never $0$, then, for $k$ sufficiently large, $y>x-ky>0$, so $\underbrace{11\dots11}_{y-1s}$ does not divide $\underbrace{11\dots11}_{(x-ky)-1s}$, as the second number is a smaller positive number.

• Therefore, we've learned that the only time that $\underbrace{33\dots33}_{y-3s}$ could possibly divide $\underbrace{11\dots11}_{x-1s}$ is when $x$ is a multiple of $y$. Now, let's assume that $y$ divides $x$ and consider $$\left(\underbrace{11\dots11}_{x-1s}\right)/\left(\underbrace{11\dots11}_{y-1s}\right).$$ This equals $$ \underbrace{1\underbrace{00\dots00}_{(y-1)-0s}1\underbrace{00\dots00}_{(y-1)-0s}\dots1\underbrace{00\dots00}_{(y-1)-0s}1\underbrace{00\dots00}_{(y-1)-0s}}_{(x/y)-1\text{ times}}1. $$ Now, we need to check divisibility by $3$ (for the $3$-factor in $\underbrace{33\dots33}_{y-3s}$). The number of $1$'s in this quotient is $\frac{x}{y}$. So, the sum of the digits of this number is $\frac{x}{y}$. To be divisible by $3$, this sum must be a multiple of $3$.

Putting this all together, the answer to our original question is that $x$ must be a multiple of $y$ and $\frac{x}{y}$ must be a multiple of $3$. In other words, $y=3mx$ for some positive integer $m$, which proves your guess was right.

Answer 2

Analogy is not proof. You are basing your claim on the fact that

1. $n$ threes will always divide $3n$ ones
2. There is no smaller number of threes that will divide $3n$ ones.

Neither of the two statements is proven.

Answer 3

$3n$ ones is $\dfrac{10^{3n}-1}9$, while $n$ threes is $\dfrac{10^{n}-1}3$.

We have

$$\frac39\frac{10^{3n}-1}{10^n-1}=\frac{10^{2n}+10^n+1}3,$$ which is indeed an integer number (because $10\bmod3=1$). This is somewhat "by chance", it wouldn't work with other digits.

And there is no guarantee that it is the smallest solution.

Answer 4

Here is a proper proof for three hundred $1$s.

First use the digit sum test for multiples of $3$ to verify that the number of $1$s is a multiple of $3$, else the number is not divisible by $3$ let alone $333...3$.

Next consider that the number must also be a multiple of $111...1$ with one hundred $1$s. If you try, let us say, $120$ $1$s for your dividend, the last $20$ of those $1$s will be a remainder, no good. To avoid that kind of outcome you need a dividend having a number of $1$s that's a multiple of $100$ to go with being a multiple of $3$ proven above.

Ergo $300$ $1$s is minimal.