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

Question

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.

Answer 1

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)$.

Answer 2

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.$