The discussion focuses on proving the congruence relation \( a^{n/4} \equiv 1 \pmod{n} \) for \( n = 2^k \) where \( k \ge 3 \) and \( a \) is any odd natural number. The initial approach utilizes Euler's theorem, noting that \( \phi(n) = n/2 \) leads to \( a^{n/2} \equiv 1 \pmod{n} \). Induction is suggested as a method for proof, starting with \( k = 3 \) and extending to \( k > 3 \) by establishing \( a^{n/8} \equiv 1 \pmod{n/2} \). The structure of the multiplicative group \( Z_n^* \) is also referenced as a key concept in understanding the problem.
PREREQUISITESMathematicians, students studying number theory, and anyone interested in modular arithmetic and group theory concepts.
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?Alexmahone said: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.
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.johng said: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.