 # Problem of the Week Problem D and Solution Perfect Squares

## Problem

Determine the number of perfect squares less than $$10\,000$$ that are divisible by $$392$$. Note: A perfect square is an integer that can be expressed as the product of two equal integers. For example, $$49$$ is a perfect square since $$49 = 7\times 7 = 7^2$$.

## Solution

In order to understand the nature of perfect squares, let’s begin by examining the prime factorization of a few perfect squares.

From the example, $$49 = 7^2$$. Also, $$36=6^2=(2\times 3)^2=2^2\times 3^2$$, and $$144=12^2=(3\times 4)^2=3^2\times (2^2)^2=3^2\times 2^4$$.

From the above examples, we note that, for each perfect square, the exponent on each of its prime factors is an even integer greater than $$0$$. This is because a perfect square is created by multiplying an integer by itself, so all of the primes in the factorization of the integer will appear twice. Also, for any integer $$a$$, if $$m$$ is an even integer greater than or equal to zero, then $$a^m$$ is a perfect square. This is because if $$m$$ is an even integer greater than or equal to $$0$$, then $$m=2n$$ for some integer $$n$$ greater than or equal to $$0$$, and so $$a^m = a^{2n} = a^n \times a^n$$, where $$a^n$$ is an integer.

To summarize, a positive integer is a perfect square exactly when the exponent on each prime in its prime factorization is even.

The number $$392 =8 \times 49=2^3\times 7^2$$. This is not a perfect square since the power $$2^3$$ has an odd exponent. We require another factor of $$2$$ to obtain a multiple of $$392$$ that is a perfect square, namely $$2\times 392=784$$. The number $$784=2^4\times 7^2=(2^2\times 7)^2=28^2$$, and is the first perfect square less than $$10\,000$$ that is divisible by $$392$$.

To find all the perfect squares less than $$10\,000$$ that are multiples of $$392$$, we will multiply $$784$$ by squares of positive integers, until we reach a product larger than $$10\,000$$.

If we multiply $$784$$ by $$2^2$$, we obtain $$3136$$ which is $$56^2$$, a second perfect square less than $$10\,000$$. If we multiply $$784$$ by $$3^2$$, we obtain $$7056$$ which is $$84^2$$, a third perfect square less than $$10\,000$$.

If we multiply $$784$$ by $$4^2$$, we obtain $$12\,544$$ which is a greater than $$10\,000$$. No other perfect squares divisible by $$392$$ exist that are less than $$10\,000$$.

Therefore, there are $$3$$ perfect squares less than $$10\,000$$ that are divisible by $$392$$.