# Thread: number of incongruent sols of x^n [congruent to] 1 (mod p)

1. ## number of incongruent sols of x^n [congruent to] 1 (mod p)

If p is a prime number and b is a primitive root modulo p, and n is a positive integer:

first I had to express the general solution of the congruence eqt. x^n [congruent to] 1 (mod p) in terms of b

...

I found the solutions are:
x= b^i for 1 <= i <= n such that (p-1)/gcd (p-1,i) | n

now I need to find how many incongruent solutions modulo p this congruence equation has...this one seems much tougher, and any help/hint would be appreciated

2. Originally Posted by minivan15
If p is a prime number and b is a primitive root modulo p, and n is a positive integer:

first I had to express the general solution of the congruence eqt. x^n [congruent to] 1 (mod p) in terms of b

...

I found the solutions are:
x= b^i for 1 <= i <= n such that (p-1)/gcd (p-1,i) | n

now I need to find how many incongruent solutions modulo p this congruence equation has...this one seems much tougher, and any help/hint would be appreciated
If $x$ is a solution to this congruence then $x \equiv b^y (\bmod p)$ for some $y\in \mathbb{Z}$. Therefore, $b^{ny}\equiv 1(\bmod p)\implies ny \equiv 0(\bmod p-1)$. The number of incongruent solutions to this congruence (which will leads to incongruence solutions to the original equation) is $(n,p-1)$.