8
$\begingroup$

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?

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

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.