5
$\begingroup$

Does $p\equiv 1\pmod{p_1}, p\equiv1\pmod{p_2}$ imply that $p\equiv1\pmod{p_1p_2}$ ?

(Here $p,p_1,p_2$ are primes)

I was able to prove that $(p-1)^2\equiv0\pmod{p_1 p_2}$ but can we just root both sides?.

Also, would this work if $p_1$ and $p_2$ were not primes?

$\endgroup$
3
  • $\begingroup$ Are $p, p_1, p_2$ pairwise different primes? (Given the two congrences, only $p_1, p_2$ different is not implied.) $\endgroup$
    – Eric Towers
    May 27, 2018 at 16:14
  • $\begingroup$ @EricTowers I'm not sure what you mean but all three are distinct from one another $\endgroup$
    – Anvit
    May 27, 2018 at 16:27
  • $\begingroup$ Well, if $p_1 = p_2$, which is not prevented by anything shown, the implication strongly does not hold. Let $p_1 = p_2$ be a Sophie Germain prime and then take $p = 2p_1+1$. $\endgroup$
    – Eric Towers
    May 27, 2018 at 17:01

1 Answer 1

Reset to default
5
$\begingroup$

Yes it is true if we suppose $p_1\ne p_2$.

Since $p_1\mid p-1$ we have $p-1 =kp_1$. Since $p_2\mid p-1 = kp_1$ and $p_1,p_2$ are relatively prime we have by Gauss lemma that $p_2\mid k$ so $k= lp_2$ and thus $p-1 = lp_1p_2$ so $$p_1p_2 \mid p-1$$

And it does not work if $p_1,p_2$ are not both primes. Say $p=29,p_1=14$ and $p_2=7$

$\endgroup$
1
  • 1
    $\begingroup$ I just corrected the typo $\endgroup$
    – marwalix
    May 27, 2018 at 16:13

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.