# 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 $\displaystyle x$ is a solution to this congruence then $\displaystyle x \equiv b^y (\bmod p)$ for some $\displaystyle y\in \mathbb{Z}$. Therefore, $\displaystyle 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 $\displaystyle (n,p-1)$.