0
$\begingroup$

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.

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

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

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

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

$\endgroup$
  • $\begingroup$ Please help with a formal proof. $\endgroup$ – jiten Mar 4 '18 at 9:02
  • 1
    $\begingroup$ He just provided a counterexample that your thing is not always true, so either you need to introduce some other restrictions or just accept that this is a counterxample. $\endgroup$ – Boots Mar 4 '18 at 9:05
  • $\begingroup$ I hope the edited title makes it more clear. $\endgroup$ – jiten Mar 4 '18 at 9:08
  • 1
    $\begingroup$ With the edited title you could assume that it does always imply that and show (generally) a case that defies it $\endgroup$ – Boots Mar 4 '18 at 9:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.