Fed up of all those 1's

the easiest way to find the remainder is find the pattern.

$a_1$ mod 271 is 1,

$a_2$ mod 271 is 11,

$a_3$ mod 271 is 111,

$a_4$ mod 271 is 27,

$a_5$ mod 271 is 0,

$a_6$ mod 271 is 1,

$a_7$ mod 271 is 11,

$a_8$ mod 271 is 111,

$a_9$ mod 271 is 27,

$a_{10}$ mod 271 is 0

if you have a couple of eagle eyes, you will find that if n = 5, than $a_n$ mod 271 is 0, and $a_{n-1}$ is 271.

The question is what is $a_{214}$ mod 271. Since 214 = 215 - 1, and from the pattern above, we find that $a_{215}$ mod 271 is 0, and $a_{214}$ mod 271 is 27. Thus the answer is so.

If we divide 1111 by 271 the reminder is 27.

So when we divide 11111by 271 the reminder is 0

So it is clear that in every repeatation of 5 digits (1) the reminder obtained by dividing he no by 27 is 0.

The no. where 1is repeated 124 times when divided by 271 ,the digit till 120th place is divided by 271 such that no reminder is obtained . When last four digits are divided by 271 the reminder obtained is 27.

So ,27 is the reminder.

Another way to solve it is without using the "1111" pattern.

Notice, that $1111111...1=10^0+10^1+10^2+10^3+...+10^{123}$ .

Find another pattern in the different powers of 10:

$10^1\equiv 10 \pmod{271}$

$10^2\equiv 100 \pmod{271}$

$10^3\equiv 187 \pmod{271}$

$10^4\equiv 244 \pmod{271}$

$10^5\equiv 1 \pmod{271}$

$10^6\equiv 10 \pmod{271}$

The pattern repeats after every 5 powers. Thus, there are $120 / 5 = 24$ cycles. Now, simplify the expression above:

$1111111...1 \pmod{271}$

$\equiv10^0+10^1+10^2+10^3+...+10^{123} \pmod{271}$

$\equiv10^0+24\times(10+100+187+244+1)+10^{121}+10^{122}+10^{123} \pmod{271}$

$\equiv1+24\times(271)+10+100+187 \pmod{271}$

$\equiv24\times(0)+298 \pmod{271}$

$\equiv27 \pmod{271}$

So, even if you didn't see the pattern with 1s, you can solve the problem anyway.

Notice that numbers having any multiple of 5 1's are divisible by 271 So we can write

$\underbrace{111\ldots11}_{\text{124 1's}} \pmod{271} = \underbrace{111\ldots11}_{\text{120 1's}} \times 10000 + 1111$

$\underbrace{111\ldots11}_{\text{120 1's}}$ is divisible by 271

So,

$\underbrace{111\ldots11}_{\text{120 1's}} \times 10000 + 1111 \equiv 0 + 1111 \pmod{271} \equiv \boxed{27}$

First, I tried to find an integer $x$ such that $271x$ has the one at the digit place. Now for this to have a one at the digit place, $x$ must have a one at the digit place as well. By trial and error, $271\times41 = 11111$

Observe that $124 \equiv 4 \quad (mod \quad5)$ , all-in-all we need to compute $1111 \quad(mod \quad 271) = \boxed{27}$

For simplicity, let $n=124$ . We use the geometric sum to simplify our number $\begin{aligned} x&:=\sum_{k=0}^{n-1}10^k=\frac{10^n-1}{10-1}=9^{-1}\left(10^n-1\right) \end{aligned}$

We define $r_k:=10^k \mod 271$ . With a small table we find $r_5=10^5\equiv 1\mod 271$ . Via Euclid's Extended Algorithm we obtain $9^{-1}\equiv -30\mod 271$ and get $\begin{aligned} x & \equiv (-30)\cdot (r_n-1) \equiv (-30)\cdot \left(1^{24}\cdot r_4-1\right) =840\equiv \boxed{27}\mod 271 &&&&& \left|\quad\begin{array}{r|rrrrrr} k & 0 & 1 & 2 & 3 & 4 & 5 & \cdots\\\hline r_k & 1 & 10 & 100 & -84 & -27 & 1 & \cdots \end{array}\right. \end{aligned}$

I had a lot of fun with trying to figure this out, here is what I thought to do:

---

Let's find such value of 11...1 that mod (271) would be congruent to 0.

It is 11111 (five 1).

Now we can subtract LHS from the original number and take modulus of that, then add it back. Surely, we subtract 5 ones and 119 zeros to get 0 from mod (271).

Since adding 0 doesn't actually do anything, we can do that for 23 more times (or just arrive at conclusion that 124 - 120 = 4 ones) to get a number 1111 in mod (271) and that is congruent to 27!

---

An article that explains this very well: http://www.devx.com/tips/Tip/39012 (you will have to ignore the fact that it's originally written for programming).

firstly rewrite $a_{n}$ as 1+10+100+1000.....271 times use GP formula next use binomial expansion