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.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top