# Thread: Prove congruence for powers of 2

1. ## Prove congruence for powers of 2

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.

2. ## Re: Prove congruence for powers of 2

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}$ ?

3. ## Re: Prove congruence for powers of 2

$a^{2^{k-1}}-1=\left(a^{2^{k-2}}-1\right)\left(a^{2^{k-2}}+1\right)$

use induction on $k$

4. ## Re: Prove congruence for powers of 2

Originally Posted by Idea
$a^{2^{k-1}}-1=\left(a^{2^{k-2}}-1\right)\left(a^{2^{k-2}}+1\right)$

use induction on $k$
Thanks!