Generalizing the Theorem: Number of Solutions to x^k ≡ 1 (mod n)

In summary, the conversation discusses proving that the equation x^k \equiv 1 (mod p) has exactly k solutions if k|p-1, and whether this theorem can be generalized to x^k \equiv 1 (mod n) with k|\varphi(n). The conversation also mentions a counterexample to the generalized statement and confirms that p is prime in the question.
  • #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.
 
Physics news on Phys.org
  • #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.
 
  • #3
I think p is prime in this question.
 
  • #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.
 
  • #5
No ones knows how to prove it?
 

What is number theory?

Number theory is a branch of mathematics that studies the properties and relationships of integers and their patterns and structures.

What are prime numbers?

Prime numbers are positive integers that are only divisible by 1 and themselves. Examples include 2, 3, 5, 7, and 11. Prime numbers play a crucial role in number theory.

What is the difference between a prime number and a composite number?

A prime number has only two factors, 1 and itself, while a composite number has more than two factors. For example, 5 is prime because its only factors are 1 and 5, while 6 is composite because it has three factors: 1, 2, and 3.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a given limit. It works by crossing off all multiples of each prime number starting from 2, leaving behind only the prime numbers.

What are some real-world applications of number theory?

Number theory has many practical applications, including cryptography, coding theory, and computer security. It is also used in fields such as physics, chemistry, and biology to model natural phenomena and solve complex problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
429
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
836
  • Calculus and Beyond Homework Help
Replies
2
Views
977
  • Calculus and Beyond Homework Help
Replies
24
Views
617
Replies
12
Views
216
  • Calculus and Beyond Homework Help
Replies
4
Views
919
  • Calculus and Beyond Homework Help
Replies
1
Views
546
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
Back
Top