Repetition Mania- A problem based on Repunits

Number Theory Level 5

If f(N) be a function used to define a string of 1's repeated such that f(1)=1, f(2)=11, .... and so on..... find the smallest (N) such that, f(N) is divisible by 2011.

The answer is 670.

1 solution

Agnishom Chattopadhyay
May 14, 2014

Done this with python:

k = 1
while k%2011:
    k = 10*k + 1
print len(str(k))

This gives 670

@Shenal Kotuwewatta - Care to share, how you solved it?

Krishna Ar - 6 years, 10 months ago

@Sharky Kesa @David Vaccaro @Jon Haussmann - Any idea of a nt solution??

Krishna Ar - 6 years, 9 months ago

Note that $f(n) = \frac{10^n - 1}{9}.$ Thus, we want to find the smallest positive integer $n$ such that $10^n \equiv 1 \pmod{2011}$ . In number theory, this number is known as the order of 10 modulo 2011.

In general, for any relatively prime positive integers $a$ and $m$ , the order of $a$ modulo $m$ divides $\phi(m)$ . Thus, the order of 10 modulo 2011 must divide $\phi(2011) = 2010$ . We can then check $10^d \pmod{2011}$ for each divisor $d$ of 2010. The smallest divisor that returns 1 modulo 2011 is 670.

Jon Haussmann - 6 years, 9 months ago

Thank you so much Jon Haussman for this :D

Krishna Ar - 6 years, 7 months ago

Did the same!

Kartik Sharma - 6 years, 3 months ago

give a proper mathematical method and solution to the problem. The solution you posted is a way of finding the answer by trial and error. Not a method of solving it..

Ashwin Tare - 7 years ago

Repetition Mania- A problem based on Repunits

The answer is 670.

1 solution

0 pending reports