MHB Prove congruence for powers of 2

  • Thread starter Thread starter alexmahone
  • Start date Start date
AI Thread Summary
The discussion focuses on proving that for any odd natural number \( a \) and \( n = 2^k \) where \( k \ge 3 \), the congruence \( a^{n/4} \equiv 1 \pmod{n} \) holds. Initial attempts reference Euler's theorem, noting that \( \phi(n) = n/2 \) leads to \( a^{n/2} \equiv 1 \pmod{n} \). Induction on \( k \) is suggested, starting with \( k=3 \) and extending to \( k>3 \) by showing \( a^{n/8} \equiv 1 \pmod{n/2} \). Further insights into the structure of the multiplicative group of integers modulo \( n \) are provided, emphasizing the relevance of group theory in the proof. The discussion highlights the importance of understanding group structures to complete the proof effectively.
alexmahone
Messages
303
Reaction score
0
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.
 
Mathematics news on Phys.org
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.
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?
 
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.
 
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.
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.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top