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

Question

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*}$$

Is there a faster way of going about this? Thanks.

Answer 1

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*}

Answer 2

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$.

Answer 3

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}

Answer 4

The OP asked

Is there a faster way of going about this? Thanks

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}$