1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 1 '17 at 18:43
  • $\begingroup$ Isn't this a duplicate? $\endgroup$ – Bob Happ Mar 1 '17 at 21:54
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So easy????????????????????????????????? $\endgroup$ – user410985 Mar 1 '17 at 17:54
  • 1
    $\begingroup$ Btw, thanks for help. $\endgroup$ – user410985 Mar 1 '17 at 17:54
  • $\begingroup$ @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. $\endgroup$ – Xam Mar 1 '17 at 18:05
  • $\begingroup$ 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$. $\endgroup$ – Adren Mar 1 '17 at 18:13
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 1 '17 at 18:38
  • $\begingroup$ Are you suggesting to me that I should delete my answer? $\endgroup$ – Leox Mar 1 '17 at 18:43
  • 1
    $\begingroup$ No, why would you think that? Rather, I gave a link so that readers can learn how these common proofs are related. $\endgroup$ – Bill Dubuque Mar 1 '17 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy