1
$\begingroup$

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$

I'm stuck.
$n = a \cdot k_1$
$n = b \cdot k_2$
$\therefore a \cdot k_1 = b \cdot k_2$

EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?

$\endgroup$
  • $\begingroup$ You are possibly thinking of the following: if $a\mid n$ and $b\mid n$ and $a,b$ are relatively prime, then $ab\mid n$. $\endgroup$ – David May 2 '14 at 0:13
  • $\begingroup$ Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment. $\endgroup$ – David May 2 '14 at 0:16
  • $\begingroup$ @David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime? $\endgroup$ – Celeritas May 2 '14 at 2:43
  • $\begingroup$ It is a sufficient condition that $a,b$ are relatively prime. $\endgroup$ – David May 2 '14 at 3:00
2
$\begingroup$

You are possibly thinking of the following: if $a\mid n$ and $b\mid n$ and $a,b$ are relatively prime (have no common factor except 1), then $ab\mid n$.

Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $b\mid ak$; since $a,b$ are relatively prime this implies $b\mid k$, so $k=bm$, so $n=abm$; therefore $ab\mid n$.

Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.

$\endgroup$
  • $\begingroup$ how do you know b | ak ? $\endgroup$ – Celeritas May 2 '14 at 2:45
  • $\begingroup$ Because $n=ak$, see the first equation in the proof. $\endgroup$ – David May 2 '14 at 2:56
  • $\begingroup$ How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k? $\endgroup$ – user394691 Oct 10 '17 at 21:43
  • $\begingroup$ @user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $b\mid akx$ (because $b\mid ak$) and $b\mid bky$ (obviously); so $b\mid akx+bky$, that is, $b\mid k$. $\endgroup$ – David Nov 5 '17 at 23:30
6
$\begingroup$

This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 \times 6 < 30$.

$\endgroup$
2
$\begingroup$

Updated: The edited version is still not true. At least two counterexamples in the comments below.

Prior counterexample: This is not true. $12|36$ and $9|36$, but $12\cdot9 = 108 \not | 36$.

$\endgroup$
  • 1
    $\begingroup$ We misread the question this isn't a counter example. $\endgroup$ – Git Gud May 2 '14 at 0:07
  • $\begingroup$ @GitGud . . . however, replacing $36$ by $36+12\times9$, that is, $144$, does give a counterexample. $\endgroup$ – David May 2 '14 at 0:10
  • $\begingroup$ Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example. $\endgroup$ – Git Gud May 2 '14 at 0:13
  • $\begingroup$ @GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood. $\endgroup$ – Eric Towers May 2 '14 at 1:30
  • $\begingroup$ @EricTowers Yes and your answer still isn't a counter example to statement in the OP's question. $\endgroup$ – Git Gud May 2 '14 at 1:32
0
$\begingroup$

Hint $\,\ a,b\mid n\iff {\rm lcm}(a,b)\mid n\!\!\!\overset{\ \ \ \large \times\, (a,b)}\iff ab\mid n(a,b),\, $ which is not equivalent to $\,ab\mid n\ $

$\endgroup$

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.