# Multiplying congruences.

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?

• Are $p, p_1, p_2$ pairwise different primes? (Given the two congrences, only $p_1, p_2$ different is not implied.) May 27, 2018 at 16:14
• @EricTowers I'm not sure what you mean but all three are distinct from one another May 27, 2018 at 16:27
• 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$. May 27, 2018 at 17:01

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$