## A challenging 11111… puzzle

I received this email from Mr. Brian Silverman who gave me permission to publish it.

I noticed that you were asking for interesting factoids about the number 11.

This isn't quite a factoid about 11 but here's a math puzzle a Russian friend of mine said her son worked out with 7th graders. Seems to me to be beyond most undergrads here. I'm not including the answer, to give you a chance to work on it if you want. but will send it if you ask.

"The question is if it's true that among the numbers consisting of only "1"s (1; 11; 111; 1,111; etc.) there is a number (maybe many) that is divisible by 572,003?

Actually, 572003 is taken arbitrarily. 57 is the number of the school (schools here are mostly numbered instead of having names) and 2003 you possibly know what is recently used for (yes, yes, here in Moscow, too). "

Brian

This puzzle doesn't seem at all obvious to me, especially if one needs to solve it for arbitrary numbers other than 572003. I thought of putting it into my pile of problems to someday solve but then thought it'd be fun to post here.

Can Russian 7th graders solve this? How much help did they get?

Can you solve it?

Raj ShahOctober 24th, 2011 - 09:26

If I interpret the question correctly, I have to find a number that when multiplied by 572003 gives a product that is all ‘1’s, correct?

If I construct that number starting in the ones column, it’s clear the ones digit must be 7, since 7×3=21 which is the only way to get a ‘1’ in the ones column of the product.

2

5 7 2 0 0 3

x Y 7

_________

Z 1

This forces a 2 carried into the tens column (see above). Now, there is no digit I can place in the tens column (Y) to multiply by zero and add two that will give a one at (Z).

Therefore, I believe there solution is that is it NOT possible for a number consisting of all ‘1’s to be divisible by 572003.

Raj ShahOctober 24th, 2011 - 09:28

Looks like my formatting above didn’t work :-(. Hopefully, the explanation stands on it’s own. Basically, I tried to construct a factor that along with 572003 could create a results of all ‘1’s starting in the “ones column”

Alastair IrvingOctober 24th, 2011 - 09:45

I found this fairly easy, but I am doing a PhD in number theory so I have much more experience than a Russian 7th grader. My solution is below:

———–

The number consisting of n 1s is given by (10^n-1)/9. We want to know if there is an n such that this is divisible by q. so we want to solve

10^n-1 = 0 mod 9q

10^n = 1 mod 9q

If 10 and 9q are coprime (which is equivalent to 10 and q being coprime), then Euler’s theorem tells us that phi(9q) is a solution of this. If they are not coprime then there can be no solution.

In the case given 572003 is coprime with 10 and phi(9*572003)=3392928 so the number with 3392928 1s is divisible by 572003.

The problem actually only asks whether an n exists you don’t need to find it. Therefore phi(n) isn’t necesary, its sufficient to say that if (10,q)=1 then the sequence of powers of 10 mod 9q never goes to 0 and must repeat itself so that there are k,l with 10^k=10^l mod 9q and thus 10^(l-k)=1 mod 9q.

I hope this all makes sense

Alastair

FelixCQOctober 24th, 2011 - 09:59

I don’t know about Russian 7th graders, but here is a solution that should work for numbers that are coprime with 9 and 10, as is the case for 572003:

Let n be coprime with 9 and 10. By Fermat’s little theorem, 10^(n-1)=1(mod n), meaning that n divides 10^(n-1)-1, which is the digit 9 repeated (n-1) times. Since n is coprime with 9, it must divide (10^(n-1)-1)/9, which is the number 1 repeated (n-1) times…

Of course, by Euler theorem, the number that has the digit 1 repeated phi(n) times will work as well (phi(n) being the totient of n), which in the case of 572003 is equal to 565488.

For other numbers, if they are even they cannot divide an odd number, if they are a multiple of 5, they cannot end with a 1. So any number that is not coprime with 10 cannot have a multiple that has all its digits equal to 1.

More generally, for a number that is coprime with 10 but divisible by 9, I am not sure whether there is a solution or not. I know there is one for 9 (111111111), but I don’t know for 27…

Patrick HonnerOctober 24th, 2011 - 10:25

Another way to solve this is to think of the decimal expansion of 1/572003.

Since 572003 is not divisible by 2 or 5, its decimal expansion repeats. Let’s call that string of repeating digits ‘A’. We can convert this to a fraction of the form A / 999…9, where the number of 9s in the denominator is equal to the number of digits in A.

So 1/572003 = A / 999…9. Cross-multiplying yields 572003 * A = 999..9. So 572003 must divide 999…9. But 999…9 = 9*111…1, and since 572003 and 9 are coprime, it must be the case that 572003 divides 111….1.

Brian SilvermanOctober 24th, 2011 - 10:49

(it was me who originally sent this to Sol…)

Impressively quick results.

As it turns out 572003 happens to not be divisible by 9. That wasn’t a requirement of the original Russian answer. It was just a coincidence. For their answer any odd number not divisible by 5 would do.

GertOctober 24th, 2011 - 11:05

Adding to Alastair:

The smallest number consisting of 1s divisible by 572003 is the number consisting of 47124 1s.

I too found the problem to be easy, but that was probably because I immediately spotted that it could be solved by using the pigeonhole priniple.

I solved it in the same way as Alastair wrote in the last paragraph, i.e., by showing the existence of a solution without bothering to find any of them.

The solution can of course be written in terms that a 7th grader can more readily understand – and I have seen 7th graders solve similar problems (e.g., “write 12,3456456456… as a fraction”) – though I am probably to dense below:

Let’s first see what happens for smaller numbers where we are actually able to compute the solutions.

A first observation is that a number of 1s is never divisible by 2 or 5.

For 3 we get:

1/3=0 with remainder 1

11/3=3 with remainder 2

111/3=37

1111/3=370 with remainder 1

11111/3=3703 with remainder 2

111111/3=37037

For 7 we get:

1/7=0 with remainder 1

11/7=1 with remainder 4

111/7=15 with remainder 6

1111/7=158 with remainder 5

11111/7=1587 with remainder 2

111111/7=15873

1111111/7=158730 with remainder 1

11111111/7=1587301 with remainder 4

111111111/7=15873015 with remainder 6

1111111111/7=158730158 with remainder 5

11111111111/7=1587301587 with remainder 2

111111111111/7=15873015873

The remainders seem to repeating. This can be shown to be the case generally, since there is only a finite number of possible remainders and the same procedure is repeatedly applied (adding one 1 is the procedure “multiply by 10, then add 1″).

The difference between two numbers consisting only of 1s is 10^n times a number of 1s. If the two numbers have the same remainder when divided by 572003, then the difference divided by 10^n is divisible by 572003.

Adding to Raj:

He made an error in his argument (as 37*572003=21164111), but his idea can still be used to give a proof.

Iteratively one can construct n-digit numbers x_n such that 572003*x_n ends in n 1s. Let x_1=7. Assume that the (n+1)th digit of 572003*x_n reading from the right is a. Then x_(n+1)=x_n+b10^(n+1), where a+3*b ends with 1. It is always possible to find such a b since looking at the last digits in the 3-column of the multiplication table, we get 3,6,9,2,5,8,1,4,7,0, which is just a reordering of 1,2,3,4,5,6,7,8,9,0 this interesting property of the multiplication table also holds for the 1, 7 and 9 columns, enabling one to extend the argument here not just to 572003 but to any number ending in 1,3,7 or 9).

It remains to show that this iteration at some stage gives a number consisting only of 1s. One could of course continue until one finds x_47124*572003. A less time consuming argument is found by applying the pigeon-hole principle to the first seven digits of the product 572003*x_n.

EvanOctober 24th, 2011 - 13:35

well each number is of the form:

the sum from i to n of 10^i. and this must divide 572003. Then, assume the summation does in fact divide 572003. Then, at least 1 number (other than 1 itself) must divide 572003 up to 1111111 (n = 6). testing each of these n’s mod 10^n should reveal at least one number that ends up being 0 mod 10^n. when that is the case the number divides it.

EvanOctober 24th, 2011 - 13:36

i forgot to mention that in this case, only 1 divides 572003 so you then the contradiction leads us to the conclusion that no number with only 1’s in their digits divides 572003, besides 1 itself.

Søren Furbo SkovOctober 25th, 2011 - 04:56

This question was on the Danish Georg Mohr competition in the late 90’ies. The Georg Mohr competition is the one they use to select the Danish participant to the math olympics. Anyway, their solution (I participated but didn’t solve it) doesn’t require any group theory:

Look at the 572004 first numbers containing only one. Two of these must have the same reminder when divided by 572003. The difference between these two numbers must be divisible with 572003, and be of the form 111….1100….000 = 1111….1111*100…0000. 572003 is coprime with 10000…0000, so 111….1111 must be divisible with 572003.

Alexander BogomolnyOctober 26th, 2011 - 07:09

You are talking of repunits and to answer the question want to use the Pigeonhole principle: http://bit.ly/s7n48E

Robert WarnerNovember 9th, 2011 - 03:31

One thing i noticed was that the question doesn’t say it has to divide evenly so with that in mind, any number consisting of and n amount of 1s is divisible by 572003, you will just get a number that isn’t whole. Or am I over simplifying it?

John PilgeNovember 11th, 2011 - 19:08

Thinking back to 7th grade, I suspect the answer by Raj Shah is likely the one the student was thinking about. You can force a 1 result by finding a number the makes the units place end in “1.”

In the following example I have forced a repeat of 8 ones by choosing each number in the multiplier that would cause a 1 in the result by adding the products.

572003

20649037

______

4004021

1716009

0

5148027

2288012

3432018

0

1144006

———————–

11,811,311,111,111

In theory, you keep this up until there is no need to add any more numbers.

Since the sum of the product columns must equal 1, 11, 21,… the next number

to put into the multiplier would be a 6 since you need to covert the 3 (carry 1) to a 21 (carry 2) making the multiplier 620649037 and the result having nine ones (355,013,111,111,111).