# Prove prime $p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b\,$ without using Fundamental Theorem of Arithmetic

Let: $p$ $\in \mathbb{P}$ $\wedge$ $n_{1},n_{2}\in \mathbb{Z}$. Then: $p|(n_{1}n_{2})\implies p|n_{1} \vee \space p|n_{2}$

This little hypothesis is straightforward while using fundamental theorem of arithmetic. I also know that this can be proved directly by the use of the contraposition for the above implication. However, I wonder how to do this without referring to the fundamental theorem of arithmetic or to contraposition. I think that this must be very easy, but I can't see it right now. Thanks for help in advance.

• See here for a few proofs, including a direct proof by descent using the Division algorithm. This also includes further elaboration on the proofs using the GCD Distributive Law in Xam's answer, its Bezout form in Leox's answer. – Bill Dubuque Mar 1 '17 at 18:43
• Isn't this a duplicate? – Bob Happ Mar 1 '17 at 21:54

Let suppose that $p\not\mid n_1$, so $\gcd(p,n_1)=1$. Now, since $p\mid n_1n_2$ and $p\mid pn_2$, then by the definition of $\gcd$ we have $$p\mid \gcd(pn_2, n_1n_2)=n_2\gcd(p,n_1)^{*}=n_2.$$

In (*) we've used the property $\gcd(ac,bc)=c\gcd(a,b)$.

• So easy????????????????????????????????? – user410985 Mar 1 '17 at 17:54
• Btw, thanks for help. – user410985 Mar 1 '17 at 17:54
• @MIT it's easy if you have practice. I suggest you that in order to get familiarity with these simple proofs try to prove that property (*) that I've used. Good luck. – Xam Mar 1 '17 at 18:05
• I would start the same way, then use Gauss theorem : since $p\mid n_1n_2$ and $\gcd(p,n_1)=1$, we see that $p\mid n_2$. – Adren Mar 1 '17 at 18:13

Suppose that $p\not\mid n_1$. Then there exist integers $x,y$ such that $px+n_1 y=1.$ Multiple both sides by $n_2$ $$p (x n_2)+ n_1 n_2 y =n_2.$$ $p$ divides LHS thus $p \mid n_2.$

• This is the Bezout form of the proof in Xam's answer. See here where I prrecisely highlight the analogy. See also the answer linked in my comment on the question. – Bill Dubuque Mar 1 '17 at 18:38
• Are you suggesting to me that I should delete my answer? – Leox Mar 1 '17 at 18:43
• No, why would you think that? Rather, I gave a link so that readers can learn how these common proofs are related. – Bill Dubuque Mar 1 '17 at 18:45