Thrill Of JEE Algebra

It can be proved by the Pigeon Hole principle that some repunit is divisible by each odd integer which is not a multiple of $5$ .

If the odd integer not divisible by 5 is $n$ , consider the first n repunits, namely, $R_1=1, R_2=11, R_3=111, .... , R_n=11...1111$ ( $n$ times).

If one of these repunits leave a remainder $0$ when divided by $n$ , we are done.

Else, let us assume that none of these repunits leave a remainder of $0$ when divided by $n$ . So they can leave $n-1$ possible remainders leaving out $0$ , that is $\{1, 2, \cdots, n-1\}$ . But there are $n$ remainders here, so by Pigeon Hole principle, two of the repunits must leave the same remainder when divided by n. So there exists $1\le i, j\le n$ such that $R_i=R_j(modn)$ .

So $n|(R_i-R_j)$ .

Let us assume without loss of generality that $i>j$ .

Then we have $R_i-R_j=R_{i-j}.10^{i-j-1}$ .

So we have that,

$n|R_{i-j}.10^{i-j-1}$ ,

but gcd $(n,2)=1$ as n is odd, and $gcd(n,5)=1$ as n is not divisible by 5, so $gcd(n,2*5)=1$ as \2) are $5$ both primes. So $gcd(n,10)=1$ .

So, $n|R_{i-j}$ , as it does not divide $10^{i-j-1}$ , since $gcd(n,10)=1$ .