I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90
Here is author's work
In this problem, the author was trying to calculate $5^{40}$
He worked the powers of 5 by 2 until he go to the largest exponent that was less than 40, 32. He then reasoned that $5^{40}$ mod 7 = $5^{32}$ mod 7 * $5^ 8$ mod 7. Does anyone know where he got this property from? I know that there is an exponent property that would state $5^{40}$ = $5^{32}$ * $5 ^ 8$ (from
http://hotmath.com/hotmath_help/topics/properties-of-exponents.html ) but can someone show how to get from that one to the mod version property? I tried looking it up but couldn't find it.
Best Answer
The aspect you're puzzled by, $(5^{40} \bmod 7) \equiv (5^{32} \bmod 7)(5^{8} \bmod 7) \pmod 7$, is really the same process that has been used through the whole squaring process that preceded it, where (for example) we had $(5^{32} \bmod 7) \equiv (5^{16} \bmod 7)(5^{16}\bmod 7) \pmod 7$.
Essentially it is the same property that you are probably familiar with from modular arithmetic in general. For example, consider calculating $(20\times 15) \bmod 7 $. We can take the $\bmod 7$ value of each: $20 \equiv 6 \bmod 7$ and $15 \equiv 1 \bmod 7$ - and use those values to calculate the result $(6 \times 1) = 6 \equiv 6 \bmod 7$. And to show that is truly the $\bmod 7$ value of the original multiplication, we can drop back into the $20=7k+6$ type representation and prove out that all the multiples of $7$ can be ignored in the multiplication process. And if we want to in this case, we can even check that $300-6$ is indeed divisible by $7$.
So all we're looking at there is a standard property of modular arithmetic - the congruence classes multiply together consistently.
All numbers $n$ such that $n \equiv k \bmod m$ are in the same congruence class $\bmod m$ . For example, $\{2,9,16,23,30,37, \ldots\}$ are all in the same congruence class $\bmod 7$, identified by the non-negative member of the class less than than the modulo number - in that case, $2$. Still working modulo $7$, if we multiply any member of congruence class $2$ by any member of congruence class $4$, the answer will be in congruence class $1$.