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\)?

## Comments

Sort by:

TopNewestSolution 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

– Ahaan Rungta · 4 years, 6 months ago

Clearly the easiest and clearest.Log in to reply

– David Altizio · 4 years, 6 months ago

Not only that, but it also shows how to generalize the problem for numbers larger than \(1000\), which is always nice.Log in to reply

– Devin Ky · 4 years, 6 months ago

clearly C is the best.Log in to reply

– Brilliant Kumar · 4 years, 6 months ago

a good solution.Log in to reply

– Tan Li Xuan · 4 years, 6 months ago

This is a very clear and easy solution,and can be applied to other numbers.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

Nand 1000 is 1000, it can be inferred thatNis 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 integersNsuch that the least common multiple ofNand 1000 is 1000. – Calvin Lin Staff · 4 years, 6 months agoLog in to reply

– Omid Rooholfada · 4 years, 6 months ago

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.Log in to reply

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

Log in to reply

– Calvin Lin Staff · 4 years, 6 months ago

This was worth 100 points. Level 5's would not have seen it.Log in to reply

– Sri Krishna Priya Dhulipala · 4 years, 6 months ago

post all the three solutionsLog in to reply

– Zi Song Yeoh · 4 years, 6 months ago

I thought he already did?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\). From there, for 1000 to be a multiple at all, the number* because *any number over 1000 cannot have 1000 as a multiplemust be an integer divisor of 1000. Because the other numberis1000, N can be any divisor of 1000 at all, because the lowest multiple of 1000 is itself. From here, we justfind all the divisors of 1000, andcount 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 agoLog in to reply

– Nishanth Hegde · 4 years, 6 months ago

There is a typo..it had to be \(2 \times 500\)Log in to reply

– Omid Rooholfada · 4 years, 6 months ago

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).Log in to reply