Find the remainder when $\overbrace{11\ldots1}^{124 \text{ times}}$ is divided by 271 .

Question

We have to find the remainder when $\overbrace{11\ldots1}^{124 \text{ times}}$ is divided by 271 .

In this I thought of using chinese remainder theorem or congruency/modular arithmetic .

But I could not get any good start .

I found a similar question .

What will be the remainder when 111...(123 times) is divided by 271?

Finding the remainder of $\overbrace{11\ldots1}^{123 \text{ times}}$ divided by $271$

But in that I could not understand how they got the idea that of 271x41

Answer 1

The number in question is $a=(10^{124}-1)/9$.

We find $10^3\equiv187$, $10^4\equiv244$, $10^5\equiv 1\pmod{271}$. Therefore $10^{124}\equiv 244\pmod{271}$. So $9a\equiv 243\pmod{271}$. I'll leave solving this congruence to you...

Answer 2

Since $11\,111=271\times41$, and since $111\,111=11\,111\times10+1$, $111\,111\equiv1\pmod{271}$. So $\overbrace{111\,111}^{6n\text{ times}}\equiv1\pmod{271}$. Since $124=6\times20+4$, $\overbrace{111\,111}^{124}\equiv1\,111\pmod{271}$, and $1\,111\equiv27\pmod{271}$.