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

128 Views Asked by At

Please vet my approach:
(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.

2

There are 2 best solutions below

2
On BEST ANSWER

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

4
On

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