- #1
Arian.D
- 101
- 0
Homework Statement
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.
Homework Equations
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.