# Divisibility

• Jul 22nd 2010, 01:49 AM
Demandeur
Divisibility
Question: If \$\displaystyle a\mid{b}\$ and \$\displaystyle c\mid{d}\$, must \$\displaystyle (a+c)\mid(b+d)? \$

Counterexample: \$\displaystyle 2\mid{4}\$ and \$\displaystyle 3\mid{9}\$, but [tex]5\nmid{13}[/Math].

However, I want to argue along the lines of if \$\displaystyle a\mid{b}\$ and \$\displaystyle c\mid{d}\$, then \$\displaystyle b = aq\$ and \$\displaystyle d = cq'\$
for some integers \$\displaystyle q\$ and \$\displaystyle q'\$. How should we proceed from there?
• Jul 23rd 2010, 06:23 AM
Media_Man
I don't understand your question. The counterexample is proof enough that the theorem is false. Are you seeking a way of finding solutions?
• Jul 23rd 2010, 08:54 AM
Demandeur
Quote:

Originally Posted by Media_Man
I don't understand your question. The counterexample is proof enough that the theorem is false. Are you seeking a way of finding solutions?

Is the counterexample the only way to show that the statement is false? I was hoping that if we proceed as if we were to prove it,
we could derive a contradiction. Perhaps I'm expecting the wrong thing, but I do of course realise that a counterexample is enough
to be prove it false. Also, now that you mention it, how can we find the set of values for which it holds?
• Jul 23rd 2010, 09:09 AM
Media_Man
Finding Solutions
Quote:

how can we find the set of values for which it holds?
Problem: Choose arbitrary a,c and find values b,d fitting the following three criteria: a|b, c|d, and a+c|b+d

Solution: Restate the three criteria as b=aq, d=cq', b+d=(a+c)n (as you have correctly done in your first post). Substitute (1) and (2) into (3) to get aq+cq'=(a+c)n. This can be rearranged as a/c=(n-q')/(q-n). The left and right are both equal rational numbers, therefore the numerators and denominators are scalar multiples: as=n-q', cs=q-n. So q=n+cs and q'=n-as. Substituting back into (1) and (2), b=an+sca and d=cn-sca. So given 4 independent parameters a,c,n,s, b and d can be gotten by this formula to satisfy your three criteria. Proving this captures ALL solutions is probably trickier, but someone else might like to tackle it.