3
$\begingroup$

Define the least common multiple of 2 nonzero integers a and b, denoted by $\operatorname{lcm}(a,b)$ to be the nonnegative integer $m$ such that both $a$ and $b$ divide $m$, and if $a$ and $b$ divide any other integer $n$, then $m$ also divides $n$. Prove that any two integers $a$ and $b$ have a unique least common multiple.

Not really sure how to prove this, but here's an attempt, I guess I am thinking it would be something like: Let the least common multiple of two nonzero integers $a$ and $b$ be given my $\operatorname{lcm}(a,b)=ab=m$. If $n/ab=x$ where $n$ and $x$ are integers, then $n/m=x$, so $m$ also divides $n$. Therefore any two integers $a$ and $b$ have a least common multiple.

Any suggestions for how to think of this problem?

$\endgroup$
  • $\begingroup$ lcm$(9,12)=36$, not $9\times 12=108$. The lcm$(a,b)$ is the smallest number that both $a$ and $b$ divide into. $\endgroup$ – Joffan Feb 6 '15 at 0:08
2
$\begingroup$

Multiples of $a$ are $$ a, 2a, 3a, 4a, \ldots\,. $$ Multiples of $b$ are $$ b, 2b, 3b, 4b, \ldots\,. $$ First we prove existence of a common multiple: $ab$ is a common multiple: it is the $b$th element of the first list and the $a$th element of the second.

It follows that the set of all common multiples is non-empty.

The well-ordering principle says every non-empty set of positive integers has a least member.

Now we prove uniqueness: There cannot be more than one least member since the integers are linearly ordered.

Q.E.D.

In some cases $ab$ is the least one; in other cases there are smaller common multiples than $ab$.

Pedagogical note:

Show a class of students this:

Multiples of $63$: ${}\quad63,126,189,252,315,378,\ldots$

Multuples of $77$: ${}\quad77,154,231,308,385,\ldots$

Then ask them to vote "yes" or "no" on this question: Is it possible that for either this pair of numbers or some other, the two lists go on forever without having any numbers in common? Have them write their votes on paper and turn them in anonymously and see what you get.

PS: OK, it said divisibly least, so let's add something: All multiples of the one that is numerically least -- call it $c$ -- are common multiples of $a$ and $b$ (proving that part is trivial), and here is the "hard" part: There are no others. For, suppose there were another, and call it $d$. Then the remainder on division of $d$ by $c$ would not be $0$ (since $d$ was assumed not a multiple of $c$) and would be less than $c$. And that remainder would be a common multiple of $a$ and $b$. So we have a common multiple of $a$ and $b$ that is less than $c$, thus a contradiction.

H/T @Bill Dubuque

$\endgroup$
  • 2
    $\begingroup$ Note that the OP is using a different definition of lcm (divisibly least, not least in value). So the above does not directly apply. $\endgroup$ – Bill Dubuque Feb 6 '15 at 0:38
  • $\begingroup$ @BillDubuque : You're quite right. I've added a postscript that sketches a proof that they're the same. $\endgroup$ – Michael Hardy Feb 6 '15 at 2:12
  • $\begingroup$ Simpler: since the set of common multiples is closed under subtraction so it follows by a one-line proof the the least positive element divides all others. However, that route is quite a roundabout way to deduce a result that follows immediately from the definition (see my answer). $\endgroup$ – Bill Dubuque Feb 6 '15 at 2:33
  • $\begingroup$ That seems pretty much the same as what I did, if one considers division to be "repeated subtraction" (as they say in fourth grade). $\endgroup$ – Michael Hardy Feb 6 '15 at 2:35
  • $\begingroup$ The relationship is clarified in the two proofs given in the linked answer. You left out some details above. If you supply those details then the proof will be longer than the linked one-line proof using subtraction (i.e. Proof 2 vs. Proof 1 in the link). This optimization works in $\,\Bbb Z\,$ because ideals simplify to subgroups. In more general Euclidean domains one has to use descent by mod/remainder (vs. the simpler descent by subtraction (Proof 1) in $\,\Bbb Z).\,$ Further the proofs abstract out key algebraic structure (ideals), multiples being a prototypical example. $\endgroup$ – Bill Dubuque Feb 6 '15 at 2:44
1
$\begingroup$

Hint $\ $ Combining the two directions of your definition yields the equivalent universal property

$$ a,b\mid n\iff m\mid n$$

If this holds for $\, m'\,$ too then $\,n = m'\,$ $\Rightarrow$ $\,m\mid m',\,$ and, by symmetry, $\,m'\mid m$.

$\endgroup$
0
$\begingroup$

It's just a natural result of the well ordering property of the natural numbers:

every non-empty set of natural numbers has a least element,

along with the corollary that such an element is unique.

If a and b are non-negative integers, ab is a common multiple of them. Thus the set of common multiples is non-empty and has a unique least element, which, by definition is lcm(a,b).

Adam V. Nease

$\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.