perplexus.info :: Numbers : Strings of Nines

Strings of Nines (Posted on 2013-05-29)

The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization. Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.
Prove it.

No Solution Yet Submitted by Danish Ahmed Khan

No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)

Puzzle Solution

Comment 3 of 3 |

We know that:

Euler's Totient function phi(x) is defined as the number of numbers less than x and relatively prime to x.

Euler's Theorem states that:

If gcd(a,m) =1, then a^phi(m) =1(mod m)

Application of Euler's Theorem to the given puzzle

---------------------------------------------------------------------------------

Since gcd(10,n) =1, since n is NOT divisible by 2 or 5, and accordingly it follows that:

10^phi(n)=1 (mod n)

=> {10^phi(n) -1} is divisible by n.

By the very definition of it, phi(n) <=n

Consequently, the required result follows immediately.

Posted by K Sengupta on 2022-08-31 22:07:19

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info