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

No vote yet

8 votes

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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.

Log in to reply

Clearly the easiest and clearest.

Log in to reply

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

clearly C is the best.

Log in to reply

a good solution.

Log in to reply

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

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?

Log in to reply

This was worth 100 points. Level 5's would not have seen it.

Log in to reply

post all the three solutions

Log in to reply

Log in to reply

Remarks added.

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

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

Log in to reply

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