1. ## Natural divisors

Hi, I have recently encountered a problem I was unable to solve. I have tried everything and none of it worked.

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.

2. ## Re: Natural divisors

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.

3. ## Re: Natural divisors

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

4. ## Re: Natural divisors

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

5. ## Re: Natural divisors

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.

6. ## Re: Natural divisors

I see, thank you. =)