# Prove : $\forall n,a,b \in \mathbb{Z}, n\mid (a+b)$ does not always imply $n\mid ab$.

(i) When $n$ is a factor of both $a,b$: Consider the prime factorization of $a,b$, and consider when $n\mid (a+b)$. So, $n,a,b$ must have at least one or more prime factors in common. Say $a= x^iy^jz^k, b= x^j, a+b = x^j(x^{|i-j|}y^jz^k+1)$, so $n = x^j.$(a factor of $(x^{|i-j|}y^jz^k+1)$). But, the product term $x^{|i-j|}y^jz^k$ might be either even or odd, and the parity changes on adding $1$, so $n=x^j$ or $ab$ only, as there can be no factor except itself, or $1$ of the term $(x^{|i-j|}y^jz^k+1)$.

Consider the case when $n= x^j$:
So, $ab = x^{i+j}y^jz^k$, and for $n=x^j$ to divide $ab$, it is must that there are common prime factors in the factorization of $j$ and $i$.

(ii) Either $n\nmid a$, or $n\nmid b$, but $n\mid (a+b)$: This case is only possible when $(n\nmid a) \wedge (n \nmid b)$, as not able to find a case otherwise.
Also, for the particular sub-case, not able to construct any approach, and applies for cases as $n=7, a=3,b=4$, as in the comment below.

• @ParclyTaxel I wanted to construct a formal proof. – jiten Mar 4 '18 at 8:57
• Why must n, a,b have a factor in common? 7|3+4 but none of them has factor in common – TheWanderer Mar 4 '18 at 8:58
• @TheWanderer Thanks, did not occur to me. But, then the proof cannot use the prime factorization. Please guide, how to proceed. – jiten Mar 4 '18 at 8:59
• I dont see the point to all this complication. A single counterexample constitutes a formal proof, does it not? – Kim Jong Un Mar 4 '18 at 9:38
• @KimJongUn Agree, but wanted to enhance proof making skills. – jiten Mar 4 '18 at 9:39

You could divide it into three cases:

1) If $n \mid (a+b)$ but $n \nmid a\cdot b$ then $a+b=nk$ but both $a,b$ don't have $n$ as a factor $\gcd(ab,n)=1$.

2) If $n \nmid (a+b)$ then $a+b \neq nk$ but either $\gcd(a,n)=n$ or $\gcd(b,n)=n$ so $n \mid ab$

3) If $n \mid (a+b)$ then $a+b = nk$ and both $a,b$ have $n$ as factor $gcd(ab,n)=n$ thus $a=np, b=nq, a+b=n(q+p)$

• Your answer is great, and gives a very easy, & might be the only possible approach to solve it. – jiten Mar 4 '18 at 9:32
• @jiten I appreciate that it's helpful for you. Thanks. – kub0x Mar 4 '18 at 9:34

This is not true. For example, $4 \mid 2+2$ and $4 \mid 2 \cdot 2$.