1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A number theory question

  1. Aug 24, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that the equation [itex]x^k \equiv 1 (mod p)[/itex] has exactly k solutions if [itex] k|p-1[/itex].

    I'm also curious to know if it's possible to generalize this theorem this way:
    Prove that the equation [itex]x^k \equiv 1 (mod n)[/itex] has exactly k solutions if [itex]k|\varphi(n)[/itex] where [itex]\varphi(n)[/itex] indicates the Euler's totient function.
    2. Relevant equations

    3. The attempt at a solution
    Well, this is what I've done so far, but at some point I couldn't progressed any futher:

    Consider the polynomial xk-1. By a theorem we know that this polynomial would have k solutions at the maximum because its degree is k. Now, since k|p-1, there exists an integer number t such that: kt=p-1. we'll have:

    [itex] x^{p-1} - 1 = x^{kt} -1 = (x^k - 1)(x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1)[/itex]

    well, since p is a prime number, by Euler's theorem (or Fermat's little theorem to be more precise) we know that [itex] x^{p-1} - 1 \equiv 0 (mod p)[/itex] would have exactly p-1 solutions (since all the numbers from 1 to p-1 would be prime relative to p).

    now we'll have:

    [itex] x^{p-1} - 1 \equiv 0 (mod p)[/itex]
    [itex] x^{kt} -1 = (x^k - 1)(x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1) \equiv 0 (mod p)[/itex]
    [itex] p | (x^k - 1)(x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1) [/itex]
    since p is prime, p divides [itex]x^k -1[/itex] or [itex]x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1[/itex], therefore:

    [itex] x^k - 1 \equiv 0 (mod p)[/itex]
    [itex] x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1 \equiv 0 (mod p)[/itex]

    Now this is where I'm stuck. I don't know how to go further. I'm not sure if what I've done is useful to conclude anything either.
    Any helps would be appreciated.
  2. jcsd
  3. Aug 24, 2012 #2
    By the way, I found a counter example to that general statement.
    x2=1 (mod 8) has 4 solutions even though that 2 divides 4.
  4. Aug 25, 2012 #3
    I think p is prime in this question.
  5. Aug 25, 2012 #4
    Yes, it is.
    I'm sorry if having not said that caused confusion because I thought that was obvious from my solution to the problem.
  6. Aug 27, 2012 #5
    No ones knows how to prove it???
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook