Given the numerical succession 5, 55, 555, 5555, 55555... Are there numbers that are multiples of 495? If so, determine the lowest.

Question

I get the solution (555555555555555555) by using prime factorization. But I was wondering if there is a solution using modular arithmetic.

Answer 1

$495=5\cdot 9\cdot 11$

Every member of the sequence is divisible by $5$.

Only members of the sequence with some multiple of $9$ digits are divisible by $9$ (from the usual divisibility test of $9$).

Only members of the sequence with an even number of digits are divisible by $11$ (from the divisibility test for $11$, that the two alternating digit sums must differ by some multiple of $11$).

Therefore all members of the sequence with some multiple of $18$ digits are divisible by $495$

Answer 2

Here's a general solution with modular arithmetic that happens to solve this problem anyway, though using divisibility tests is faster.

Writing $555\dots5$ as $\frac59 (10^n-1)$, we want to know when $\frac{5}{9}(10^n-1) \equiv 0 \pmod{495}$, or when $10^n-1 \equiv 0 \pmod{891}$.

Since $891 = 81 \cdot 11$, by the Chinese remainder theorem, we have a solution when we satisfy both of:$$\begin{cases}10^n \equiv 1 \pmod{81}, \\ 10^n \equiv 1 \pmod{11}.\end{cases}$$

For the first equation, we can write $10 = 9+1$, and therefore $$10^n = (1+9)^n = 1 + \binom{n}{1}9 + \binom{n}{2}81 + \cdots.$$ Taking $10^n \bmod{81}$ leaves only $1 + 9n$ to worry about. So $10^n \equiv 1 + 9n \pmod{81}$, which is $1$ if and only if $9 \mid n$.

(This is taking a shortcut. The long way around, we know that $10^{72} \equiv 1 \pmod{81}$, because $\phi(81) = 72$. But this might not be the minimal solution, so we'd have to consider $10^d$ where $d$ is a divisor of $72$ to see which of these are $1\pmod{81}$.)

The second equation is easy. $10^n \equiv (-1)^n \pmod{11}$, so this is equal to $1$ if and only if $n$ is even.

For both of these to be true, we want $n$ to be a multiple of $18$, which unsurprisingly gives the same answer as straightforward divisibility tests.

Answer 3

We have $\frac{555..5}{495} = \frac{111..11}{99} = \frac{111..11}{9\cdot 11}$(with $n$ digits in the numerator). A number is divisible by 9 if and only if the sum of its digits is divisible by 9, therefore for $111...11$ to be divisible by $99$, $1 + 1 + 1 + ... + 1 + 1 = n\cdot 1 = n$ has to be divisible by 9. For a number to be divisible by 11, the sum of the digits with alternating signs: $1 - 1 + 1 - ... \pm 1 \equiv n \pmod{2}$ has to be divisible by 11, so $n$ has to be even. This leaves us with $111...11$ being divisible by $99$, and therefore $555...55$ being divisible by $495$ if and only if $n$ is divisible by $18$, which makes $n=18$ the lowest amount of digits.

Answer 4

As others have said, $495 = 5 \cdot 9 \cdot 11$. We can leverage this fact very nicely.

All multiples of 9 have digits that add up to a multiple of 9, so we can deduce that the number of 5s in the answer has to be a multiple of 9.

$11$ is a multiple of 11, and $1111$, or $11 \cdot 100 + 11$ is also a multiple of 11. You can keep going and conclude that every even number of ones can be a multiple of 11 (e.g. $11, 1111, 111111, ...$). If every even number of ones is a multiple of 11, an odd number of ones is $10 \cdot \text{an even number of ones} + 1$, which is $1 \text{ mod } 11$ and not divisible by 11.

Therefore, our number must have an even number of 5's which is also divisible by 9. The smallest number of 5's which satisfies this is 18, so the answer is $555555555555555555$.

I knew the fact about the even number of ones beforehand, as well as the nine divisibility rule, so this was easy to solve after those. Things like that are good to know in math competitions.