Pell's Equation

There was an interesting pure maths problem set by Ian Stewart in the New York Times two days ago linked here. To save you a click, here is the challenge in his own phrasing:

"The Halloween Parade

The students at Frightful High School were excited because today was their favorite school event — the annual Halloween Parade. They were in 10 classes, each containing the same number of young students.

They knew that the number of students in each class was a perfect square, because that’s how their desks were arranged.

On Halloween they always paraded on the playground as 10 separate square arrays, with the students neatly arranged in rows and columns like a square grid. But today there was a difference. The principal told them to form one big square.

“Sir, that’s impossible,” said young Roger.

“Why?” asked the principal.

“Ten isn’t a square, so 10 times a square is never a square,” said Roger. “Unless the square is zero, of course.”

“Very good,” said the principal. “But as a special treat, the Halloween Spirit is joining us, so there will be one more of you.” And he did, and they all formed one big square.

How many students were there in each class? (It was less than 50,000.)"

Ok, back to me writing. That number 50,000 is a bit daunting and suggests that we are looking at some sort of brute force computer based solution. However, after reading around a bit I've come up with a solution (well infinity actually). This is an example of a Diophantine equation, where normally to solve an a set of equations with n variables we need n equations. For example to solve something for both x and y you would expect to has two simultaneous equations. However we are trying to solve 10*x^2 + 1 = y^2, which is only one equation, but it has two variables. But we have an extra request that these numbers should be integer (and, by merit of us talking about a number of students, it must also be a natural number).

The ancient Greeks loved solving Diophantine equations and they had all sorts of geometric arguments for solving them, but most of the general cases are yet to be solved. It is an area of maths that had some significant progress over the last century.

Equations of the form n*x^2 + 1 = y^2 are called Pell's Equation and we know how to find the solutions. The first thing to realise is that if you can find a solution (a,b) then (2ab,b^2+n*a^2) is also a solution (known as Brahmagupta's Lemma); which means that if we can find one, then we can find another. We can repeat this process to get an infinite number of solutions, but so far we don't have a way of generating the first.

Step number 2 is was to notice that if you have have a more general equation with a constant k in place of the 1, n*x^2 + k = y^2, with a solution (a,b) then (2ab,b^2+n*a^2) is another solution to n*x^2 + k^2 = y^2 with a similar argument as before, so by dividing by k^2 we get that (2ab/k,(b^2+n*a^2)/k) is a solution to the original Pell's Equation n*x^2 + 1 = y^2. This all sounds quite complicated and I didn't understand it when I first read it, but don't worry about the details. The plan is to come up with a solution for something close to what we want, then we are going to use that to generate an actual solution. The best thing to understand it is to see an example. Let's try the method:

We want to solve 10*x^2 + 1 = y^2 but there are no obvious solutions. Well let's make it easy for ourselves and try x=1. This gives 10 + 1 = y^2. Well that isn't going to give a nice value for y, so let's pretend that + 1 was a - 1. (In practice, any value which made y an integer would work, so changing the + 1 into a + 6 would also be successful.) So we can see that (1,3) is a solution to the equation 10*x^2 - 1 = y^2 which is almost correct.

But using the formula from above with a = 1, b = 3 and k = -1, we get that the solutions (2ab/k,(b^2+10*a^2)/k) = (2*1*3/-1,(3^2+10*1^2)/-1) = (-6,-19) which works as a solution to our equation. However since the x's and y's are both squared then we can just get rid of the negatives: so each class was a 6x6 square and the overall parade was a 19x19 square.

If we wanted another solution to the equation we can use (6,19) to generate (228,721) which gives a total of 519,840 students plus a ghost, but that is over the 50,000 limit, so is not in the range for the word problem above.

This was us solving it for n = 10, but in practice we can do a similar thing to find solutions to n = whatever we want. Here's a link to the smallest solutions for different values of n. While most values have small solutions, there are some surprises along the way. The idea is that you might not get integer solutions the first time, but if you keep using your rational solutions to generate new ones you will eventually end up with an integer (proven by Legrange). However this can take a long time for some numbers (see 61 in the table).