CEMC Banner

Problem of the Week
Problem E and Solution
All Square

Problem

The positive multiples of \(3\) from \(3\) to \(2400\), inclusive, are each multiplied by the same positive integer, \(n\). All of the products are then added together and the resulting sum is a perfect square.

Determine the value of the smallest positive integer \(n\) that makes this true.

A list of positive integers starting with 3, 6, and 9 and
ending with 2400.

Solution

What does the prime factorization of a perfect square look like? Let’s look at a few examples: \(9=3^2\), \(36=6^2=2^23^2\), and \(129\,600=360^2=2^63^45^2\). Notice that the exponent on each of the prime factors in the prime factorization in each of the three examples is an even number. In fact, a positive integer is a perfect square exactly when the exponent on each prime in its prime factorization is even. Can you convince yourself that this is true?

The positive integer \(n\) is the smallest positive integer such that \[3n+6n+9n+\cdots + 2394n + 2397n+2400n \tag{1}\]

is a perfect square.

Factoring expression \((1)\), we obtain \[3n(1+2+3+\cdots+798+799+800)\] Then, using the formula \(1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}\), with \(n=800\), we see that this expression is equal to \[3n\left(\frac{800\times 801}{2}\right)=3n(400)(801)\] Factoring \(3\times 400\times 801\) into the product of primes, we have that expression \((1)\) is equal to \[3n[(2)(2)(2)(2)(5)(5)][(3)(3)(89)]=n(2^4)(5^2)(3^3)(89)\tag{2}\]

We need to determine what additional factors are required to make the quantity in expression \((2)\) a perfect square such that \(n\) is as small as possible. In order for the exponent on each prime in the prime factorization to be even, we need \(n\) to be \(3\times 89=267\). Then the quantity in expression \((2)\) is the perfect square \[n(2^4)(5^2)(3^3)(89)=(3)(89)(2^4)(5^2)(3^3)(89)=(2^4)(5^2)(3^4)(89^2)=\left[(2^2)(5)(3^2)(89)\right]^2\]

Therefore, the smallest positive integer is \(267\) and the perfect square is \[267\times 3\times 400\times 801=256\,640\,400=(16\,020)^2\]

Note: When solving this problem, we could have instead noticed that \(3n + 6n + 9n+ \cdots + 2400n\) is an arithmetic series with \(t_1 = 3n\) and \(t_{800}=2400n\).

Substituting these values for \(t_1\) and \(t_{800}\) into the formula for the sum of the terms in an arithmetic series, we get \[S_{800} = \frac{800}{2}\left( 3n + 2400n\right) = 400(2403n)\] When we factor \(400(2403n)\) into the product of primes, we get the same expression as \((2)\), and then we can continue from there to get the solution of \(267\).