# 77-digit number divisible by 7 with seven 7s

The smallest number divisible by 7 with seven 7s is trivially 7777777.

Then, what is the greatest 77-digit number divisible by 7 which contains seven 7s?

• Exactly seven 7s, or at least seven 7s? Sep 30 '20 at 5:21
• quite ironic this puzzle has seven upvotes (at the time of writing) ;-) Sep 30 '20 at 20:57
• @Randal'Thor No matter. Oct 2 '20 at 4:53

Starting with the factoid that

111111 (3 * 7 * 11 * 13 * 37)

is divisible by seven, we can tell that

999999 is too, so if we have any number that's divisible by 7, we can put six nines in front of it and still get a number that's divisible by seven.

So, we can focus on

finding the largest number with 11 digits that's divisible by seven, and has 7 sevens: we can later prepend 66 nines to it.

Being greedy, we should first try the biggest possible such number,

99,997,777,777.

To check its divisibility, we can use the divisibility rules for 7:

we can combine two consecutive sets of 3 digits by subtracting one from the other (this is equivalent to subtracting multiples of 1001, which is divisible by seven), and once we have reached 3 digits, we can subtract twice the last digit from the number formed by the first two.

Both of those operations result in a number that's divisible by seven if and only if they were performed on a number that was divisible by seven. So we get

99,997,777,777 -> 99,997,000,000 -> 99,997 -> 997-99 = 898 -> 89-16 = 73.

Sadly, not a multiple of seven. The next biggest is

99,987,777,777

No luck there, either. The next two are

99,979,777,777 and 99,978,777,777

but alas, no. Moving along in a similar manner, we have to try a couple more until we hit

99,977,787,777 (7 times 14282541111)

which gives the final solution of

69 nines followed by 77787777

It is

$$999...99977787777$$

We can find this by hand using le p'tit Fermat:
$$10^{77} = 10^{13\times 6 - 1} = 10^{-1} = 5 \mod 7$$
$$10^{8} = 2 \mod 7$$
Taking the difference and replacing $$0$$s with $$7$$s:
$$999...99977777777 = 3 \mod 7$$
We need to check increments $$2\times 10^7,10^7,2\times 10^6,10^6,2\times 10^5,...$$ yielding $$6,3,2,1,3,5,1,4,... \mod 7$$. So the largest usable increment is $$10^4$$.

• I've taken the liberty to change to a more maimstream notation for "modulo". And while at it I also got rid of "I think", your argument is as good as anyone could ask. Sep 30 '20 at 20:59
• Thanks @PaulPanzer. That is reassuring. Sep 30 '20 at 21:24

Brute force solution in Ruby code:

n = 10**77
until (start % 7).zero? && (start.to_s.count('7') == 7) do
n -= 1
end
n
#=> 99999999999999999999999999999999999999999999999999999999999999999999977787777

I believe it's:

Sixty-nine 9s followed by 74777777

• Why not put the 4 at the end? And maybe then add 203? Sep 30 '20 at 5:48
• Oh, yeah. I wasn't thinking clearly. Sep 30 '20 at 6:00