# Finding the remainder of $7^{27}\mod 11$

I just finished reading about Euler's Totient theorem, Fermat's little theorem, and the Chinese Remainder theorem, so I decided to test what I learned with a small problem that I came up with for myself. The question was to find the remainder of $$7^{27}$$ when divided by $$11$$. Here is how I started:

$$7^{27}=7^{11}\cdot 7^{11}\cdot 7^5\equiv 7\cdot 7\cdot 7^5\mod 11\equiv 5\cdot 7^5\mod 11 \tag{via Flt}$$

Here is where I ran into some problems. I noticed that $$7^{31}\equiv 5\mod 11$$ via Euler's Totient theorem and that $$7^5\equiv 2\mod 5$$ via Flt, but I had to deduce that $$7^7\equiv 10\mod 11$$ via the following method, which I am pretty sure is correct using the fact that $$ab\mod n=(a\mod n) \cdot (b\mod n)$$ :

\begin{align*} 5\cdot 7^5\mod 11&\equiv(5\pmod {11})\cdot (7^2\pmod {11})^2\cdot(7\pmod{11})\\&\equiv (5\pmod{11})^3\cdot(7\pmod{11})\\&\equiv (125\pmod{11})\cdot(7\pmod {11})\\&\equiv (4\pmod {11})\cdot(7\pmod{11})\\&\equiv (28\pmod {11})\\&\equiv 6\pmod{11} \end{align*}

• For small exponents we usually do not need to use FLT or Euler. But be careful that $7^{11}\equiv 7\pmod {11}$. Commented Sep 9, 2020 at 8:52
• Note $7^3 \equiv 2 \mod 11$. Therefore $7^5 \equiv 98 \mod 11 \equiv -1 \mod 11$.
– Tapi
Commented Sep 9, 2020 at 8:52
• @player3236 Thanks Commented Sep 9, 2020 at 8:53
• Another one: from $7^3\equiv2$, we get $(7^3)^3\equiv8\equiv-3$ and $((7^3)^3)^3\equiv -27\equiv6$. Commented Sep 9, 2020 at 17:26

Fermat's Little Theorem implies $$7^{11} \equiv 7 \pmod{11}$$, which was your mistake (before you edited the question). Since $$7$$ is not divisible by $$11$$, $$7^{10} \equiv 1 \pmod{11}$$. Observe that $$7^2 \equiv 49 \equiv 5 \pmod{11} \implies 7^3 \equiv 7 \cdot 5 \equiv 35 \equiv 2 \pmod{11}$$ Hence, \begin{align*} 7^{27} & \equiv (7^{10})^2 \cdot 7^7 \pmod{11}\\ & \equiv 7^7 \pmod{11}\\ & \equiv (7^3)^2 \cdot 7 \pmod{11}\\ & \equiv 28 \pmod{11}\\ & \equiv 6 \pmod{11} \end{align*}

• Thanks. I should have added the edits below the original question. Sorry Commented Sep 9, 2020 at 9:20

Something is wrong with your computation.

$$7^{27} \equiv (-4)^{27} = -2^{54} = -(2^{10})^5\cdot 16 \equiv - 1^5 \cdot 5 = - 5 \equiv 6 \pmod{11}$$.

but $$7^{5} \equiv - 2^{10} \equiv -1\equiv 10 \pmod{11}$$

so the error was in the very first reduction.

Note that you applied Fermat's Little Theorem incorrectly. $$7^{11} \equiv 7 \pmod {11}$$ but you seemed to equate it to $$1$$.

• Yes, I just noticed that something was off as well. I edited it in the question. I got $\psi(11)$ mixed up with $11$.Thank you. Commented Sep 9, 2020 at 9:12

You have an initial error in your computation: $$7^{11}\equiv \color{red} 7\mod 11$$.

Actually, what is coorect is that $$7^{\varphi(11)}=7^{10}=1$$, and it is easy to check the order of $$7\bmod 11$$ in indeed $$10$$ (a priori, we can only say it is one of its divisors). Therefore $$7^{27}\equiv 7^{7}\mod 11\equiv (-4)^7.$$ Now, you can use the Fast exponentiation algorithm: $$\begin{array}{crr} n & x^{2^k} & P \\ \hline 7 & -4 & -4 \\ 3 & (-4)^2\equiv 5 &-4\cdot 5\equiv 2 \\ 1 & 5^2\equiv 3 & 2\cdot 3=\color{red}6 \end{array}$$

• the exponent is wrong in $7^{11}$ but thanks. i’ll have to go and read about fast exponentiation algorithm as well Commented Sep 9, 2020 at 9:31
• @CSquared: Sorry for the typo. I'll fix it instantly. Commented Sep 9, 2020 at 9:44

You can 'peel off' one $$7$$ factor at a time and perform the mod calculation in your head,
$$\quad 5 \cdot 7^5 \equiv 2 \cdot 7^4 \equiv 3 \cdot 7^3 \equiv (-1) \cdot 7^2 \equiv 4 \cdot 7 \equiv 6 \pmod{11}$$