Indefinite Series, Perfect Squares

Date: 01/01/98 at 15:54:23
From: Connie
Subject: Indefinite series/perfect squares.

A table consists of eleven columns. Reading across the first row of 
the table, we find the numbers 1991, 1992, 1993, .... 2000, 2001. In 
the other rows, each entry in the table is 13 greater than the entry 
above it, and the table continues indefinitely. What is the number of 
columns containing at least one perfect square?

I've tried approaching this question by finding the equation for the 
nth term for all of the columns, but that just adds to the confusion.

Can you pleases help me solve this?

Connie

Date: 01/08/98 at 10:01:41
From: Doctor Nick
Subject: Re: Indefinite series/perfect squares.

Hi Connie - interesting question!

What it all boils down to is: if you have a perfect square, and divide 
it by 13, what can the remainder be? 

To answer this, use the fact that every integer n can be written as 

   n = 13 a + b, 

where a and b are integers, and 0 <= b <= 12. That is, b is the 
remainder you get when you divide n by 13.

Then, n squared is

   n^2 = (13 a + b)^2 =   169 a + 26 b + b^2.

Now, if we divide n^2 by 13, we get

   13 a + 2 b + (b^2)/13.

Since 13 a + 2 b is a whole number, we can tell that the remainder we 
get when we divide n^2 by 13 is the same as the remainder we get when 
we divide b^2 by 13.  Now we can make the following table:

   b   remainder when b^2 is divided by 13

   0      0
   1      1
   2      4
   3      9
   4      3
   5     12
   6     10
   7     10
   8     12
   9      3
  10      9
  11      4
  12      1

This tells us a lot: a perfect square must have a remainder of 
0,1,3,4,9,10, or 12 when divided by 13. That means that if a number 
gives a remainder of 2,5,6,7,8, or 11 when divided by 13, then it's
not a perfect square. 

Now, all of the numbers in the first column give a remainder of 2 when 
divided by 13: 1991 = 153*13+2, 2004 = 1991+13 = 154*13+2, etc.  
Therefore, none of the numbers in the first column can be perfect
squares!

The next column under 1992 is different. The remainder you get when 
you divide 1992 by 13 is 3, so this column might contain perfect 
squares. Looking at the table above, we can see that perfect squares 
that give a remainder of 3 when divided by 13 are squares of numbers 
that give a  remainder of 3 or 9 when divided by 13.  

Now, the square root of 1992 is about 44; the next bigger number that 
gives 4 or 9 as its remainder is 48; 48 squared is 2304; and so 2304 
is a perfect square in the second column (one way to recheck that it's 
in the second column is to check that 2304-1992 is a multiple of 13).

Now continue for the rest of the columns: either eliminate them for 
having a remainder other than 0,1,3,4,9,10, or 12 when divided by 13, 
or find a square in the column.

This is definitely a sophisticated question. Remember to have fun with 
it, and write back if you need more info. You could also look in a 
library for books on number theory.  Look up "modular arithmetic"
and "congruences" to find more on the method we used here.

-Doctor Nick,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/