elementary number theory - Proving modular statements with variable exponents

I'm currently stuck on proving congruence of mod statements with variable exponents.

First problem is showing $2^{mn} \equiv 1 \mod (2^n + 1)$ for all even m.

What I have done so far is:

• There exists an $x$ such that $m = 2x$ for the parity definition.


• $2^{mn} = 2^{2xn} = 4^{xn}$

I am now lost on how to manipulate that to become $2^{mn} - 1 = (2^n + 1)z$ where $z$ is an integer.

Second problem is showing that $a^m \% p \equiv a^{m \% (p-1)} \% p$ where p is a prime number using Fermat's Little Theorem. I know FLT means $a^{p-1} \%p = 1$ but I don't really know how to deal with the $m \% (p-1)$ exponent.

Any helps and hints are greatly appreciated.

Answer

First:
$$2^{mn}=(2^n)^m\equiv(-1)^m\equiv1\pmod{2^n+1}\ .$$
Second: if $k\%(p-1)=r$ then $k=m(p-1)+r$ for some $m$, and then
$$a^k\%p=(a^{p-1})^ma^r\%p=1^ma^r\%p=a^r\%p=a^{k\%(p-1)}\%p\ .$$