Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 4 of 4
  1. MHB Craftsman
    Alexmahone's Avatar
    Status
    Offline
    Join Date
    Jan 2012
    Posts
    264
    Thanks
    125 times
    Thanked
    72 times
    #1
    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.

  2. MHB Journeyman
    MHB Math Scholar
    caffeinemachine's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    India
    Posts
    779
    Thanks
    564 times
    Thanked
    1,102 time
    Thank/Post
    1.415
    Awards
    MHB Topology and Advanced Geometry Award (2016)
    #2
    Quote Originally Posted by Alexmahone View Post
    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?

  3. MHB Craftsman
    MHB Math Helper

    Status
    Offline
    Join Date
    Jan 2013
    Posts
    227
    Thanks
    20 times
    Thanked
    339 times
    Thank/Post
    1.493
    Awards
    Graduate POTW Award (Jul-Dec 2013)
    #3
    Since you have posted questions on groups, you might be interested in the following link: . 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.

  4. MHB Journeyman
    MHB Math Scholar
    caffeinemachine's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    India
    Posts
    779
    Thanks
    564 times
    Thanked
    1,102 time
    Thank/Post
    1.415
    Awards
    MHB Topology and Advanced Geometry Award (2016)
    #4
    Quote Originally Posted by johng View Post
    Since you have posted questions on groups, you might be interested in the following link: . 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.

Similar Threads

  1. Modulos with regards to Congruence
    By shamieh in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: March 26th, 2015, 03:55
  2. How do we get the congruence?
    By evinda in forum Number Theory
    Replies: 0
    Last Post: November 2nd, 2014, 14:10
  3. Why do we solve this congruence?
    By evinda in forum Number Theory
    Replies: 21
    Last Post: October 4th, 2014, 06:39
  4. Why do we have to solve this linear congruence?
    By evinda in forum Number Theory
    Replies: 4
    Last Post: May 10th, 2014, 13:04
  5. [SOLVED] Congruence equation
    By Poirot in forum Number Theory
    Replies: 1
    Last Post: May 2nd, 2013, 10:10

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards