$2^{n!}\bmod n$ if $n$ is odd Given an odd number $n$, find $2^{n!}\bmod n$ and what if $n$ is even?
I am not getting how to deal with that $n!$ in the power of $2$.
Any help will be truly appreciated.....

Elaborating on @André Nicolas hint for odd $n$:


*

*By Euler's theorem, if $\gcd(a,n)=1$ then $a^{\phi(n)}\equiv1\pmod n$

*So the fact that $\gcd(2,n)=1$ implies that $2^{\phi(n)}\equiv1\pmod n$

*Since $\phi(n)<n$ by definition, $\phi(n)$ divides $n!$

*Therefore, $\exists{k\in\mathbb{N}}:2^{n!}=2^{\phi(n)\cdot k}=(2^{\phi(n)})^k$



From all the above, we can conclude that for odd $n$:
$$2^{n!}\equiv(\color\red{2^{\phi(n)}})^k\equiv\color\red{1}^k\equiv1\pmod{n}$$
