Congruence Solving

  1. Let p be a prime number and d / p-1 .

    Then which of the following statements about the congruence?
    x ^d = 1( mod p) is / are correct :
    1. It does not have a solution
    2 atmost d incongurent solutions
    3 exactly d incongruent solutions
    4 aleast d incongruent solutions.
  2. jcsd
  3. micromass

    micromass 20,039
    Staff Emeritus
    Science Advisor
    Education Advisor

    Hi Bhatia! :smile:

    What do you think? And why?

    (maybe try to work it out for a concrete example of p and d? Like p=11 and d=5?)
  4. Thanks for your reply :smile:

    Going by your idea

    Let p= 5, then since d / p-1 then I guess we have d= 1, 2, 4...then solving x^ d = 1 (mod 5)

    for d=1, x=1
    for d=2, x= 4, 6,9,11,14, ....
    for d=4, x= 2, 3,4,6, 7 .....

    So I am thinking atleast d....

    But not sure....I did not study number theory at graduation level.
  5. micromass

    micromass 20,039
    Staff Emeritus
    Science Advisor
    Education Advisor

    You're working (mod 5) here, so I suggest that you express the x also in (mod 5). (thus x can be 0,1,2,3 or 4).
    When I do this, I get

    for d=1: x=1
    for d=2: x=1,4
    for d=4: x=1,2,3,4

    Solutions like 9 are superfluous here, since 9=4 (mod 5).

    This is certainly correct, but the above example suggest exactly d!

    To prove this consider a number a coprime with p (for example take a=2 when p is odd). Then what can you say about


    By the way, do you know some group theory? It would make it a lot easier...
  6. Thank you so much...

    I agree with this...I realized my mistake x should be strictly less than p.

    Taking p to be odd (as suggested) p= 5 , then d =1, 2, 3, 4.

    Does 2 ^ (p-1)/d imply the following we get:

    for d=1, 2^ 4 = 16 works for d=1 that is , 16= 1 (mod 5).
    for d=2, 2 ^ 2= 4 works for d=2 that is, 4^2 = 1( mod 5)
    for d= 4, 2 ^ 1 =2 works for d =4, that is , 2^ 4 = 1 (mod 5).

    Does this mean that we can generate other values of x ( above we get x= 16) x has to be at least d but can be more than d as well.

    Please help !
    Last edited: Jun 8, 2011
  7. 9 is not prime.
  8. Thanks, Yuqing.
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?