A number theory question

  • Thread starter Arian.D
  • Start date
  • #1
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.
 

Answers and Replies

  • #2
101
0
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.
 
  • #3
296
0
I think p is prime in this question.
 
  • #4
101
0
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.
 
  • #5
101
0
No ones knows how to prove it???
 

Related Threads on A number theory question

  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
19
Views
2K
  • Last Post
Replies
4
Views
687
Top