Let $n=2^k$ where $k\ge 3$. Let $a$ be any odd natural number. Prove that $a^{n/4}\equiv 1\pmod{n}$. My attempt: $\phi(n)=n/2$ So, by Euler's formula, $a^{n/2}\equiv 1\pmod{n}$. I don't know how to proceed.
Follow Math Help Forum on Facebook and Google+
Originally Posted by alexmahone Let $n=2^k$ where $k\ge 3$. Let $a$ be any odd natural number. Prove that $a^{n/4}\equiv 1\pmod{n}$. My attempt: $\phi(n)=n/2$ So, by Euler's formula, $a^{n/2}\equiv 1\pmod{n}$. I don't know how to proceed. if $a \equiv 1 \pmod{n}$ what is $a^2 \pmod{n}$ ?
$\displaystyle a^{2^{k-1}}-1=\left(a^{2^{k-2}}-1\right)\left(a^{2^{k-2}}+1\right)$ use induction on $\displaystyle k$
Originally Posted by Idea $\displaystyle a^{2^{k-1}}-1=\left(a^{2^{k-2}}-1\right)\left(a^{2^{k-2}}+1\right)$ use induction on $\displaystyle k$ Thanks!