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}$ ?
use induction on
Originally Posted by Idea use induction on Thanks!