The discussion centers around 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 scope includes mathematical reasoning and exploration of group theory concepts related to modular arithmetic.
There is no clear consensus on the proof approach, as participants propose different methods and express varying levels of certainty about their contributions. The discussion remains unresolved regarding the completion of the proof.
Some assumptions about the properties of odd natural numbers and the application of group theory are present, but not all steps in the reasoning are fully explored or validated.
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.