## Divisible Perfect Squares

How many different numbers between 2 to 100 satisfy all three of the following conditions:
1.  The number is not a prime number.
2.  The number is not divisible by a perfect square greater than one.
3.  The double of the number is not divisible by a perfect square greater than one.
Source: mathcontest.olemiss.edu 4/25/2011

SOLUTION
We use the process of elimination to find these special numbers. Let’s list all the numbers from 2 to 100 in a table and cross out all the numbers that are either 1) prime or 2) perfect square or 3) multiple of a perfect square. Even though the numbers we are considering are less than or equal to 100, their doubles are larger than 100 so it is very convenient to write down all the multiples of the perfect squares so that you can see in a glance whether the number or the double of the number is a multiple of a perfect square or not.

STEP 1 Cross out the prime numbers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

STEP 2 Cross out the perfect squares
4, 9, 16, 25, 36, 49, 64, 81, 100.

STEP 3 Cross out the multiples of the perfect squares
3.1 Multiples of 4 less than or equal to 100

8, 12, 16, 20, 24, 28, 32, 36, 40, 44,
48, 52, 56, 60, 64, 68, 72, 76, 80, 84,
88, 92, 96, 100.

3.2 Multiples of 9 less than or equal to 100
18, 27, 36, 45, 54, 63, 72, 81, 90, 99.

3.2 Multiples of 16 less than or equal to 100
32, 48, 64, 80, 96.

3.3 Multiples of 25 less than or equal to 100
50, 75, 100.

3.4 Multiples of 36 less than or equal to 100
72.

3.5 Multiples of 49 less than or equal to 100
98.

STEP 4 Double of the number
Our original list of numbers from 2 to 100 should now be smaller than before. These leftover numbers satisfy condition (1) and condition (2). All we have to do now is to consider whether their doubles are multiples of perfect squares or not.

Example 1
The first leftover number is 6. The double of 6 is 12. But 12 is a multiple of 4, a perfect square, so we eliminate 6.

Example 2
10 is the next leftover number. The double of 10 is 20. But 20 is a multiple of 4, so we eliminate 10.

Example 3
15 is one of the leftover numbers. The double of 15 is 30. If you look at the lists of multiples of perfect squares, none of them shows 30. Therefore, we accept 15 as a solution.

Example 4
91 is a leftover number near the bottom of our list. The double of 91 is 182.

The multiples of 4 near 182 are: 176, 180, 184, 188.
The multiples of 9 near 182 are: 171, 180, 189, 198.
The multiples of 16 near 182 are: 144, 160, 176, 192.
The multiples of 25 near 182 are: 125, 150, 175, 200.
The multiples of 36 near 182 are: 108, 144, 180, 216.
The multiples of 49 near 182 are: 98, 147, 196.
The multiples of 64 near 182 are: 128, 192.

None of them shows 182. Therefore, we accept 91 as a solution.

SUMMARY
The table below summarizes our results:

 Number Double of number Divisible by a perfect square Solution 6 12 Y (12 ÷ 4 = 3) 10 20 Y (20 ÷ 4 = 5) 14 28 Y (28 ÷ 4 = 7) 15 30 N Y 21 42 N Y 22 44 Y (44 ÷ 4 = 11) 26 52 Y (52 ÷ 4 = 13) 30 60 Y (60 ÷ 4 = 15) 33 66 N Y 34 68 Y (68 ÷ 4 = 17) 35 70 N Y 38 76 Y (76 ÷ 4 = 19) 39 78 N Y 42 84 Y (84 ÷ 4 = 21) 46 92 Y (92 ÷ 4 = 23) 51 102 N Y 55 110 N Y 57 114 N Y 58 116 Y (116 ÷ 4 = 29) 62 124 Y (124 ÷ 4 = 31) 65 130 N Y 66 132 Y (132 ÷ 4 = 33) 69 138 N Y 70 140 Y (140 ÷ 4 = 35) 74 148 Y (148 ÷ 4 = 37) 77 154 N Y 78 156 Y (156 ÷ 4 = 39) 82 164 Y (164 ÷ 4 = 41) 85 170 N Y 86 172 Y (172 ÷ 4 = 43) 87 174 N Y 91 182 N Y 93 186 N Y 94 188 Y (188 ÷ 4 = 47) 95 190 N Y

Thus, the 16 special numbers are: 15, 21, 33, 35, 39, 51, 55, 57, 65, 69, 77, 85, 87, 91, 93, and 95.