HaCkEd By KaSpEr511

Super Divisible

June 28th, 2009

Here is a problem taken from Wild About Math (Monday Math Madness #33):

What’s the prime factorization of the smallest whole number that is divisible by all integers from 1 up to and including 50?

The competition is over now, the solutions are revealed and the winner is declared. Nevertheless the problem is interesting on its own and I didn’t see anybody tackled the general problem. Ok, so here is the generalization of the above problem.

What’s the prime factorization of the smallest whole number that is divisible by the first $n$ natural numbers?

Let $p_1,p_2,\cdots, p_s$ are all prime numbers that less or equal to $n$ and let $k_1,k_2,\cdots,k_s$ be the biggest integers such that $p_i^{k_i}\leq n$ . We claim that $S:=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$ is the smallest integer divisible by the first $n$ natural numbers.

Let’s prove the claim!

To prove the claim we need to show two things:

All natural numbers less or equal to $n$ divide $S$
If all natural numbers less or equal $n$ divide a number $T$ , then $S$ divides $T$ .

Let $m$ be a number between 1 to $n$ (inclusively). Let $m=q_1^{l_1}\cdots q_r^{l_r}$ be the prime factorization of $m$ . Since $q_i\leq n$ then each of $q_i$ must be one of the prime numbers $p_1,\cdots p_s$ . If we allow the exponent to be zero, then we can rewrite $m$ as $m=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}$ where $a_1,\cdots,a_s\geq 0$ . Now if $a_i >k_i$ , then by definition of $k_i$ , $m\geq p_i^{a_i}>n$ (contradiction!). Hence for all $i$ we must have $a_i\leq k_i$ and from this we conclude that $m$ divides $S$ .

Let $T$ be any number divisible by the first $n$ natural numbers. Since each of $p_i^{k_i}\leq n$ , then in particular $p_i^{k_i}$ divides $T$ . It follows that all product of these $p_i^{k_i}$ also divides $T$ , i.e., $S$ divides $T$ .

Now for the original problem, by looking at the prime numbers table here, the prime numbers which are less or equal to $50$ are $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$ and let us call them in the ascending order as $p_1,p_2,\cdots, p_{15}$ . One can easily checks that the corresponding $k_i$ ‘s are $k_1=5,k_2=3, k_3=k_4=2$ and $k_5=k_6=\cdots=k_{15}=1$ . So that the smallest numbers divisible by 1 to 50 is $2^{5}\cdot 3^{3}\cdot 5^2\cdot 7^2\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31\cdot 37\cdot 41\cdot 43\cdot 47$

Categories: Math Monday Madness

Tags: Integer factorization, Prime number Leave a comment

Super Divisible

Leave a comment

Subscribe

Translator

Recent Posts

Categories

Math Videos

Search

Comments

Meta

Categories