mathschallenge.net

Problem

A number consisting entirely of ones is called a repunit. We shall define $R(k)$ to be a repunit of length $k$; for example, $R(6) = 111111$.

Given that $n$ is a positive integer and $GCD(n, 10) = 1$, prove that there always exists a value, $k$, for which $R(k)$ is divisible by $n$.

Solution

Consider $R(k) \mod n$ for $1 \le k \le n$.

Under modulo $n$ the residues can be $0, 1, 2, ... , n - 1$; that is, there are up to $n$ different possible remainders when $R(k)$ is divided by $n$.

If each residue is different then one of them must be zero, in which case there exists a value of $k$ such that $n|R(k)$ and the proof is complete.

However, if they are not all different, there must be at least two residues that are equal (by the Pigeon Hole Principle). Suppose that $R(i) = R(j)$, where $i \gt j$, then it should be clear that $R(i) - R(j) \equiv 0 \mod n$.

Now consider $R(7) - R(4) = 1111111 - 1111 = 1110000$.

$\therefore R(i) - R(j) = 10^j R(i - j) \equiv 0 \mod n$

In other words, $10^j R(i - j)$ is a multiple of $n$, and as $GCD(n, 10) = 1$, it must be $R(i - j)$ that is a multiple of $n$.

But as $1 \le j \lt i \le n$, it follows that $i - j \lt n$, and so there must exist a value of $k = i - j$ such that $n | R(k)$. Q.E.D.