> HJG[@ Ibjbj44 "LViVi4nnnnnnnT$nRnnnrrrr
nnrrBrV@nn3`nNF0'V3nnnnn3rD
\
On a Property of the Least Common Multiple of Two Integers
Dan Kalman
The Least Common Multiple of two integers, is the least positive integer that is divisible by both integers. This is connected by a simple formula with the greatest common divisor of the two integers, a familiar topic from modern algebra and number theory. The purpose of this paper is to present a proof for the connection between least common multiple and greatest common divisor. Along the way we will see several other properties of the least common multiple, as well as a number of examples.
Throughout the discussion, we will consider only positive integers, the set of which is expressed as N. We also assume the notation and properties of the greatest common divisor presented in Hungerford [1]. In particular, if a and b are positive integers, we denote the greatest common divisor of a and b by (a,b). To begin the discussion of least common multiple, we present the following definition.
Definition 1. If a and b are positive integers, the least common multiple of a and b, denoted [a,b], is the least positive element of the set {z ( N : a | z and b | z }.
It should be remarked that for any positive integers a and b, their product ab is always divisible by both a and b, showing that the set of positive common multiples is not empty. Thus, [a,b] is always defined.
As an example, [4,6] = 12. To see this, observe that the multiples of 4 and 6, respectively, can be listed as follows:
4N = {4, 8, 12, 16, 20, 24, }6N = {6, 12, 18, 24, 30, 36 }.
We see that 12 is the least entry that is common to both sets. Indeed, 4|12 and 6|12 so 12 is definitely a common multiple. On the other hand, since the only positive multiple of 6 less than 12 is 6 itself, and since 4 is not a divisor of 6, we see that no other common multiple can be less than 12. This shows that 12 is the least common multiple.
In this example, we notice that 12 is not only less than or equal to every other common multiple of 4 and 6, it is also a divisor of all those multiples. We state this as a theorem.
Theorem 2. Let a and b be positive integers, and let c = [a,b]. Also, let C be the common multiples of a and b. That is, C = {z ( N : a | z and b | z }. Then C = cN.
Proof. Because c is a common multiple of a and b, we know both a and b are divisors of c. This shows they are also divisors of cn for any n in N. Put another way, every such cn is a common multiple of a and b, and so is an element of C. Therefore, we have established that cN ( C.
For the opposite inclusion, let d(C, so that d is an arbitrary common multiple of a and b. We must show that d ( cN. To that end, apply the division algorithm, expressing
d = cq + r (1)
where q and r are non-negative integers, and 0 d" r < c. Now both d and c are multiples of a, so we can write c = as and d = at for some positive integers s and t. Substitution in equation (1) then leads to at = asq + r. Rearranging this last equation then produces r = a (t - sq), demonstrating that a divides r. Exactly the same argument with b in place of a shows that b divides r as well. Thus, r is a common multiple of a and b. Now since r < d, which is the least positive common multiple, we see that r cannot be positive. Thus, we conclude r = 0, and by equation (1), d = cq. This shows that d is an element of cN. In summary, we have shown that d ( C implies d ( cN, which proves that C ( cN. This completes the proof that C = cN. %
The preceding theorem shows that the LCM of two integers is a divisor of every other common multiple of the integers. This is very similar to the situation with the greatest common divisor, which is also a divisor of every other common divisor. Next we show how factorization can be used to simplify the computation of LCM. This is provided by the following two lemmas.
Lemma 3. If r and s are positive integers, and if (r,s) = 1, then [r,s] = rs.
Proof. Let c = [r,s] . Since rs is a common multiple of r and s, and c is the least common multiple, we must have c d" rs. Now we know c is a multiple of r, so we can write c = rt for some positive integer t. By substitution, we observe that rt d" rs, and hence, t d" s.
Next, using the fact that c is also a multiple of s, we obtain s | c = rt, so s| rt. But recall that s and r are relatively prime. Therefore, by Theorem 1.5 in reference [1], we conclude that s| t. Since we already know that t d" s , it must follow that s = t. Finally, using the equation c=rt, we obtain c = rs. That is what we wanted to show. %
As an example, observe that [2,3] = 6 = 2(3. On the other hand, in the earlier example, we saw [4,6]= 12 ( 4(6. This is consistent with the lemma because 4 and 6 are not relatively prime, sharing a common factor of 2. Indeed, in this example, we see that [4,6]= 4(6/(4,6). As we will see below, this relationship between the least common multiple and the greatest common divisor holds in general. But first, let us proceed to the second lemma.
Lemma 4. If a, b, and t are positive integers, then [at,bt] = t [a,b].
Proof. Let c = [a,b] and let d = [at,bt]. Then a | c and b | c, so at | ct and bt | ct. This shows that ct is a common multiple of at and bt, and so ct ( d = [at,bt]. On the other hand, we know at | d and bt | d, so we may write d = atx = bty for some positive integers x and y. But then a | (d/t) and b | (d/t), so d/t is a common multiple of a and b. This implies d/t ( c, the least common multiple. Multiplying by t yields d ( ct. Combined with the earlier inequality, this shows d =Zo
0167xy~2389CDEFGHrtuvwxz{}
&
L
M
N
O
P
Q
d
ٹٴٹ h6h h8A6h'Ch8A5 jh8Ah'Ch8A6h'C hL5 hL6 h8A5h8AhLhL6hLhZG
JUVL
M
e
f
$a$gdLgdLId
e
u
v
y
z
8DHINOnorstuvw$%*+<=egpquv h5 jhhYS$h6 h6h h8A5h'Ch8AhhP
78xy<> !!gdL^gd `gdgd8Ap^pgd8A"#$%/0TUZ[pqrstuv &(24XZ~D^
/0λζʯh `h ` hYS$6 h `5 jhh `h ` h `6 jhhhYS$ h6h jh5 h5hh5E0=>JKTUfg "45GHIkmnopyz{|}~y hLV6hLV hL5 h B5 jhX
5hX
hX
6 jhhX
hX
5 hYS$6hX
hX
6 h `6h `G
!@A&(LRtx~*,24rt
@L h B6h B hYS$6hYS$ hLV5hX
hLV hLV6h'CS ! " * + a b e f k l n o !!!!!!J!_!!!!!!!!!!!!!!!!!!!""""""" """"""""" "!"*"+"."/"1"2"ƵƱұұұhNh V6h V hN5hNhN hN6hNhNhN6 h V6 h B6hYS$ jh B jh Bh'Ch BhLV h B5B!""<<>>>>AvAxAHHHHHHHHHI@^@gd}LgdgdL2"3"4"5"="B"G"L"Q"X"]"_"b"d"w"y"""""""""""""""""""""""""# #!#&#'#3#4#8#;#A#E#F#I#O#R#k#l#q#r################# hAA6hAA jhhh Vh V6 h6h jh Vh Vh Vh'C h V6hNh V6J ct. That is, we have derived [at,bt] = t [a,b], as desired. %
To illustrate this example, consider [10,35]. Factoring these two integers, we see that [10,35] = [2(5,7(5] = 5 [2,7]. Proceeding further, since (2,7) = 1, Lemma 3 shows [2,7] = 14. In this way we easily find [10,35] = 5(14 = 70. This approach to calculating the least common multiple is generally valid, and provides a proof for our main result.
Theorem 5. If a and b are positive integers, then (a,b)[a,b] = ab.
Proof. Let t = (a,b). Thus we may write a = rt and b = st for some positive integers r and s. Moreover, as stated in problem 16 in section 1.2 of reference [1], (r,s) = 1. Now according to Lemma 4, we can compute [a,b] = [rt,st] = t [r,s]. Next, by Lemma 3, we see that [a,b] = trs. Now multiply both sides of this equation by t. That gives t[a,b] = trts = ab. But t = (a,b). Therefore, we have shown that
(a,b)[a,b] = ab. This completes the proof. %
Notice that the conclusion of Theorem 5 can be rewritten in the form##<<B<D<H<J<L<N<P<V<X<Z<\<^<`<b<d<<<<<<<<<:=<=F=H=N=P=R=T=Z=\=^=`=j=l=r=t=====>>> >$>%>P>e>>>>>>>>>>>>>>>>>>>>>>>>>> h'C6hAA jh h B5 h5hNhhNh6h'C h6UhO>>>???? ?#?%?A?B?G?H????????????????????????????@@@@@@p@r@@@@@@@@@@@@@@@@@@AAAAAA A"A$A&A(A*A0A4A:AtAvABh}Lhh6 h6hh'Ch h6 h6hS
[a,b] = ab/(a,b).
We can apply this to the earlier example with a = 10 and b = 35. We obtain [10,35] = 10(35/ (10,35) = 350/5 = 70.
REFERENCES
[1.] Thomas Hungerford, Abstract Algebra an Introduction, 2nd Ed., Brooks-Cole, www.brookscole.com, 1997.
BHHHHHHHH
HHHHHDHFHOHPHcHdHiHjHoHpHsHtHHHHHHHHHHHHIIƾƶƯƨhZxvhZxvhidWhidWhRhRH*hRhZxv6hRhZxvhR hZxv5hZxvh}Lh}L jh}Lh}Lh}L6 h}L6h'Ch}LU& 1h/ =!"#$%@@@NormalCJ_HaJmH sH tH DA@DDefault Paragraph FontRi@RTable Normal4
l4a(k@(No List:0@:
List Bullet
&F4L
JUVLMef78
fg01;<qr01CD60@0x@0x@0x@0x@0x@0x@0@0@0x@0@0x@0 @0x@0@0@0@0x@0@0@0@00@00 @0 0 @0@0 @0@0 @0@0 @00@0x@0@00@0x000@0@00@00@0 0@0x0@00@0x0@00@00@000000x00x00x000 0
6>{00,`<<{00<{00@0<{00>{00,d
02"#>BI!"%
!IIDGMPsve g t
v
J
L
r
t
24oq
).58MP_d+.14PU\_
),FHQS
-047wz~259;=@+6wNPwy8Btv T
Y
nuJ
L
goW\MROQ57+.<BNP-2FP AH
*,FH.0uw24;=
3633333333333333333333333333333333333333333333333333333333333333333333JUN7
O
8f :j1D
26+6College of Arts and Sciences>>An8&(OMhh^h`OJQJo( ^` 5o(. ^` 5o(..0^`05o(...0^`05o(.... 88^8`5o(
..... 88^8`5o(......
`^``5o(.......
`^``5o(........
^`5o(.........\^`\5o(\^`\5o(.0^`05o(..0^`05o(... 88^8`5o( .... 88^8`5o(.....
`^``5o(
......
`^``5o(.......
^`5o(........n8(OM'C7X
:YS$8A B}LNLVidW `ZxvmZLvZRAA V@++++++
000....4`@``,@``4@```@@`<`|@`@`@UnknownGz Times New Roman5Symbol3&z Arial"qhҙ&Cҙ&*%
1%
124'' 3QH(?vZ:On a Property of the Least Common Multiple of Two IntegersCollege of Arts and SciencesCollege of Arts and SciencesOh+'0( P\
x
;On a Property of the Least Common Multiple of Two Integersfn aCollege of Arts and SciencesmmoollNormal.dotACollege of Arts and Sciencesmmo4llMicrosoft Word 10.0@| @d@%՜.+,04hp
American University1
'{
;On a Property of the Least Common Multiple of Two IntegersTitle
!"#$%&()*+,-./012345689:;<=>@ABCDEFIRoot Entry F cK1Table'WordDocument"LSummaryInformation(7DocumentSummaryInformation8?CompObjj
FMicrosoft Word Document
MSWordDocWord.Document.89q