To find a remainder, when divided by $101$

Question

There is a large number given in an exam. It is said to find a remainder when it is divided by $101$. The number is $$1+11^{{(1+11+11^2+11^3+...+11^{100}~~)}^{(11^{101}~~+11^{102}~~+\cdots+11^{1000}~~)}}$$

We know $11$ and $101$ are itself prime then $(101,11)=1$ and $\phi(101)=100$

Now, $$1+11+11^2+11^3+....+11^{100}\equiv r\mod 100 \\ \Rightarrow1+11+21+21*11+21^2+21^2*11+.....+(21^2)^{50}\equiv r \mod 100 \\ \Rightarrow (1+11+21+31+41+51+61+71+81-9)*10 \equiv r\mod 100 \\ \Rightarrow 0\equiv r\mod 100 \\ \therefore 0^{{(11^{101}+11^{102}+.....+11^{1000}~~)}}\equiv0 \mod 100 \\ \therefore 1+11^0\equiv1+1\equiv2 \mod 101$$

Is it correct? Any help is appreciated.

Answer 1

You can use the geometric series formula $\displaystyle \frac{a(1-r^n)}{1-r}$, where $a$ is the first term, and $r$ is the common ratio.

For $1+11+\cdots+11^{100}$ this is $1 \cdot {{1-11^{100}} \over {1-11}}$. By Fermat's little theorem, $11^{101-1} \equiv 1 \pmod {101}$, so the whole expression is congruent to $1 \pmod {101}$.

For $11^{101}+11^{102}+\cdots+11^{1000}$ this is $11^{101} \cdot {{1-11^{1000}} \over {1-11}}$. Since $11^{101-1} \equiv 1 \pmod {101}$, then $11^{1000} \equiv (11^{100})^{10}$ $ \equiv 1 \pmod {101}$, so ${{1-11^{1000}} \over {1-11}}$ evaluates to $1 \pmod {101}$.

Therefore, the problem is simplified to $1+11^{1^1} \pmod {101}$, which is congruent to $12 \pmod {101}$.

Answer 2

Let's show $1+11+11^2+11^3+....+11^{100} \equiv 1 \mod 100$.

Easy to see that $11^{101}-1$ is divisible by $10$.
Not trivial, but not that hard to work that $11^{10} \equiv 1 \mod 100$.

With above two results we have
$$10(1+11+11^2+11^3+....+11^{100}) = 11^{101}-1 \equiv 11-1 \equiv 10 \mod 100$$

This yields $$1+11+11^2+11^3+....+11^{100} \equiv 1 \mod 100$$

---

$$1+11^{{(1+11+11^2+11^3+...+11^{100})}^{(11^{101}+11^{102}+.....+11^{1000})}} \\ \equiv 1 + 11^{1\mod 100} \\ \equiv 1 + 11 \\ \equiv 12 \mod 101$$