$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.....
 A: For the first question, note that $\varphi(n)$ divides $n!$, and use Euler's Theorem.
The $n$ even problem is more interesting. Let $n=2^km$ where $m$ is odd. Then by the result for odd moduli, we have $2^{n!}\equiv 1\pmod{m}$. Also, $2^{n!}\equiv 0\pmod{2^k}$. Now use the Chinese Remainder Theorem.
Added: In more detail, we want to find a $t$ such that $1+tm$ is divisible by $2^k$. So we are looking at the congruence $tm\equiv -1\pmod{2^k}$. This can be solved in the usual way, by multiplying both sides by the inverse of $m$ modulo $2^k$.
A: 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}$$
