# Proof of a formula for modulo

\[16^{54} \mod 17 = 3^{24 \times 54} \mod 17\]Why?

Public Key Cryptography: Diffie-Hellman Key Exchange (short version) - YouTube is a good video to understand asymmetric cryptography. There is a jump from 4:34 in the video that is not obvious to everyone.

The jump is from \(16^{54} \mod 17\) to \(3^{24 \times 54} \mod 17\), but why? From the comments of video, I’m not the only one who is supprised by this jump.

First let me introduce a formula:

\[a^b \mod p = ((a \mod p) ^ b) \mod p \tag{1}\]Then the proof:

There must be one integer `n`

to have

so

\[((a \mod p) ^ b) \mod p = ((a-np)^b) \mod p\]With Binomial theorem - Wikipedia,

\[(a-np)^b = a^b + {b\choose 1}a^{b-1}(-np) + {b\choose 2}a^{b-2}(-np)^2 + ... + (-np)^b\]We could see that all items are times of `p`

except \(a^b\),

Now we got

\[((a-np)^b \mod p) = a^b \mod p\]Use formula (2)

\[((a \mod p) ^ b) \mod p = a^b \mod p\]Now let a as \(3^{24}\), and b as 54 in formula (1):

\[\begin{align} 3^{24 \times 54} \mod 17 & = ((3^{24})^{54}) \mod 17 \\ & = ((3^{24} \mod 17)^{54}) \mod 17 \\ & = 16^{54} \mod 17 \end{align}\]