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?

  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Ahmad May 16 '17 at 12:37
  • $\begingroup$ @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$. $\endgroup$ – daruma May 16 '17 at 12:58
  • $\begingroup$ 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 ) $\endgroup$ – Ahmad May 16 '17 at 13:07
  • $\begingroup$ 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? $\endgroup$ – Nasenhaar May 18 '17 at 0:21
  • 1
    $\begingroup$ 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)$. $\endgroup$ – daruma May 19 '17 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.