I am trying to understand modular exponentiation and its implementation in C from here
On my way of understanding it I came across the following equation: $$(x^{n/2}\bmod M)^2\equiv(x^2\bmod M)^{n/2}$$ I am not able to understand how are we arriving from LHS to RHS.
On
Going back to the site https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/
The refer to the "remainder" operation where $a \% M=k$ is the unique remainder between $0$ (inclusive) and $M$ (exclusive) where $a = k + mM$ for some unique integer $M$.
In that case the above is not true. Example: $(2^7 \% 5)^2 = (128\% 5)^2 = 3^2 = 9$ and $(2^2\% 5)^7 = 4^7 = 16384$. They are not equal.
What is the case is that $(2^7 \% 5)^2\% 5 = 9\% 5=4$ and $(2^2\% 5)^7\% 5 = 16384 \% 5=4$ and they are equal.
The expression $a \mod M$ means something slightly different. It refers to a set of numbers that all have the same remainder when divided by $M$. $7 \mod 5$ isn't $2$. $7$ is equivalent to $2$ when you are condsdering remainders by $5$.
$7 \mod 5 \ne 2$. Instead $7\mod 5 = \{......, -8,-3, 2, 7, 13,.....\}$ and $7 \mod 5 \equiv 2$-- Note the three bars in the equivalence (NOT equal) sign-- means $7 \in \{....., -8,-3, 2,7,12, ....\}$.
Or in other words $7\mod 5 \equiv 2$ means "$7$ is equivalent to $2$ in the sense that they both have the same remainder when divided by $5$.
In that light
$2^7 \mod 5 \equiv 3$ and $2^2\mod 5\equiv 4$ and it is true thatn $3^2\mod 5\equiv 4^7 \mod 5\equiv 4 \mod 5$.
It is not true. Take $n=2$, $M=5$, $x=2$. Then $x^{n/2}=x$, your equality now would be $$ (2\mod 5)^2=(4\mod 5)^2, $$ which is not true (the left-hand-side is $4$, while the right -hand-side is $1$).