# Natural divisors

• Dec 3rd 2012, 09:18 AM
Randompn
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.
• Dec 3rd 2012, 09:35 AM
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.
• Dec 3rd 2012, 10:05 AM
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.
• Dec 3rd 2012, 10:14 AM
Randompn
Re: Natural divisors
Thank you very much. Last thing, could you please explain what 'relatively prime' means? I am a bit confused by that.
• Dec 3rd 2012, 10:27 AM
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.
• Dec 3rd 2012, 10:33 AM
Randompn
Re: Natural divisors
I see, thank you. =)
• Dec 9th 2012, 09:15 AM
Randompn
Re: Natural divisors
Quote: