HS Math Meet Quadratic Form Problem

fibept, "IRC nick", worked the following problem at a high school math team meet:
Find the smallest positive integer solution to 3 n² - 37 m² = -1

m=1 is not a solution but m=2 gives n=7 which is a solution. In this case guessing works right away. landen, "IRC nick", wrote up the following which shows how to find any solution of this equation. The write-up tries to avoid using number theory which a HS student is unlikely to know.

Sometimes Problems Like These Have No Solutions

3 n² - 37 m² = 2 has no solutions

It is surprisingly easy to show this has no solutions and the methods used in the steps are common in other problems. We will show that no combination of having m and n be odd or even can work. Therefore, the assumption of having solutions leads to a contradiction.

If either m or n is even, both are even. One number even and one odd is impossible.
Proof: If m is even then 2 | 3 n² ("|" means "divides") so n is even too. If is n is even then 2 | 37*m² and m is even too. This proves only the cases "both even" or "both odd" are possible.
m and n cannot both be even.
Proof: If they were both even, 4 |(3 n² - 37 m²) which means 4 | 2 which is impossible.
Notice that the square of an odd number is 1 more than a multiple of 8. This little fact turns up a lot. It is left as an exercise. Hint: All odd numbers must be of the form 4 k+1 or 4 k+3.
Only the case "both odd" is left. Both numbers odd is also impossible. Proof:
Let n² = 8 r+1 and m² = 8 s+1. 3 *( 8 r+1) - 37 (8 s+1) = 2 or 8 (3 r -37 s) = 36 but this implies 8 | 36 which is false.
So, there are no solutions.

Discussion of the Proof of No Solutions

One of the ways of proving that an equation in integers has no solutions is to separate all solutions into a finite number of classes. Then prove that the theorem is impossible for each of the classes. In this case the classes were: one even and one odd, both even, and both odd. Then for each class we get to use special properties of the members of the class. In the both odd case the property that the square of an odd number is 1 more than a multiple of 8 was used. To use this fact requires you to know in advance this famous property of odd squares. It is not enough to be able just to prove this property of odd squares. You need to be familiar in advance so you can steer the proof toward using it.

If you know "mod arithmetic" you can get your computer to try to prove there is no solution. If there is a solution at all, then there is a solution mod every integer. So just take some moduli, r = 2,3,4,5 etc., and try all possible values of m and n for each modulus r. If you find even one r for which there is no solution then you have proved that there are no integer solutions. Not surprisingly, working (mod 8), shows 3 n² - 37 m² = 2 has no solution.

This Problem Has Infinitely Many Integer Solutions

3 n² - 37 m² = -1   has the solution n = 7; ma = 2 which is easy to find by searching. We can rewrite the equation as:

m = sqrt(( 3 n² + 1) / 37)

Since the expression inside the sqrt is positive, we have a real number value for m for any positive n. An obvious question is whether m can be an integer for integer values of n besides 7. We can show that this particular equation has an infinite number of integer solutions in a simple pattern. Write the first solution with this notation:

p₀ = [7, 2] = [n₀, m₀]   with n₀ = 7 and m₀ = 2.
p_k = [n_k, m_k]   means the kth solution to our equation, using this notation.

In problems of this type the numbers involved get real big real fast, so I used a computer to try values of n and then check if m is an integer. This lead to the next smallest solution:

p₁ = [4137, 1178]   and we can check that 3*4137² - 37*1178² = -1

A powerful idea for solving problems is the concept of recurrence, recurrence means getting a new solution by mathematical operations on old ones. In this case we can compute a new solution p_k+1 from p_k by somehow "guessing", see below, the following linear recurrence formulas:

n_k+1 = 295 n_k + 1036 m_k
m_k+1 = 84 n_k + 295 m_k

As an example we can get p₁ from p₀ as:

n₁ = 295 * 7 + 1036 * 2 = 4137
m₁ = 84 * 7 + 295 * 2 = 1178

We can prove the recurrence above gives new solutions in general by computing:

3 (295 n_k + 1036 m_k)² - 37 (84 n_k + 295 m_k)² =
3 n_k² - 37 m_k² = -1

How to Guess Recurrence Solutions

Suppose we want to find r,s,u, and v to make the following recurrences give new solutions.

n_k+1 = r n_k + s m_k
m_k+1 = u n_k + v m_k

We can substitute the expressions for the new solutions into our equation and then try to get some constraints on r,s,u, and v. The following should be true:
3 (r n_k + s m_k)² - 37 (u n_k + v m_k)² =
(3 r² - 37 u²)n_k² + (3 s² - 37 v²)m_k² + (6 rs - 74uv)n_km_k = -1

We want the coefficients of n_k², m_k², and n_km_k to be 3, -37, and 0, respectively, so:

3 r² - 37 u² = 3
3 s² - 37 v² = -37
6 rs - 74uv = 0
Now we get a piece of luck. 37 u² = 3 r² -3 implies 3 | u. A similar argument says 37 | s. So we can define new variables, u' and s', so that u = 3u', and s = 37s'

r² - 111 u'² = 1
v² - 111 s'² = 1
rs' - u'v = 0

Now we can pick v = r and s' = u' and all we need is a solution to:

r² - 111 u'² = 1
We get our computer to try values and it finds: 295² - 111*28² = 1. So:
r = 295, s = 1036, u = 84, v = 295 are numbers that can be used for a recurrence.

We Can Run the Recurrence Backward Too

We can also take the recurrence equations and solve for the smaller numbers, n_k and m_k, in terms of n_k+1 and m_k+1. This is the resulting backward or descending recurrence:

n_k = 295 n_k+1 - 1036 m_k+1
m_k = -84 n_k+1 + 295 m_k+1

Since this result has to give integer answers, the determinant of the coefficients of the recurrence equations has to be 1. We divide by the determinant in solving the equations for the backward case. Notice that 295² - 84*1036 = 1.

But Are There More Solutions?

Our recurrence relation leads to infinitely many solutions but it might not find all positive integer solutions. Using the numbers [174049, 611240; 49560, 174049], instead of [295, 1036; 84, 295], in the recurrence relations leads to the next solution after p₀ = [7,2] being [2440823, 695018]. The solution p₁ = [4137, 1178] is missed. The recurrence with [174049, 611240; 49560, 174049] does generate an infinite number of solutions though. A way to resolve this is to use the backward recurrences to get smaller solutions from a larger one. Suppose there is a big solution that we miss with our recurrence starting at p₀. We could run the backward recurrence starting at any big solution and eventually get a solution between p₀ and p₁ in size. When we find no solutions for x between 7 and 4137, then we know the chain of solutions starting at [7,2] and using the recurrence numbers [295, 1036; 84, 295] will give all solutions.

Since there are infinitely many solutions, we can get ones with big numbers. High precision arithmetic is required. Here are several solutions to: 3 n² - 37 m² = -1 which were computed using PARI-GP and the method above:

p₀ = [7 , 2]

p₁ = [4137, 1178]

p₂ = [2440823, 695018]

p₄ = [849645604647, 241934375762]

p₂₀ = [183168183901089799048455793355239948773846490752959735207,
52156663895155063903713009004972842992229533347630150802]

p₁₀₀ =

[8529256227460311775900793417603008843261135932506976838962787170594516948505
62636158868176112601645816762963907378513852247600033393951022366392415432729
45413008063311398248229184846717207182884722557831824917740638614751837542228
180277330979660372257018408031662371741299476007,

24286835238347250628644322376131853912232361197483042182437237729965212689843
29532929555535913900290876034100009055890020758590800619826566726835269985096
96586002204835419591465850937439142019533832072388226376755517332976996208656
77179050964717762235850747322629402300259554002]

More Discussion of the Proof of Infinitely Many Solutions

There is a powerful general theory of integer solutions to quadratic forms of the type:
a n² - b m² = q, given a and b naturals and q an integer.

Unfortunately, the theory is not covered in a typical introduction to number theory course and requires abstract algebra and linear algebra as background. Fortunately, given an explicit equation you can easily find all the solutions that there are using recurrence techniques. It may not seem elegant to get your computer to find a couple of solutions to 3 n² - 37 m² = -1 using brute force but it took less than 2000 tries using no optimizations (easy to program). Once the recurrence relation is found big solutions are obtained fast. Even p₁₀₀ was printed instantly. There are famous examples such as n² - 61 m² = 1, which has n = 1766319049; m = 226153980 as the smallest solution. With a little more programming you can avoid brute force search and use the chakravala method of Bhaskara II discovered in 1150 C.E. This method uses clever manipulation but does not require advanced math beyond typical HS. The same URL above also discusses the use of continued fractions to solve these equations. Continued fractions are probably the easiest to program but require more theory (easy) to learn.

Created on ... March 20, 2003