Sums and divisors

Number Theory Level 3

What is the smallest value of $n$ such that $1 + 2 + 3 + \cdots + n$ is divisible by 1, 2, 3, 4, 5 and 6?

The answer is 15.

1 solution

Tom Engelsman
Nov 4, 2017

The LCM of 1, 2, 3 ,4, 5, and 6 is just $60 = 2^{2}3^{1}5^{1}$ . We are interested in the smallest positive integer $n$ such that:

$1 + 2 + 3 + ... + n = \frac{n(n+1)}{2} = 60k; k \in \mathbb{N}$

holds true. Solving for $n$ produces the quadratic $n^2 + n - 120k = 0 \Rightarrow n = \frac{-1 \pm \sqrt{1^2 - 4(1)(-120k)}}{2} = \frac{-1 + \sqrt{480k + 1}}{2}$ (NOTE: we only accept the positive root to ensure $n > 0$ ). At $k = 2$ , we obtain $n = \frac{-1 + \sqrt{961}}{2} = \frac{-1 + 31}{2} = 15$ .

Hence, the smallest such value for $n$ is $\boxed{15}.$

Why do you specifically choose the value $k = 2$ ? i.e. how did you know that the value $k = 2$ will correspond to an integer?

Syed Hamza Khalid - 2 years, 7 months ago

I just knew 31^2 = 961 = (480*2) + 1......k = 2 is the first positive integer 'k' to result in a perfect square for the radicand that results in the smallest positive integer for n. Just chalking it up to 25+ years of experience.

tom engelsman - 2 years, 7 months ago

Lol. It is okay. I solved this question by creating a table of $\dfrac{n(n +1)}{60}$ and then found out that 15 was the smallest $k$ to give a positive integer

Syed Hamza Khalid - 2 years, 7 months ago

Sums and divisors

The answer is 15.

1 solution

0 pending reports