# Solutions to $x^p \equiv 1$

I have \begin{align*} p = 2p_1+1 && p_1 = 2p_2+1 \\ q = 2q_1+1 && q_1 = 2q_2+1 \end{align*} where $p,q, p_1, q_1, p_2$ and $q_2$ are distinct primes. I am now trying to find the number of solutions for the congruence $$x^{p_2} \equiv 1 \pmod{4p_1q_1}$$ I know that the answer is supposed to be $p_2$ but I cannot figure out why that is. I can assume that $p_1, q_1$ and $4$ are pairwise relatively prime, so I can break it up into \begin{align*} x^{p_2} &\equiv 1 \pmod{4}\\ x^{p_2} &\equiv 1 \pmod{p_1}\\ x^{p_2} &\equiv 1 \pmod{q_1} \end{align*} but I am stuck from here. Any hints?

• When you rewrite your equation in terms of congruences in $4,p_1,q_1$, it should be clear that the first congruence gives you one solution. The second one gives you $p_2$ solutions(modulo $p_1$) which can be shown with Fermat's little theorem. The last one gives you one solution (modulo $q_2$) so you get $p_2$ solutions altogether. – daruma May 16 '17 at 3:51

1. $x^{p_2} \equiv1(\textrm{mod}\hspace{3pt}4)$. This tell me $x$ is odd so, $x\equiv \pm 1(\textrm{mod}\hspace{3pt}4)$. But $(-1)^{p_2}\equiv -1(\textrm{mod}\hspace{3pt}4)$ as $p_2$ is odd.

So, $x\equiv 1 (\textrm{mod}\hspace{3pt}4)$

1. $x^{p_2}\equiv 1(\textrm{mod}\hspace{3pt}p_1)$

Fermat's little theorem tells us that $x^{p_1-1}\equiv x^{2p_2}\equiv 1(\textrm{mod}\hspace{3pt}p_1)$. Since $p_1$ is a prime, $a^2\equiv 1(\textrm{mod}\hspace{3pt}p_1)$ tell us $a\equiv \pm 1 (\textrm{mod}\hspace{3pt}p_1)$. Now of the $p_1-1$ classes that are not identical to $0$, exactly half of them will satisfy $x^{p_2}\equiv -1(\textrm{mod}\hspace{3pt}p_1)$ and exactly half of them will satisfy $x^{p_2}\equiv 1(\textrm{mod}\hspace{3pt}p_1)$.

(There are several ways of seeing this. Either consider the fact that there is a primitive root for modulo primes or looking at the bijection $a\mapsto -a$ where $a$ is an element whose $p_2$-th power is $1$.)

So in particular, there are $\frac{p_1-1}{2}=p_2$ distinct solutions modulo $p_2$.

1. $x^{p_2}\equiv 1(\textrm{mod}\hspace{3pt}q_1)$.

Fermat tells me $x^{2q_2}\equiv 1 (\textrm{mod}\hspace{3pt}q_1)$. Unless $p_2=2$, we have that $2q_2$ and $p_2$ are coprime as $q_2$ and $p_2$ are distinct primes. So, in particular, $x^{p_2}\equiv 1 (\textrm{mod}\hspace{3pt}q_1)$ immediately tells me $x\equiv 1(\textrm{mod}\hspace{3pt}q_1)$.

So finally, $1\times p_2\times 1=p_2$ is the number of solutions.

• good answer, you beat me to it. but you miss an important part what about the the other solution when $x^{p_2} = -1 \mod 4$ and $x^{p_2} = -1 \mod p_1$ which adds another $p_2$ solutions unless you prove that they are the same as the previous $p_2$ solutions. – Ahmad May 16 '17 at 12:37
• @Ahmad I am not sure what you mean unless the subscripts are not what they are supposed to be. We are using Chinese remainder theorem so we know as a fact that $x^p_2\equiv 1(\textrm{mod}\hspace{3pt} 4)$ and similarly for $p_2$. – daruma May 16 '17 at 12:58
• Assume $x^{p_2} = 1 \mod 4$ and $x^{p_2} = 1 \mod p_1$ then $(-x)^{p_2} = -1 \mod 4$ and $(-x)^{p_2} = -1 \mod p_1$ so they are both valid solutions to $x^{p_2} = 1 \mod 4 p_1$ , but the problem with your answer as with the one i was working on is the i did not deal with the other valid solutions (in proving that they are actually equal to the first $p_2$ solutions ) – Ahmad May 16 '17 at 13:07
• In your first line, did you meant to say $(-1)^{p_2} \equiv -1 \pmod{4}$ as $p_2$ is odd? If not, how does it follow from $p_1$ being odd? – Nasenhaar May 18 '17 at 0:21
• By Fermat, $x^{q_1-1}\equiv 1(\textrm{mod}\hspace{3pt} q_2)$. We also know $x^{p_2}\equiv 1(\textrm{mod}\hspace{3pt} p_2)$. By Bezout's identity(or if you prefer by using Euclid's algorithm), we know there are integers $a,b$ such that $a(q_2-1)+b(p_1)=1$. This is because $q_2-1=2q_1$ and $p_1$ are coprime. So $x^{a(q_2-1)+b(p_1)}\equiv 1(\textrm{mod}\hspace{3pt} q_2)$. – daruma May 19 '17 at 13:49