Compute $5^{10,000}\equiv \mod 52$ I'm unsure how to solve questions like these, we are given an example below but I'm still confused about how they got from $5^{100\times10+0}$ to $5^{0}$.
ie) Compute $5^{1000} \bmod 77$
$$
5^{1000}=5^{(166⋅6+4)}=5^4=25^2=4^2=16=2 \pmod 7\\
5^{1000}=5^{(100⋅10+0)}=5^0=1 \pmod{11}\\
5^{1000}=2⋅2⋅11+1⋅8⋅7=44+56=100=23 \pmod{77}
$$
 A: One uses the effective Chinese remainder theorem:  
Let $7u+11v=1$ a Bézout's relation between $7$ and $11$. Then $$(x\equiv a\mod 7  \;\text{ and }\; x\equiv b\mod 11)\iff (x\equiv 7bu+11av\mod 7\times11).$$
One ingredient is Lil' Fermat: as $7$ and $11$ are prime, $x^6\equiv1\mod 7$ for all $x\not \equiv 0\mod 7$ and  $x^{10}\equiv1\mod 11$ for all $x\not \equiv 0\mod 11$, hence $5^{10,000}\equiv 5^{10,000\bmod 6}\mod 7$ and $5^{10,000}\equiv 5^{10,000\bmod 10}\mod 11$.
This is the general method. However, in the present case, it is faster to observe that $$5^4=625\equiv 1\mod 52, \;\text{ hence }\; 5^{10,000}=(5^4)^{2500}\equiv 1^{2500}\mod 52.$$
A: What you have to understand from the examples is that if $n$ is relatively prime to $m$, then there exists a exponent $k$ such that $n^k\equiv1\mod m$.
One exponent that works every time is $m-1$, but there may be others (divisors of $m-1$). For example, $5^6\equiv1\mod 7$, so 
$$5{(166.6+4}\equiv {(5^6)}^{166}.5^4\equiv 1^{166}.5^4\equiv5^4\mod7$$
So now you have to find the first power of $5$ equivalent to $1$ modulo $52$, and use the same principle.
Hint : you should find $5^1000\equiv1\mod52$ ;-)
A: If you need $x^p\mod{n}$ and $\gcd(x,n)=1\Rightarrow\exists i\in\{1,2,\dots,n-1\}$ such that $x^i\equiv1\mod{n}$.
By Fermat's Little Theorem $x^{n-1}\equiv1\mod{n}$. Maybe there exists $i<n-1$ and $x^i\equiv1\mod{n}$.
Then $(x^i)^m\equiv1^m\mod{n}\Rightarrow (x^i)^m\equiv1\mod{n}$.  
Also $\exists q,r\in\mathbb{Z}:p=iq+r,~0\le r<i\Rightarrow x^p=x^{iq+r}=x^{iq}\cdot x^r=(x^i)^q\cdot x^r\Rightarrow x^p\equiv x^r\mod{n}$.  
If $\gcd(x,n)\ne1$ then $x^n\equiv x\mod{n}$ by Fermat's Little Theorem.
Also $\exists k_1,r_1\in\mathbb{Z}:p=k_1n+r_1,~0\le r_1<n\Rightarrow x^p=x^{k_1n+r_1}$.  
Let's do this:
(1) $x^{k_1n+r_1}=(x^n)^{k_1}\cdot x^{r_1}\Rightarrow x^{p}\equiv x^{k_1}\cdot x^{r_1}\equiv x^{k_1+r_1}\mod{n}$.
(2) If $k_1+r_1\ge n$ then go to (3) else go to (4).
(3) $\exists k_2,r_2\in\mathbb{Z}:k_1+r_1=k_2n+r_2,~0\le r_2<n$.
$~~~~~~~$Repeat step (1) but now with $k_2$ instead $k_1$ and $r_2$ instead $r_1$.
(4) We have $0\le k_i+r_i<n$ and $x^p\equiv x^{k_i+r_i}\mod{n}$, calculate $x^{k_i+r_i}$ should be "relatively" easy.  

For this case, we have to calculate $5^{10000}\mod{52}$.
$\gcd(5,52)=1\Rightarrow\exists i\in\{1,2,\dots,51\}:5^i\equiv1\mod{52}$.  
Let's take $i=51$ by Fermat's Little Theorem, then $5^{51}\equiv1\mod{52}$.
$10000=196\cdot51+4$
$5^{10000}=5^{196\cdot51+4}=\left(5^{51}\right)^{196}\cdot5^4\Rightarrow5^{10000}\equiv\left(5^{51}\right)^{196}\cdot5^4\equiv5^4\equiv625\equiv1\mod{52}$.
A: $\big[5^{\large 2} =\, -1+26\big]^{\large 2}\!\Rightarrow\,\color{#c00}{5^{\large 4}=\bf 1}+\color{#0a0}{52}k\,\Rightarrow\, 5^{\large 4N}\!\equiv (\color{#c00}{5^{\large 4}})^{\large N}\equiv \color{#c00}{\bf 1}^{\large N}\equiv 1\pmod{\color{#0a0}{52}}$
