Senior Mentoring – Solving equations in integers

At school, we learn how to solve equations like . Sometimes the answer is an integer (that is, a whole number), sometimes it isn’t. If we change that -5 to a -6, the solution to the equation above won’t be an integer any more. What is more, if we change the 5 to , the solution won’t even be rational (that is, a normal fraction that looks like ). But, the key point is that in the introduction to the chapter on linear equations, or whatever they call it, in a textbook, there will be an explanation of how to solve this generic class of problems, which will work whether the numbers in the equation are integers, fractions, or even complex numbers!

Later, we move on to quadratic equations. Spotting factorisations is a good way to get started, then you could learn the quadratic formula to use in those cases where the factors are harder to spot. Alternatively, there’s the method of ‘completing the square’, which takes more steps, but means you can do the arithmetic in clear stages. Then, if you think about why the quadratic formula works, you realise that you are just completing the square for all quadratics (using a, b, c in place of any numerical coefficients). In other words, though there are a few different ways of approaching the problem, the sensible methods are essentially the same. And then you might get problems about logarithms or matrices for which you use your new knowledge about these objects to turn the question into a quadratic equation, say. At all times, there’s an implicit assumption that any question can be turned into an equation which you ‘know how to solve’.

So when you first come across a problem which asks you to find integer solutions to an equation, as have appeared a few times on this year’s Senior Mentoring scheme, it is hard to know where to start. You could try to solve it as if it wasn’t about integers, then select the integer solutions at the end. But this could be difficult, or might not even make sense. You might have a condition that x is odd: what does this mean if x isn’t even an integer? You also often start making sensible-looking substitutions: x is odd, so write x=2n+1 for some n which is also an integer, then work with n. But this can sometimes cause you to end with a huge number of variables which you can’t really relate to, and horribly complicated expressions.

As with so much of maths, experience is very useful. If you’ve seen solutions to twenty moderately tricky integer equations, you’ll have more ideas about how to think about starting another problem. So here are a few tricks that might come in handy.

Smallest solution: Are you stuck trying to prove there aren’t any solutions? Do all your substitutions just give more complicated versions of the original equation? What about considering the smallest solution? You might have to be careful about what you mean by ‘small’, but suppose you consider the smallest solution x, and end up finding a smaller solution x'<x. What could this mean? Well it can only mean that there isn’t a smallest solution! In other words, there are no solutions. You should think about why the fact that we are working with integers means that if there is any solution there must be a smallest one. Then see if you can find all solutions in positive (>0) integers to .

Divisibility: You can get a lot of information from looking at divisors. Which integers divide 64? What integers divide where p is a prime. And this applies whether the factors are integers, or algebraic expressions.

Modulo Arithmetic: Are there solutions in integers to ? Look at the equation carefully. The left hand side is always odd, while the right hand side is always even. So no, there can’t be any solutions. This idea works in more complicated situations too. ‘Odd’ or ‘even’ tells us what the remainder is when we divide by 2. But we can also consider the remainders when we divide by other integers. This is called modulo arithmetic (or clock arithmetic), and has lots of nice properties, like the fact that it is easy to calculate remainders under multiplication. For example, how would you go about finding the remainder when is divided by 7? Do you need to perform an enormous long division, or can you take some shortcuts? I will write a bit more about modulo arithmetic at another time, but an excellent example is to take the squares 1,4,9,16,… and look at the remainders obtained when we divide these by 4. Is this useful? Try to find all solutions to .

Sandwiching: Integer equations often involve squares and we’ll be trying to show that there aren’t many solutions apart from perhaps a few small ones. It can be good to consider how close together squares can be. Which perfect squares are next to ? So how many solutions are there to ? And you can make similar deductions for powers of two for example. If I tell you that I have two powers of two and their difference is 8, you can probably tell me what they are.

To put some of the ideas into practice, let’s try two problems from this year’s sheet.

Find all solutions to .

• We have a look at Pascal’s triangle, and suspect that there won’t be too many solutions. For example, if n>120, there certainly aren’t any solutions, but that is still a lot to check. You could check by looking at n, but why not consider r?
• We know is a necessary condition. But can we do better? Remember that , so the solutions will by and large come in pairs, with the same n, but values of r reflected in n/2. So we may assume that . Suddenly this is quite a useful bound.
• For example, if , therefore , and similarly for larger r. So we only need to check r=1,2,3,4.
• For each of these cases, it is not too hard to find all the suitable n. Then, remembering that we need the symmetric copies too, the solutions are: (n,r)=(120,1), (120,119), (16,2), (16,14), (10,3), (10,7),.

Find all solutions to .

• Note the solution (m,n)=(1,1). For larger n, the power of two is divisible by 4. Checking modulo 4, we realise that we need m to be even. But then is a difference of two squares. Write a=m/2.
• So . Is this progress? What can we say about the two factors on the right hand side?
• They need to be powers of two, since the only divisors of a power of two are other powers of two. (Why?) But what is the relationship between the factors, and how does this enable us to identify all the solutions to the problem?

Advertisement