Thread: Natural divisors

Hi, I have recently encountered a problem I was unable to solve. I have tried everything and none of it worked.
Please help. The problem goes like this:


Prove that every natural odd number 'n' undividable by number 5, divides at least one of the numbers
1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, ....... etc.

Let u(n) be 11...1 (n times)
Let x be a natural odd number undividable by number 5. This implies x is relatively prime to any multiple of 10 because their divisors are only 5 and 2.
Using the Pigeonhole principle - Wikipedia, the free encyclopedia there is p and q such that the remainders of x/u(p) and x/u(q) are the same so x divide a number written 11...100..0 (1's followed by 0's)
x divide 11...1 * 10...0 and x is relatively prime to 10...0 so x must divide 11...1 using this lemma : If n|ab, and n is relatively prime to a, then n|b.

a little mistake in 2nd line : x is relatively prime to any power of 10 because their prime divisors are only 5 and 2.

Thank you very much. Last thing, could you please explain what 'relatively prime' means? I am a bit confused by that.

a is relatively prime to b if they have no common divisor, for exemple 17 and 30. and this is equivalent to saying they have no common prime divisor.

I see, thank you. =)

Originally Posted by Link

Using the Pigeonhole principle - Wikipedia, the free encyclopedia there is p and q such that the remainders of x/u(p) and x/u(q) are the same so x divide a number written 11...100..0 (1's followed by 0's)

Last thing, how do you prove this part?

Sorry i meant u(p)/x and u(q)/x. Suppose u(p)>u(q) we have :

u(p)=qx+r
u(q)=q'x+r
so u(p)-u(q)=(q-q')x. u(p)-u(q) is written 111...000... and x divide u(p)-u(q)