Notepad/enter/Machine Tips (Quantum)/Resources/Concepts Review/Math/Proof of a formula for modulo.md

16^{54} \ mod \ 17=3^{24×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 1654mod17 to 324×54mod17, 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 \ \ \ \ (1)

Then the proof:

There must be one integer n to have

a \ mod \ p=a−np \ \ \  \  (2)

so

((a \ mod \ p)^b) \ mod \ p=((a−np)^b) \ mod \ p

With Binomial theorem - Wikipedia,

(a−np)b=ab+(b1)ab−1(−np)+(b2)ab−2(−np)2+...+(−np)b

We could see that all items are times of p except a^b,

((a−np)bmodp)=(ab+(b1)ab−1(−np)+(b2)ab−2(−np)2+...+(−np)b)modp=abmodp+0+0+...+0

Now we got

((a−np)^b \ mod \ p)=a^b \ mod \ p

Use formula (2)

((amodp)b)modp=abmodp

Now let a as 3^{24}, and b as 54 in formula (1):

 \\ 

\\begin{align}
 3^{24×54}\ mod \ 17=((3^{24})^{54}) \ mod \ 17 \\ \\&=  ((3^{24} \ mod \17)^{54})mod 17 


\end{align}
= 16^{54}mod17$$

via [BrookHongs github](https://brookhong.github.io/2018/05/22/proof-of-a-formula-for-modulo.html)