Modular Arithmetic with Powers and Large Numbers

Question

I have a question similar to the following:

Evaluate $8767^{2123} \mod 15$.

So I got

$(8767^{11})^{193}$

$(8767^1*8767^{10})^{193}$

$(8767^1*(8767^3 *8767^4))^{193} \mod 15$

Now I haven't completed it but it doesnt feel I am going in the right direction can anyone help me out?

Answer 1

Hint :

Reduce 8767 mod 15 and 2123 mod $\phi(15)=8$

Answer 2

Note that : $$8767^{2123} \equiv 7^{2123} \mod 15$$

Since 7 and 15 are coprime, we exploit Euler's theorem (a generalization of FLT) as follows: $$\begin{align}7^{\phi(15)} &= 7^8 \\&\equiv 1 \mod 15\end{align}$$

Using the above result, we get : $$\begin{align}7^{2123} &= 7^{8\times265}7^3 \\&\equiv 7^3 \\&\equiv 13 \mod 15 \end{align}$$

It follows that : $$8767^{2123} \equiv 13 \mod 15$$

Answer 3

Hint $\rm\ mod\ 15\!:\ 8767\equiv 7\ $ and $\ \color{#c00}{7^4} \equiv (7^2)^2 \equiv 4^2\equiv \color{#c00}1\ $ so $\rm\ 8767^{\,4J+K}\!\equiv 7^{\,4J+K}\!\equiv (\color{#c00}{7^4})^J 7^K\!\equiv 7^K$

i.e. $\rm\ 8767\equiv 7\,\Rightarrow\,8767^{\large\,\color{#0a0}4}\equiv 7^{\large\color{#0a0}4}\equiv 1\, \Rightarrow\, 8767^{\,\large N}\! \equiv 7^{\large N}\equiv 7^{\large K}\ (mod\ 15)\ $ if $\rm\, K\,\equiv\, N\ \ (mod\ \color{#0a0}4).\,$ The arithmetic is simpler if one chooses the smallest such $\rm\,K > 0,\ $ namely $\rm\ \: K \,= (N\ \,mod\,\ \color{#0a0}4).$

The OP has $\rm\,N=2123\,$ so $\rm\, K \,= (2123\ \,mod\,\ \color{}4) = \color{orange}3\ $ $\Rightarrow$ $\rm\ 8767^{\large 2123}\equiv 7^{\large\color{orange}3}\equiv 13\pmod{15}$

Edit $\ $ Per request, below are very detailed explanations of the modular arithmetic calculations above. See here for a proof of the Congruence Power Rule (iterated application of Product rule).

$\begin{eqnarray}\rm mod\ 15\!:\ \ 7^4 &\equiv&\ (\color{#0a0}{7^{\large 2}})^{\large 2}\\ &\equiv&\ \ \, (\color{#c00}4)^{\,\large 2}\ \ \rm by\ \ \color{#0a0}{7^2}\! = 49\equiv \color{#c00}4,\ \ by\ \ 15\mid 49-4 = 45\\ &\equiv&\ \ \ \ \, \color{}1\quad\ \ \rm by\ \ \color{#c00}4^2\! = 16\equiv 1,\ \ by\ \ 15\mid 16-1 = 15\end{eqnarray}$

$\begin{eqnarray}\rm mod\ 15\!:\!\! &&\rm 8767^{\large\,4J+K}\quad but\ \ 8767\equiv 7\ \ by\ \ 15\mid 8767-7 = 8760 = 15\cdot 584,\ \ hence \\ &\equiv&\rm \quad\ \ 7^{\rm\large\,4J+K}\quad by\quad 8767\equiv 7\ \Rightarrow 8767^{\large N}\equiv 7^{\large N} \ \ by\ the\ Congruence\ Power\ Rule\\ &\equiv&\rm\ \ \ \ \ (\color{}{7^{\large 4}})^{\large J} 7^{\large K}\ \ \ by\ \ 7^{\,\large 4J+K} = 7^{\large 4J} 7^{\large K}\ \ and\ \ 7^{\large 4J} = (7^{\large 4})^{\large J} \ \ by\ \ Exponent\ Laws\\ &\equiv&\rm \qquad\ \, 1^{\large J} 7^{\large K}\,\ \ \, by\ \ 7^{\large 4}\equiv 1\ (prior\ paragraph)\ so\,\ 7^{\large 4J}\equiv 1^{\large J}\ by\ Congruence\ Power\ Rule\\ &\equiv&\rm\qquad\quad\,\ \ 7^K\ \ \ by\ \ 1^{\large J}\equiv 1\ \ by\ induction!\end{eqnarray}$

Remark $\ $ By little Fermat we know $\rm\,mod\ 5\!:\ 7^4\equiv 1\,$ and $\rm\,mod\ 3\!:\ \,7^2\equiv 1\,\Rightarrow\,7^4\equiv 1.\,$ Therefore we deduce $\,7^4\equiv 1\,$ mod $\,\rm lcm(3,5) = 15,\ $ i.e. $\rm\ 3,5\mid 7^4-1\,\Rightarrow\, 15=lcm(3,5)\mid 7^4-1.\,$ However, this method is a bit overkill for such a small problem. But it would be helpful for larger problems, where such divide-and-conquer order-computation can be aided using the Carmichael function).