Results 1 to 2 of 2

Math Help - number of incongruent sols of x^n [congruent to] 1 (mod p)

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    number of incongruent sols of x^n [congruent to] 1 (mod p)

    If p is a prime number and b is a primitive root modulo p, and n is a positive integer:


    first I had to express the general solution of the congruence eqt. x^n [congruent to] 1 (mod p) in terms of b

    ...

    I found the solutions are:
    x= b^i for 1 <= i <= n such that (p-1)/gcd (p-1,i) | n


    now I need to find how many incongruent solutions modulo p this congruence equation has...this one seems much tougher, and any help/hint would be appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    If p is a prime number and b is a primitive root modulo p, and n is a positive integer:


    first I had to express the general solution of the congruence eqt. x^n [congruent to] 1 (mod p) in terms of b

    ...

    I found the solutions are:
    x= b^i for 1 <= i <= n such that (p-1)/gcd (p-1,i) | n


    now I need to find how many incongruent solutions modulo p this congruence equation has...this one seems much tougher, and any help/hint would be appreciated
    If x is a solution to this congruence then x \equiv b^y (\bmod p) for some y\in \mathbb{Z}. Therefore, b^{ny}\equiv 1(\bmod p)\implies ny \equiv 0(\bmod p-1). The number of incongruent solutions to this congruence (which will leads to incongruence solutions to the original equation) is (n,p-1).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. incongruent solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2010, 07:27 PM
  2. Replies: 1
    Last Post: December 2nd 2009, 08:36 PM
  3. number of incongruent primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 11:02 AM
  4. incongruent integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 11:00 AM
  5. 2^n is incongruent to 1 (mod n)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 13th 2007, 03:11 PM

Search Tags


/mathhelpforum @mathhelpforum