Results 1 to 2 of 2

Math Help - order

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    order

    Hi,

    Find the order of 3 modulo 97.

    That is, find the smallest positve integer x such that 3^x = 1 mod 97.

    Using a calculator, I found the answer to be x = 48, but I want to know how to do this without a calculator.

    Let phi(n) be Euler's phi function.
    I know by Euler's Theorem that 3^(phi(97)) = 1 mod 97, and since 97 is prime, I know phi(97) = 96.

    48 = 96/2, but I don't see how to show that 48 is the order from this. Any help would be awesome. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,971
    Thanks
    1637
    Quote Originally Posted by jimmyjimmyjimmy View Post
    Hi,

    Find the order of 3 modulo 97.

    That is, find the smallest positve integer x such that 3^x = 1 mod 97.

    Using a calculator, I found the answer to be x = 48, but I want to know how to do this without a calculator.

    Let phi(n) be Euler's phi function.
    I know by Euler's Theorem that 3^(phi(97)) = 1 mod 97, and since 97 is prime, I know phi(97) = 96.

    48 = 96/2, but I don't see how to show that 48 is the order from this. Any help would be awesome. Thanks.
    Well, if 3^x= 1 (mod 97), then (3^x)^n= 1 (mod 97) for any n. That is, knowing that 3^{phi(97)}= 3^{96}= 1 (mod 97) tells you that the lowest power must be some divisor of 96. You would still have to show that 3^2 3^3, 3^4, 3^6, through all divisors of 96 less than 48 are NOT congurent to 1 mod 97.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Re-writing higher order spatial derivatives as lower order system
    Posted in the Differential Equations Forum
    Replies: 11
    Last Post: July 27th 2010, 08:56 AM
  2. Replies: 1
    Last Post: October 27th 2009, 04:03 AM
  3. Replies: 2
    Last Post: February 23rd 2009, 05:54 AM
  4. Replies: 2
    Last Post: November 25th 2008, 09:29 PM
  5. Replies: 1
    Last Post: May 11th 2007, 03:01 AM

Search Tags


/mathhelpforum @mathhelpforum