Prove congruence for powers of 2

[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.

 

[caffeinemachine]

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.

Let's use induction on $k$. For $k=3$ one can show by computation. For $k>3$, we have by induction that $a^{n/8}\equiv 1\pmod{n/2}$. Thus $a^{n/8}=nm/2+1$. This gives $a^{n/4}= 1+ nm + n^2m/4$. Can you finish?

 

[johng1]

Since you have posted questions on groups, you might be interested in the following link: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n. Here, it is stated that for $n=2^k$, the structure of $Z_n^\ast$ is the direct product of the cyclic group of order 2 and the cyclic group of order $2^{k-2}$; it also states that 3 has order $2^{n-2}$ You might try and prove these things for your self or look in practically any book on groups.

 

[caffeinemachine]

Since you have posted questions on groups, you might be interested in the following link: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n. Here, it is stated that for $n=2^k$, the structure of $Z_n^\ast$ is the direct product of the cyclic group of order 2 and the cyclic group of order $2^{k-2}$; it also states that 3 has order $2^{n-2}$ You might try and prove these things for your self or look in practically any book on groups.

This is probably the best way to do it and explains why we have "$n/4$" in the problem. As always, johng is awesome, especially at group theory.