Mock AIME 4 2006-2007 Problems/Problem 6
Contents
[hide]Problem
For how many positive integers does there exist a regular -sided polygon such that the number of diagonals is a nonzero perfect square?
Solution
The formula for the number of diagonals of a convex n-gon is . We need to count the for which this is a perfect square.
The numbers and are either relatively prime, or their greatest common divisor is . We will handle each case separately.
Case 1: relatively prime
If they are relatively prime, we know the following things:
- neither of them is divisible by
- one of them is an odd perfect square
- the other is twice a perfect square
One possible way of handling this case would be to try all odd perfect squares less than , there are just of them. We will show an alternate approach.
The one that is the odd perfect square not divisible by is of the form . The other one is either larger or smaller by .
, hence the number that is larger is divisible by and not by , and thus it can not be twice a perfect square.
, thus . This means that half the smaller number can not be a perfect square, as perfect squares give only the remainders and modulo .
Thus in this case there are no solutions.
Case 2: both are divisible by 3
Let , then . We now want to count all for which is a perfect square. Once again we can make a similar observation about and :
- one of them is an odd perfect square
- the other is twice a perfect square
There are nine odd perfect squares less than . Trying each of them as either or , we find the following solutions: , giving .