# Complicated MAths problem?

The least common multiple of positive integers a, b, c and d is equal to a + b + c + d.

Prove that abcd is divisible by at least one of 3 and 5.

http://www.amt.edu.au/wuimtotq01.pdf

Thanks

Relevance

According to the given information,

(a + b + c + d) is the least common multiple.

Which means that (a + b + c + d) is divisible by a, b, c, & d.

So, if I divide (a + b + c + d) by the smallest number (pretend it's a) I have to get an integer.

a = a This gives me "a" divided by "a" which gives me 1

b > a This gives me "b" divided by "a" which gives me 1 and a fraction (b-a)/a

c > a This gives me "c" divided by "a" which gives me 1 and a fraction (c-a)/a

d > a This gives me "d" divided by "a" which gives me 1 and a fraction (d-a)/a

So if I divide (a + b + c + d) by "a", I will get a 4 + the fractions which can only equal 1 resulting in a 5.

So 5 is a factor of the LCM.

On the other hand, if I divide (a + b + c + d) by the largest number (pretend it's d) I, again, have to get an integer.

a < d This gives me "a" divided by "d" which gives me a fraction a/d

b < d This gives me "b" divided by "d" which gives me a fraction b/d

c < d This gives me "c" divided by "d" which gives me a fraction c/d

d = d This gives me "d" divided by "d" which gives me 1

So if I divide (a + b + c + d) by "d", I will get a 1 + the fractions which can only equal 2 resulting in a 3.

So 3 is another factor of the LCM.

Now the least common multiple is either all the numbers multiplied by each other or a smaller factor of all the numbers multiplied by each other.

This means that: abcd is divisible by the LCM

Which means that abcd is also divisible by all the factors LCM.

This results in abcd being divisible at either 3, 5 or both.

Source(s): This is one heck of a problem. I really hope you were able to follow my logic. :D
• Login to reply the answers
• <= means less or equal as there is no such symbol on my keyboard

You can prove that abcd is divisible by 3 or 5 if any of these 4 integers is divisible by 3 or 5.

Since their position is the same, let's just say that a<=b<=c<=d. Even if the order is different, for example, a<=c<=d<=b , it doesn't matter, as we just put the smallest one in front and then rename them as a, then 2nd smallest as b, and so on. It's just to simplify things.

We'll start with d being something not divisible by 3. as a, b, c, and d are positive, it's obvious that a+b+c+d > d. But since a+b+c+d is the common multiple, it must be divisible by d. a=b=c=d is not possible because if that's the case, then the smallest multiple will be d, which is less than a+b+c+d. Since a=b=c=d is not possible, a, b, or c must be less than d, then a+b+c+d < 4d while a+b+c+d is divisible by d. Then, the only possibilities left are that a+b+c+d=3d or a+b+c+d=2d.

1. If a+b+c+d=3d, while a+b+c+d is divisible by all of those four, then a, b, and c divides 3d. Is it possible that only the factors in d are scattered among a, b, and c in the same or less power such that they all divide 3d? No. Because if that's the case, then they all will divide d, and the least multiple will be d, which has been proven not possible. So the only way so that a, b, and c divides 3d while not all of them divides d is by having at least one of a, b, and c divisible by 3. So for a+b+c+d=3d, it's already proved.

2. The only remaining possibility is that a+b+c+d=2d

that way, a+b+c=d that a+b+c+d= 2(a+b+c)

in this possibility, it's obvious c<d

because a<=b<=c , a+b+c+d= 2(a+b+c)<=6c

if 2(a+b+c)=6c, then a=b=c and that means d=3a=3b=3c. This will cause d being the least common multiple again. So this possibility doesn't even fulfill the requirement.

Then, 2(a+b+c)<6c. And it's obvious that 2(a+b+c)>2c . Since a+b+c+d = 2(a+b+c) is divisible by c, the remaining possibilities are

2(a+b+c) = 3c, 4c, or 5c

don't forget that in this second possibility a+b+c=d, then if 2(a+b+c)=3c or 5c, it will cause d to be divisible by 3 or 5 as well.

Now the remaining unproven possibility is 2(a+b+c)=4c that means a+b = c

the total sum now becomes a+b+c+d= 2(a+b+ (a+b)) = 4(a+b)

we now know that b divides a+b+c+d= 4(a+b)=4a+4b , which means that b divides 4a

as b is more or equal a, while 4a/a=4 , 4a/b <=4a/a=4

that means 4a/b=4 or 4a/b=3 or 4a/b=2 or 4a=b

For 4a/b=4 , a=b , which cause c=2a . That way, a and b divides c, and c divides d. That way, all of them divides d, and the least common multiple becomes d again, and it fails the requirement.

For 4a/b=3 , we get 3 divides 4a, which means 3 divides a.

For 4a/b = 2, b=2a, and then c= a+b= 3a. That means 3 divides c.

For 4a/b=1, b=4a , and c=a+b=5a. That means 5 divides c.

With this, we find out that all the options that can possibly fulfill the requirement of a+b+c+d being the least common multiple of a, b, c, and d lead to one of a,b,c, or d being divisible by 3 or 5. That way, abcd will definitely be divisible by 3 or 5.

Source(s): brute force
• Login to reply the answers
• Let LCM denote the least common multiple of a,b,c and d. If k1*a=k2*b=k3*c=k4*d=LCM then k1,k2,k3 and k4 cannot have a common divisor, q>1.

If they had z1=k1/q, z2=k2/q, z3=k3/q and z4=k4/q would render z1*a=z2*b=z3*c=z4*d=LCM/q<LCM which contradicts LCM being minimal. Furthermore LCM divides any common multiple and in particular abcd. Hence it suffices to show that LCM is divisible by 3 or 5.

Now since LCM=a+b+c+d we have a=(a+b+c+d)*1/k1 etc. so we must have

1/k1+1/k2+1/k3+1/k4=1

Now since we cannot have all k's equal to 4 as they have no common factor we must have both smaller and greater k's. Furthermore we cannot have k's less than 2 because then the sum would exceed 1. Hence we may assume 1<k1<4 ie. k1=2 or k1=3. If k1=3 we are done because then k1*a=LCM is divisible by 3.

Assume that k1=2. Then we must have 1/k2+1/k3+1/k4=1/2. We cannot have k2=k3=k4=6 because then q=2 would be a common divisor of all k's. Thus we must have both smaller and greater k's. And every k must be greater than 2 because otherwise the sum would exceed 1/2. Hence we may assume 2<k2<6 ie. k2=3, k2=4 or k2=5. If k2=3 or k2=5 we are done because then LCM is either divisible by 3 or 5.

Therefore assume that k2=4. Then it follows that 1/k3+1/k4=1/4. We cannot have k3=k4=8 because 2 would be a common divisor of all k's. Thus one will be greater and the other will be less than 8. At the same time each of them must be greater than 4 in order not to have their sum exceeding 1/4. Assume 4<k3<8. Then either k3=5, k3=6 or k3=7. We rule out k3=5 or k3=6 because then we would be done.

If k3=7 then 1/k4=1/4-1/7=3/28 which contradicts k4 being an integer. All cases where none of the k's are divisible by either 3 or 5 have been ruled out and we reach the conclusion that at least one of them must be. Hence LCM will be divisible by either 3 or 5, and so will abcd.

• Login to reply the answers
• Anonymous
9 years ago

is this by any chance your homework?

• Login to reply the answers
• Login to reply the answers