# Modular Arithmetic with Powers and Large Numbers

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?

• Do you know Fermat's so-called little theorem and Euler's generalisation of that? Jan 9, 2014 at 15:16

Hint :

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

• Yes I forgot I could use the totient function thanks for your help I select this as the answer as soon as I'm allowed to do so Jan 9, 2014 at 15:24
• @user1552404, Using this(mathworld.wolfram.com/CarmichaelFunction.html), $\lambda(15)=4$ Jan 9, 2014 at 18:04

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

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

• I really respect your intellect Bill but it is hard for me to understand what is going on here from my current understanding of this kind of mathematics. I think this may have something to do with the ≡ symbol and how it allows you to go from something like (74)^J*7^K≡7K or 4^2 ≡ 1 Jan 9, 2014 at 15:44
• @user1552404 To master elementary number theory, it is essential that you learn to do modular arithmetic as fluidly as you do normal integer arithmetic. Let's see if we can figure out where the stumbling block is above, since it is very basic modular arithmetic. If you can tell me precisely which congruence(s) you do not follow, then I can explain them in much greater detail. Jan 9, 2014 at 15:51
• Okay after re-reading I understand it a lot better I didn't realise you were mod 15ing (for lack a better term) across the board as I was taught to do them somewhat differently. And also I see now that ((7^4)^J = 1. Would I be right in saying that if I put 2123 in for k into 7^k I would get my answer to this question? It is the answer part I find confusing as I'm not sure were you solved my problem or did you just derive a general formula for solving it for any value K? Jan 9, 2014 at 16:17
• @user1552404 Ok, I explained it in more detail. The proof above shows that if $\rm\,N\equiv K\pmod 4\,$ then $\rm \,8767^N\equiv 8767^K\pmod{15}.\,$ So you can choose any such $\rm\,K\,$ that you desire. The one that results in the implest arithmetic is the least one $\rm \,K:= (N\ mod\ 4).\,$ Jan 9, 2014 at 17:05
• Seriously Bill thank you so much thats really cleared it up for me! Jan 9, 2014 at 17:35