# Remainder on division with $22$

What is the remainder obtained when $$14^{16}$$ is divided with $$22$$?

Is there a general method for this, without using number theory? I wish to solve this question using binomial theorem only - maybe expressing the numerator as a summation in which most terms are divisible by $$22$$, except the remainder?

How should I proceed?

• $14^{16} = (22 - 8)^{16}$ – ab123 Jul 3 '18 at 10:37
• $8^{16} = 64^8 = (66 - 2)^8$ – ab123 Jul 3 '18 at 10:41
• @ab123 Why not make an answer of that? – Arthur Jul 3 '18 at 10:41

You can use binomial expansions and see that $$14^{16} = (22 - 8)^{16}$$ implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$ Proceeding similarly,

$8^{16} = 64^8 = (66 - 2)^8 \implies 2^8 = 256 \text{ divided by } 22 \implies \text{remainder = 14}$

Since $$14^2 \equiv -2$$ so $$14^{16} \equiv (-2)^8 \equiv 16^2\equiv (-6)^2 \equiv 14$$

or

$$14^2 = 22k -2$$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22\cdot 11+14$$

A method that uses FLT.

Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7\cdot14^{15}$ by $11$.

By FLT, $14^{10}\equiv1\pmod{11}$ so $$7\cdot14^{15}\equiv7\cdot14^5\equiv98\cdot196\cdot196\equiv-1\cdot(-2)\cdot(-2)\equiv-4\equiv7\pmod{11}$$ hence the required remainder is $7\times 2=14$.

Using the Euclidean Algorithm

Note that \begin{align} 14^{16}&\equiv0&\pmod2\tag1 \end{align} Reducing mod $11$ and using Fermat's Little Theorem, we get \begin{align} 14^{16} &\equiv3^6&\pmod{11}\\ &\equiv3&\pmod{11}\tag2 \end{align} Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer, $$\begin{array}{r} &&5&2\\\hline 1&0&1&-2\\ 0&1&-5&11\\ 11&2&1&0\\ \end{array}\tag3$$ we have $$11(1)+2(-5)=1\tag4$$ from which we get \begin{align} -10&\equiv0&\pmod2\\ -10&\equiv1&\pmod{11} \end{align}\tag5 Multiplying $(5)$ by $3$ gives \begin{align} -30&\equiv0&\pmod2\\ -30&\equiv3&\pmod{11} \end{align}\tag6

Using the Chinese Remainder Theorem

The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be \begin{align} 14&\equiv0&\pmod2\\ 14&\equiv3&\pmod{11} \end{align}\tag7 Thus, $(1)$, $(2)$, and $(7)$ yields \begin{align} 14^{16}&\equiv14&\pmod{22}\tag8 \end{align}