Waste less time on Facebook — follow Brilliant.
×

[Calvin] Which solution would you feature (9)?

Previous discussion

Below, we present a problem from the 2/11 Algebra and Number Theory set, along with 3 student submitted solution. You may vote up for the solutions that you think should be featured, and should vote down for those solutions that you think are wrong.

LCM with 1000 How many positive integers \(N\) are there such that the least common multiple of \(N\) and 1000 is 1000?

You may try the problem by clicking on the above link.

All solutions may have LaTeX edits to make the math appear properly. The exposition is presented as is, and has not been edited.

About 60% of those who answered this problem got it correct.

\[ \mbox{Remarks from Calvin} \]

When it comes to proof-writing, it is often difficult to determine the exact amount of information to provide. You should identify your audience, which would be someone of the same mathematical ability who is unable to solve the problem. You should provide enough justification for your peers to understand, without requiring them to read your mind. Because this question is very basic, you have to explain the important statement, i.e. show that "LCM\((N, 1000) = 1000\) if and only if \(N\) is a divisor of 1000". This is a unique property, which doesn't hold for "LCM\((N, M) = 1000\)", where \(M \neq 1000\). You will need to explain why non-divisors of 1000 will not work, and why a divisor of 1000 will work.

Solution A - The statement "As the lowest common multiple is 1000, we are looking for numbers which divide perfectly into 1000." is merely a restatement of the "if and only if property", and doesn't offer any justification. While he was able to present the correct "interpretation of the question", it offers no explanation of the reasoning apart from saying that "\(N\) is no more than 1000".

Solution B - I have chosen to feature this solution presented by Russell, because it explains the "If and only if" fact. I like that he mentioned "Because the other number is 1000", to stress that this solution is unique to the condition given.

As Omid mentioned, the explanation could be made cleaner. He should have continued to refer to "the number \(N\)", and "the other number 1000". When talking about a function on 2 variables, make sure you distinguish the two. An alternative way is to talk about the variable in the first coordinate / entry, vs the variable in the second coordinate / entry.

Solution C - This solution is correct, and can be understood by others who have already solved the problem. However, you will often be asked to explain to others who do not already understand it, and so you should learn how to provide enough information that others will be willing to agree with you.

For students who have difficulty counting the number of divisors of an integer, read the blog post.

Pop Quiz: How would you approach the general problem: How many positive integers \(N\) are there such that the least common multiple of \(N\) and \(M\) is \(A\)?

Note by Calvin Lin
4 years, 6 months ago

No vote yet
8 votes

Comments

Sort by:

Top Newest

Solution C - Denote the least common multiple of two integers, m and n, by lcm(m,n). lcm(n,1000)=1000 if and only if n divides 1000. All that remains is to count the divisors of 1000. Note that \(1000=(2^3)*(5^3)\). The exponents in the prime factorization enable us to count the divisors. Simply add 1 to each exponent, and then multiply them all together. In this case, 3+1=4, so the number of divisors is 4*4=16. Calvin Lin Staff · 4 years, 6 months ago

Log in to reply

@Calvin Lin Clearly the easiest and clearest. Ahaan Rungta · 4 years, 6 months ago

Log in to reply

@Ahaan Rungta Not only that, but it also shows how to generalize the problem for numbers larger than \(1000\), which is always nice. David Altizio · 4 years, 6 months ago

Log in to reply

@Calvin Lin clearly C is the best. Devin Ky · 4 years, 6 months ago

Log in to reply

@Calvin Lin a good solution. Brilliant Kumar · 4 years, 6 months ago

Log in to reply

@Calvin Lin This is a very clear and easy solution,and can be applied to other numbers. Tan Li Xuan · 4 years, 6 months ago

Log in to reply

Solution A - The most important step to solving this is interpretation of the question. A lowest common multiple is the lowest integer into which two smaller integers perfectly and commonly divide. Therefore, in the statement that the lowest common multiple of N and 1000 is 1000, it can be inferred that N is no more than 1000 (and as stated by 'positive integers' - no less than 1). As the lowest common multiple is 1000, we are looking for numbers which divide perfectly into 1000. Factors of 1000, essentially. There are 16 factors of 1000: 1 ( 1 * 1000 = 1000 ) 2 ( 2 * 500 = 1000 ) 4 ( 4 * 250 = 1000 ) 5 ( 5 * 200 = 1000 ) 8 ( 8 * 125 = 1000 ) 10 ( 10 * 100 = 1000 ) 20 ( 20 * 50 = 1000 ) 25 ( 25 * 40 = 1000 ) 40 ( 40 * 25 = 1000 ) 50 ( 50 * 20 = 1000 ) 100 ( 100 * 10 = 1000 ) 125 ( 125 * 8 = 1000 ) 200 ( 200 * 5 = 1000 ) 250 ( 250 * 4 = 1000 ) 500 ( 500 * 2 = 1000 ) 1000 ( 1000 * 1 = 1000 ) Q.E.D. There are sixteen positive integers N such that the least common multiple of N and 1000 is 1000. Calvin Lin Staff · 4 years, 6 months ago

Log in to reply

@Calvin Lin Although this solution is correct, it is unnecessarily wordy. For example, much of the introduction could be omitted. Also, words such as "inferred" should be avoided, as they imply that the statement is not absolutely true. Note that it is generally easier to count the divisors of a number using the prime factorization method in Solution C, rather than listing them. Omid Rooholfada · 4 years, 6 months ago

Log in to reply

what level was this problem in? Harshit Kapur · 4 years, 6 months ago

Log in to reply

@Harshit Kapur This was worth 100 points. Level 5's would not have seen it. Calvin Lin Staff · 4 years, 6 months ago

Log in to reply

@Calvin Lin post all the three solutions Sri Krishna Priya Dhulipala · 4 years, 6 months ago

Log in to reply

@Sri Krishna Priya Dhulipala I thought he already did? Zi Song Yeoh · 4 years, 6 months ago

Log in to reply

Remarks added. Calvin Lin Staff · 4 years, 6 months ago

Log in to reply

Solution B - For the least common multiple of N and 1000 to be 1000, the number is already limited to \(N \leq 1000\) * because *any number over 1000 cannot have 1000 as a multiple. From there, for 1000 to be a multiple at all, the number must be an integer divisor of 1000. Because the other number is 1000, N can be any divisor of 1000 at all, because the lowest multiple of 1000 is itself. From here, we just find all the divisors of 1000, and count how many there are. We thus get \(1\times1000\), \(2\times5000\), \(4\times250\), \(5\times200\), \(8\times125\), \(10\times100\), \(20\times50\), and \(25\times40\). The resulting answer is * *16 **: (1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, and 1000). Calvin Lin Staff · 4 years, 6 months ago

Log in to reply

@Calvin Lin There is a typo..it had to be \(2 \times 500\) Nishanth Hegde · 4 years, 6 months ago

Log in to reply

@Calvin Lin This solution appears to be correct. However, in some places the wording is ambiguous. In particular, it is not immediately clear what "the number" and "the other number" refer to. On another note, it is unnecessary to find all of the divisors of 1000; we only need to count how many there are (see Solution C for a quick way to do this). Omid Rooholfada · 4 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...