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

^{k}-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.