# A number theory question

Arian.D

## Homework Statement

Prove that the equation $x^k \equiv 1 (mod p)$ has exactly k solutions if $k|p-1$.

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

## 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:

$x^{p-1} - 1 = x^{kt} -1 = (x^k - 1)(x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1)$

well, since p is a prime number, by Euler's theorem (or Fermat's little theorem to be more precise) we know that $x^{p-1} - 1 \equiv 0 (mod p)$ 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:

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

$x^k - 1 \equiv 0 (mod p)$
$x^{k(t-1)} + x^{k(t-2)} + ... + x^k + 1 \equiv 0 (mod p)$

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.

Arian.D
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.

Millennial
I think p is prime in this question.

Arian.D
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.

Arian.D
No ones knows how to prove it???