I have just began learning number theory and I wanted to prove the following statement:

'if $x$ is coprime with each $p_i$ then $x$ is coprime with $p_1...p_n$'

This was actually a statement from a proof within CRT and they also had the condition that $p_i$ are pairwise coprime but I am not sure if that was used in proving the above statement.

Here is my attempt.

Suppose for a contradiction that $x$ is coprime with each $p_i$ and $x$ is not coprime with $p_1...p_n$, then there exists a prime number $q$ such that $q\mid x$, $q\mid p_1...p_n$. By the property that $q$ is prime we must have $q\mid p_i$ for some $i$. Hence $\operatorname{hcf}(x, p_i)\geq q$ for that specific $i$ and so there is a contradiction.

As I said, since I didn't use at all the pairwise coprime property of $p_i$, I am not sure if my proof was correct, could someone please let me know if there were any flaws in my argument?

  • 3
    $\begingroup$ You are right that you don't need to assume the $p_i$ are pairwise coprime. Indeed in an extreme case all the $p_i$ could be equal, and the conclusion still holds. $\endgroup$ – hardmath Feb 21 at 15:10

Your proof is correct. FYI, you're basically using the general version of Euclid's lemma in your statement that if a prime $q \mid p_1 \ldots p_n$, then for at least one $i$ you have $q \mid p_i$.

Also, as hardmath's question comment states, you don't actually need to assume the $p_i$ values are coprime. It's not required, or needed, anywhere in your proof.


Yes, that argument is correct. Generally it shows: $ $ if $\,a_i$ are coprime to $n$ then so too is their product. This has a nice algebraic interpretion: by Bezout, $\,a_i\,$ is comprime to $\,n\iff a_i$ is invertible $\!\bmod n,\,$ so we can view the result as: $ $ invertibles ("units") are closed under multiplication, which is clear by

$$\begin{align} a_k^{-1}\cdots a_1^{-1}&\:\!\times\:\! (a_1\cdots a_n) =1\\[.2em] \Rightarrow\ \ a_k^{-1}\cdots a_1^{-1} &= (a_1\cdots a_n)^{-1}\end{align}\ \ $$

Thus the invertible elements of a ring form a multiplicative group - known as the unit group (a key object in many ring theoretic contexts).


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.