4
$\begingroup$

(I'm a programmer, please excuse my abuse of or lack of proper mathematical language)

The other day I needed to find a natural number that is cleanly divisible by all integers in the range [1,10]

To start, I figured I'd just multiple them all:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 (a.k.a. 10!) = 3628800 3628800 mod 1 = 0 3628800 mod 2 = 0 3628800 mod 3 = 0 3628800 mod 4 = 0 3628800 mod 5 = 0 3628800 mod 6 = 0 3628800 mod 7 = 0 3628800 mod 8 = 0 3628800 mod 9 = 0 3628800 mod 10 = 0 

Well, that works, but I thought I could probably find a smaller number. I figured that I could remove e.g. the factor 6, because it can be made by multiplying the factors 2 and 3 that are also in the list.

So I tried just including prime numbers:

1 * 2 * 3 * 5 * 7 * 9 = 1890 1890 mod 1 = 0 1890 mod 2 = 0 1890 mod 3 = 0 1890 mod 4 = 2 uh-oh 

So, that doesn't work. It's because while 4 can be made by multiplying 2 and 2, there is only one 2 in the list.

What I eventually end up with is:

1 * 2 * 4 * 5 * 7 * 9 = 2520 

Or: A set of numbers in a range [1, N] that only includes those numbers that cannot be made by multiplying other numbers in the set, where each of those numbers may be used only once.

Now, the question (which is purely out of curiosity): Is this a common, known, named mathematical concept?

$\endgroup$
3
  • 3
    $\begingroup$ You can read about the least common multiple. $\endgroup$ Commented Apr 19, 2013 at 14:44
  • 1
    $\begingroup$ It appears the LCM of [1,10] might be 2520, but that doesn't name the set of numbers that can be multiplied to result in 2520. $\endgroup$ Commented Apr 19, 2013 at 14:46
  • $\begingroup$ Consider the prime factorization of the LCM. $\endgroup$ Commented Apr 19, 2013 at 14:57

2 Answers 2

3
$\begingroup$

Given a finite list $(N_i)_{1\leq i\leq n}$ of natural numbers $\geq1$ one may ask for the smallest number $N$ that is a multiple of all $N_i$. This $N$ is called the least common multiple (LCM) of the $N_i$ and may be obtained as follows: Each $N_i$ has a unique prime factorization of the form $$N_i=p_1^{\alpha_{i1}}\ p_2^{\alpha_{i2}}\ p_3^{\alpha_{i3}}\cdot\ldots=\prod_{k\geq1} p_k^{\alpha_{ik}}\ ,$$ where $(p_1,p_2,p_3,\ldots)$ is the sequence of all primes, the $\alpha_{ik}$ are natural numbers $\geq0$, and for each $i$ only finitely many $\alpha_{ik}$ are $\ne0$.

Consider a fixed prime $p_k$. This prime appears in the $N_i$ with various exponents $\alpha_{ik}$, and there will be a largest among them: Let $$\rho_k:=\max\{\alpha_{ik}\>|\>1\leq i\leq n\}\ .$$ This means: Among the $N_i$ there is at least one that has $p_k^{\rho_k}$ as a factor, but none containing a higher power of $p_k$. Taking again the fundamental theorem of arithmetic for granted it follows that the LCM $N$ of the $N_i$ is given by $$N=\prod_{k\geq1} p_k^{\rho_k}\ .\tag{1}$$

Formula (1) is more of a theoretical nature. In practice the LCM is determined using the so-called euclidean algorithm; and primes don't even make an appearance then.

$\endgroup$
1
$\begingroup$

You're looking for the least common multiple of {1, 2, ..., 10}. If you generalize to lcm({1, 2, ..., n}) this is A003418, which has a great deal of information on this problem. (You may find the OEIS a useful resource on this sort of problem.)

Here's one way to compute these numbers. For all the primes from 2 to the target number $n$, take the largest power of the prime which is less than or equal to $n$, and take the product of all these prime powers.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.