Too many 5's?

when checking for divisibility of n sequences of digits divisible by a prime number we can the sequence as a nth power of 10

$555555....(\text{n terms}) ... 5 = 5 \times 111111 ....(\text{n terms}) ... 1 = \frac{5 \times 9 \times 111111 ....(\text{n terms}) ... 1}{9} = \frac{5 \times 999999 ....(\text{n terms}) ... 9}{9}$ $\Rightarrow \frac{5 \times 999999 ....(\text{n terms}) ... 9}{9} = \frac{5 \times (10^n - 1) }{9}$

So if $2003 | 555555....(\text{n terms}) ... 5 \Rightarrow 2003 |10^n - 1$

\Rightarrow 10^n (\mod 2003) \equiv 1 \tag{1}

The following is quoted from Wikipedia article on Euler's theorem Now, Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group Let $10^n = a$ and $a \equiv 1(\mod 2003)$ then a is one of the residual classes, and its powers

a, a^2, .... a^k \equiv 1 (\mod n)\tag{2}

are a subgroup.

Now per Lagrange's theorem, $k | \mathrm{\varphi}(n)$ .

So, k \in {1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002} \tag{3}

The only number that has a power relationship with 2002 is 1001 so the smallest number that divides 2003 is 1001

I'll let someone else post the Number Theory solution.

In the meantime, we can quickly solve with code. It is good to be efficient by only keeping track of the remainders for $n=1,2,3,\ldots$ 5's, rather than actually creating the entire $n$ digit number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

x = 5
n = 1
success = False

while success == False:
    n += 1
    x = (10*x + 5) % 2003
    if x == 0:
        print n
        success = True

returns 1001.

The answer must be a divisor of $\phi(2003) = 2002 = 2\cdot 7\cdot 11\cdot 13$ . That leaves in principle 16 possibilities: $1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002$ .

We need the smallest of these values $n$ for which $10^n \equiv 1$ mod 2003.

I calculated the powers of 10, using $10^{m+n} = 10^m\cdot 10^n\ \text{mod}\ 2003$ : $\begin{array}{cccc} 10^4 \equiv -15 & 10^7 \equiv -979 & 10^{11} \equiv 664 & 10^{13} \equiv 301 \\ 10^8 \equiv 225 & 10^{14} \equiv -996 & 10^{22} \equiv 236 & 10^{26} \equiv 466 \\ 10^{16} \equiv 550 & & & \\ 10^{32} \equiv 47 & 10^{77} \equiv -87 & 10^{143} \equiv 485 & 10^{91} \equiv 523 \\ 10^{64} \equiv 206 & 10^{154} \equiv -443 & 10^{286} \equiv 874 & 10^{182} \equiv -882 \\ 10^{128} \equiv 373 & & & \\ 10^{256} \equiv 922 & & 10^{1001} \equiv 1 & \\ 10^{512} \equiv 812 & & & \end{array}$

(For instance, I calculated $10^{1001}$ as $10^{512}\cdot 10^{256}\cdot 10^{128}\cdot 10^{64}\cdot 10^{32}\cdot 10^8\cdot 10^1$ .)

From $10^{1001} \equiv 1$ mod 2003 it follows that $111\cdots 1$ (1001 digits) is a multiple of 2003, and therefore so is $555\cdots 5$ .

Do the division 1/2003. Period of repeating decimal digits is 1001. This is the required answer. How does it work?

1/n has a property that its period of terminating digits will be equal to k iff n | (999... k times) for smallest k.

Since 5 and 9 are coprime, we will get k for (5555... k times) also.