Prove: $2^{n-1}\equiv 1\pmod {n},n=2701$ Prove: $2^{n-1}\equiv 1\pmod {n},n=2701$
$n=2701=37\cdot 73$
By Fermat's little theorem:
$$2^{37-1}\equiv 1\pmod {37}$$
$$2^{73-1}\equiv 1\pmod {73}$$
How to combine these relations to get the statement?

Use the fast exponentiation algorithm modulo 73:
$$\begin{array}{rlclr}
n&a&&P& \\
\hline
36&a&2&1&1\\18&a^2&4&1&1\\
9&a^4&16&a^4&16\\
4&a^8&257\equiv 37&a^4&16\\
2&a^{16}&37^2\equiv 55&a^4&16\\1&a^{32}&55^2\equiv32&a^{36}&16\cdot32\equiv\color{red}{1}\\
\hline
\end{array}$$
Thus $2^{36}\equiv 1\mod 37$ and $\mod73$, and by the Chinese remainder theorem:
$$\mathbf Z/37\mathbf Z\times\mathbf Z/73\mathbf Z\simeq\mathbf Z /2701\mathbf Z, $$
$2$ has order $36$ modulo $2701$, so that $\;2^{2700}\equiv2^{2700\bmod 36}\equiv 2^0=1\mod 2701.$
