You are currently browsing the tag archive for the ‘number theory’ tag.

**Have you got a Super Brain?**

Adapting and exploring maths challenge problems is an excellent way of finding ideas for IB maths explorations and extended essays. This problem is taken from the book: The first 25 years of the Superbrain challenges. I’m going to see how many different ways I can solve it.

The problem is to find all the integer solutions to the equation above. Finding only integer solutions is a fundamental part of number theory – a branch of mathematics that only deals with integers.

**Method number 1: Brute force**

This is a problem that computers can make short work of. Above I wrote a very simple Python program which checked all values of x and y between -99 and 99. This returned the only solution pairs as:

Clearly we have not proved these are the only solutions – but even by modifying the code to check more numbers, no more pairs were found.

**Method number 2: Solving a linear equation**

We can notice that the equation is linear in terms of y, and so rearrange to make y the subject.

We can then use either polynomial long division or the method of partial fractions to rewrite this. I’ll use partial fractions. The general form for this fraction can be written as follows:

Next I multiply by the denominator and the compare coefficients of terms.

This therefore gives:

I can now see that there will only be an integer solution for y when the denominator of the fraction is a factor of 6. This then gives (ignoring non integer solutions):

I can then substitute these back to find my y values, which give me the same 4 coordinate pairs as before:

**Method number 3: Solving a quadratic equation**

I start by making a quadratic in x:

I can then use the quadratic formula to find solutions:

Which I can simplify to give:

Next I can note that x will only be an integer solution if the expression inside the square root is a square number. Therefore I have:

Next I can solve a new quadratic as follows:

As before I notice that the expression inside my square root must be a square number. Now I can see that I need to find m and n such that I have 2 square numbers with a difference of 24. I can look at the first 13 square numbers to see that from the 12th and 13th square numbers onwards there will also be a difference of more than 24. Checking this list I can find that m = 1 and m = 5 will satisfy this equation.

This then gives:

which when I solve for integer solutions and then sub back into find x gives the same four solutions:

**Method number 4: Graphical understanding**

Without rearranging I could imagine this as a 3D problem by plotting the 2 equations:

This gives the following graph:

We can see that the plane intersects the curve in infinite places. I’ve marked A, B on the graph to illustrate 2 of the coordinate pairs which we have found. This is a nice visualization but doesn’t help find our coordinates, so lets switch to 2D.

In 2D we can use our rearranged equation:

This gives the following graph:

Here I have marked on the solution pairs that we found. The oblique asymptote (red) is y = 2x-1 because as x gets large the fraction gets very small and so the graph gets closer and closer to y = 2x -1.

All points on this curve are solutions to the equation – but we can see that the only integer solution pairs will be when x is small. When x is a large integer then the curve will be close to the asymptote and hence will return a number slightly bigger than an integer.

So, using this approach we would check all possible integer solutions when x is small, and again should be able to arrive at our coordinate pairs.

So, 4 different approaches that would be able to solve this problem. Can you find any others?

**Further investigation of the Mordell Equation**

This post carries on from the previous post on the Mordell Equation – so make sure you read that one first – otherwise this may not make much sense. The man pictured above (cite: Wikipedia) is Louis Mordell who studied the equations we are looking at today (and which now bear his name).

In the previous post I looked at solutions to the difference between a cube and a square giving an answer of 2. This time I’ll try to generalise to the difference between a cube and a square giving an answer of k. I’ll start with the same method as from the previous post:

In the last 2 lines we outline the 2 possibilities, either b = 1 or b = -1. First let’s see what happens when b = 1:

This will only provide an integer solution for a if we have:

Which generates the following first few values for k when we run through m = 1, 2,3..:

k = 2, 11, 26, 47

We follow the same method for b = -1 and get the following:

Which generates the following first few values for k when we run through m = 1, 2,3…:

k = 4, 13, 28, 49

These are the values of k which we will be able to generate solutions to. Following the same method as in the previous post this generates the following solutions:

Let’s illustrate one of these results graphically. If we take the solutions for k = 13, which are (17,70) and (17,-70), these points should be on the curve x cubed – y squared = 13.

This is indeed the case. This graph also demonstrates how all solutions to these curves will have symmetrical solutions (e, f) and (e, -f).

We can run a quick computer program to show that this method does not find all the solutions for the given values of k, but it does ensure solutions will be found for the k values in these lists.

In the code solutions above, results are listed k, x, y, x cubed, y squared. We can see for example that in the case of k = 11 our method did not find the solution x = 3 and y = 4 (though we found x = 15 and y = 58). So, using this method we now have a way of finding *some* solutions for *some* values of k – we’ve not cracked the general case, but we have at least made a start!

**The Mordell Equation [Fermat’s proof]**

Let’s have a look at a special case of the Mordell Equation, which looks at the difference between an integer cube and an integer square. In this case we want to find all the integers x,y such that the difference between the cube and the square gives 2. These sorts of problems are called Diophantine problems and have been studied by mathematicians for around 2000 years. We want to find integer solution to:

First we can rearrange and factorise, using the property of imaginary numbers.

Next we define alpha and beta such that:

For completeness we can say that alpha and beta are part of an algebraic number field:

Next we use an extension of the Coprime Power Trick, which ensures that the following 2 equations have solutions (if our original equation also has a solution). Therefore we define:

We can then substitute our definition for alpha into the first equation directly above and expand:

Next we equate real and imaginary coefficients to give:

This last equation therefore requires that either one of the following equations must be true:

If we take the case when b = 1 we get:

If we take the case when b = -1 we get

Therefore our solution set is (a,b): (1,1), (1,-1), (-1,1), (-1,-1. We substitute these possible answers into our definition for y to give the following:

We can then substitute these 2 values for y into the definition for x to get:

These therefore are the only solutions to our original equation. We can check they both work:

We can see this result illustrated graphically by plotting the graph:

and then seeing that we have our integer solutions (3,5) and (3,-5) as coordinate on this curve.

This curve also clearly illustrates why we have a symmetrical set of solutions, as our graph is symmetrical about the x axis.

This particular proof was first derived by Fermat (of Fermat’s Last Theorem fame) in the 1600s and is an elegant example of a proof in number theory. You can read more about the Mordell Equation in this paper (the proof above is based on that given in the paper, but there is a small mistake in factorization so that y = 7 and y = -7 is erroneously obtained)

**Square Triangular Numbers**

Square triangular numbers are numbers which are both square numbers and also triangular numbers – i.e they can be arranged in a square or a triangle. The picture above (source: wikipedia) shows that 36 is both a square number and also a triangular number. The question is how many other square triangular numbers we can find?

The equation we are trying to solve is:

a^{2} = 0.5(b^{2}+b)

for some a, b as positive integers. The LHS is the formula to generate square numbers and the RHS is the formula to generate the triangular numbers.

We can start with some simple Python code (which you can run here):

```
```for c in range(1,10001):

for d in range(1,10001):

if c**2 == (d**2+d)/2:

print(c**2, c,d)

This checks the first 10000 square numbers and the first 10000 triangular numbers and returns the following:

1 1 1

36 6 8

1225 35 49

41616 204 288

1413721 1189 1681

48024900 6930 9800

i.e 1225 is the next square triangular number after 36, and can be formed as 35^{2} or as 0.5(49^{2}+49). We can see that there are very few square triangular numbers to be found in the first 50 million numbers. The largest we found was 48,024,900 which is made by 6930^{2} or as 0.5(9800^{2}+9800).

We can notice that the ratio between each consecutive pair of square triangular numbers looks like it converges as it gives:

36/1 = 36

1225/36 = 34.027778

41616/1225 = 33.972245

1413721/41616 = 33.970612

48024900/1413721 = 33.970564

So, let’s use this to predict that the next square triangular number will be around

48024900 x 33.9706 = 1,631,434,668.

If we square root this answer we get approximately 40391

If we solve 0.5(b^{2}+b) = 1,631,434,668 using Wolfram we get approximately 57120.

Therefore let’s amend our code to look in this region:

```
```for c in range(40380,40400):

for d in range(57100,57130):

if c**2 == (d**2+d)/2:

print(c**2, c,d)

This very quickly finds the next solution as:

1631432881 40391 57121

This is indeed 40391^{2} – so our approximation was very accurate. We can see that this also gives a ratio of 1631432881/48024900 = 33.97056279 which we can then use to predict that the next term will be 33.970563 x 1631432881 = 55,420,693,460. Square rooting this gives a prediction that we will use the 235,416 square number. 235,416^{2} gives 55,420,693,056 (using Wolfram Alpha) and this is indeed the next square triangular number.

So, using a mixture of computer code and some pattern exploration we have found a method for finding the next square triangular numbers. Clearly we will quickly get some very large numbers – but as long as we have the computational power, this method should continue to work.

**Using number theory**

The ever industrious Euler actually found a formula for square triangular numbers in 1778 – a very long time before computers and calculators, so let’s have a look at his method:

We start with the initial problem, and our initial goal is to rearrange it into the following form:

Next we make a substitution:

Here, when we get to the equation 1 = x^{2} – 2y^{2} we have arrived at a Pell Equation (hence the rearrangement to get to this point). This particular Pell Equation has the solution quoted above where we can define P_{k} as

Therefore we have

Therefore for any given k we can find the kth square triangular number. The a value will give us the square number required and the b value will give us the triangular number required. For example with k = 3:

This tells us the 3rd square triangular number is the 35th square number or the 49th triangular number. Both these give us an answer of 1225 – which checking back from our table is the correct answer.

So, we have arrived at 2 possible methods for finding the square triangular numbers – one using modern computational power, and one using the skills of 18th century number theory.

**Ramanujan’s Taxi Cabs and the Sum of 2 Cubes **

The Indian mathematician Ramanujan (picture cite: Wikipedia) is renowned as one of great self-taught mathematical prodigies. His correspondence with the renowned mathematician G. H Hardy led him to being invited to study in England, though whilst there he fell sick. Visiting him in hospital, Hardy remarked that the taxi that had brought him to the hospital had a very “rather dull number” – number 1729. Ramanujan remarked in reply, ” No Hardy, it’s a very interesting number! It’s the smallest number expressible as the sum of 2 cubes in 2 different ways!”

Ramanujan was profoundly interested in number theory – the study of integers and patterns inherent within them. The general problem referenced above is finding integer solutions to the below equation for given values of A:

In the case that A = 1729, we have 2 possible ways of finding distinct integer solutions:

The smallest number which can be formed through 3 distinct (positive) integer solutions to the equation is A = 87, 539, 319.

Although this began as a number theory problem it has close links with both graphs and group theory – and it is from these fields that mathematicians have gained a deeper understanding as to the nature of its solutions. The modern field of elliptical curve cryptography is closely related to the ideas below and provides a very secure method of encrypting data.

We start by sketching the graph of:

For some given integer value of A. We will notice that the graph has a line of symmetry around y = x and also an asymptote at y = -x. If we plot:

We can see that both our integer solutions to this problem (1,12) and (9,10) lie on the curve:

**Group theory**

Groups can be considered as sets which follow a set number of rules with regards to operations like multiplication, addition etc. Establishing that a set is a group then allows certain properties to be inferred. If we can establish the following rules hold then we can create an Abelian group. If we start with a set A and and operation Θ.

1) **Identity.** For an element e in A, we have a Θ e = a for all a in A.

(for example 0 is the identity element for the addition operation for the set of integers numbers. a+0 = a for all a in the real numbers).

2) **Closure**. For all elements a,b in A, a Θ b = c, where c is also in A.

(For example with the addition operation, the addition of 2 integers numbers is still an integer)

3) **Associativity**. For all elements a,b,c in A, (a Θ b) Θ c = a Θ (b Θ c)

(For example with the addition operation, (1+2) + 3 = 1 + (2+3) )

4) **Inverse**. For each a in A there exists a b in A such that a Θ b = b Θ a = e. Where e is the identity.

(For example with the addition operation, 4+-4 = -4+4 = 0. 0 is the identity element for addition)

5) **Commutativity**. For all elements a,b in A, a Θ b = b Θ a

(For example with the addition operation 1+2 = 2+1).

As we have seen, the set of integers under the operation addition forms an abelian group.

**Establishing a group**

So, let’s see if we can establish a Abelian group based around the rational coordinates on our graph. We can demonstrate with the graph:

We then take 2 coordinate points with rational coordinates (i.e coordinates that can be written as a fraction of integers). In this case A (1,12) and B (9,10).

We then draw the line through A and B. This will intersect the graph in a 3rd point, C (except in a special case to be looked at in a minute).

We then reflect this new point C in the line y = x, giving us C’.

In this case C’ is the point (46/3, -37/3)

We therefore define *addition* (our operation Θ) in this group as:

A + B = C’.

(1,12) + (9,10) = (46/3, -37/3).

We now need to deal with the special case when a line joining 2 points on the curve does not intersect the curve again. This will happen whenever the gradient of this line is -1, which will make it parallel to the graph’s asymptote y = -x.

In this case we affix a special point at infinity to the Cartesian (x,y) plane. We define this point as the point through which all lines with gradient -1 intersect. Therefore in our expanded geometry, the line through AB *will* intersect the curve at this point at infinity. Let’s call our special point Φ. Now we have a new geometry, the (x,y) plane affixed with Φ.

We can now create an Abelian group. For any 2 rational points P(x,y), Q(x,y) we will have:

1) **Identity.** P + Φ = Φ + P = P

2) **Closure**. P + Q = R. (Where R(x,y) is also a rational point on the curve)

3) **Associativity**. (P+Q) + R = P+(Q+R)

4) **Inverse**. P + (-P) = Φ

5) **Commutativity**. P+Q = Q+P

**Understanding the identity**

Let’s see if we can understand some of these. For the identity, if we have a point A on the line and the point at infinity then this will contain the line with gradient -1. Therefore the line between the point at infinity and A will intersect the curve again at B. Our new point, B’ will be created by reflecting this point in the line y = x. This gets us back to point A. Therefore P + Φ = P as required.

**Understanding the inverse**

With the inverse of our point P(x,y) given as -P = (-x,-y) we can see that this is the reflection in the line y = x. We can see that we we join up the 2 points reflected in the line y = x we will have a line with slope -1, which will intersect with the curve at our point at infinity. Therefore P + (-P) = Φ.

Through our graphical understanding the commutativity rule also follows immediately, It doesn’t matter which of the 2 points come first when we draw a line that connects them, therefore P+Q = Q+P.

**Understanding associativity and closure**

Neither associativity nor closure are obvious from our graph. We could check individual points to show that (P+Q) + R = P+(Q+R), but it would be harder to explain why this always held. Equally whilst it’s clear that P+Q will always create a point on the curve it’s not obvious that this will be a *rational* point.

In fact we do have both associativity and closure for our group as we have the following algebraic definition for our addition operation:

The addition of 2 points is given by:

In the case of our curve:

If we take P = (1,12). P + P will be given by:

We can check this result graphically. If P and Q are the same point, then the line that passes through both P and Q has to be the tangent to the curve at that point. Therefore we would have:

Here the tangent at A does indeed meet the curve again – at point C, which does reflect in y = x to give us the coordinates above.

We could also find this intersection point algebraically. If we differentiate the original curve to find the gradient when x = 1 we can find the equation of the tangent when x=1 and then substitute this back into the equation of the curve to find the intersection point. This would give us:

We would then reverse the x and y coordinates to reflect in the line y = x. This also gives us the same coordinates.

More generally if we have the 2 rational coordinates on the curve:

We have the algebraic formula for addition as:

If P = (1,12) and Q = (9,10), P + Q would give (after much tedious substitution!):

This agrees with the coordinates we found earlier using the much easier geometrical approach. As we can see from this formula, both coordinate points will always be rational – as they will be composed of combinations of our original rational coordinates. For any given curve there will be a generator set of coordinates through which we can generate all other rational coordinates on the curve through our addition operation.

So, we seem to have come a long way from our original goal – finding integer solutions to an algebraic equation. Instead we seem to have got sidetracked into studying graphs and establishing groups. However by reinterpreting this problem as one in group theory then this then opens up many new mathematical techniques to help us understand the solutions to this problem.

A fuller introduction to this topic is the very readable, “Taxicabs and the Sum of Two Cubes” by Joseph Silverman (from which the 2 general equations were taken) .

**Project Euler: Coding to Solve Maths Problems**

Project Euler, named after one of the greatest mathematicians of all time, has been designed to bring together the twin disciplines of mathematics and coding. Computers are now become ever more integral in the field of mathematics – and now creative coding can be a method of solving mathematics problems just as much as creative mathematics has always been.

The first problem on the Project Euler Page is as follows:

*If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.*

*Find the sum of all the multiples of 3 or 5 below 1000.*

This is a reasonably straight forward maths problem which we can solve using the summation of arithmetic sequences (I’ll solve it below!) but more interestingly is how a computer code can be written to solve this same problem. Given that I am something of a coding novice, I went to the Project Nayuki website which has an archive of solutions. Here is a slightly modified version of the solution given on Project Nayki, designed to run in JAVA:

The original file can be copied from here, I then pasted this into an online JAVA site jdoodle. The only modification necessary was to replace:

*public final class p001 implements EulerSolution* with *public class p001*

Then after hitting execute you get the following result:

i.e the solution is returned as 233,168. Amazing!

But before we get carried away, let’s check the answer using some more old fashioned maths. We can break down the question into simply trying to find the sum of multiples of 3 under 1000, the sum of the multiples of 5 under 1000 and then subtracting the multiples of 15 under 1000 (as these will have been double counted). i.e:

(3 + 6 + 9 + … 999) + (5 + 10 + 15 + … 995) – (15 + 30 + 45 + …990)

This gives:

S_333 = 333/2 (2(3)+ 332(3)) = 166,833

+

S_199 = 199/2 (2(5) + 198(5)) = 99, 500

–

S_66 = 66/2 (2(15) +65(15) = 33, 165.

166,833 + 99, 500 – 33, 165 = 233, 168 as required.

Now that we have seen that this works we can modify the original code. For example if we replace:

if (i % 3 == 0 || i % 3 == 0)

with

if (i % 5 == 0 || i % 7 == 0)

This will find the sum of all the multiples of 5 or 7 below 1000. Which returns the answer 156,361.

Replacing the same line with:

if (i % 5 == 0 || i % 7 == 0 || i % 3 == 0)

will find the sum of all the multiples of 3 or 5 or 7 below 1000, which returns the answer 271,066. To find this using the previous method we would have to do:

Sum of 3s + Sum of 5s – Sum of 15s + Sum of 7s – Sum of 21s – Sum 35s – Sum of 105s. Which starts to show why using a computer makes life easier.

This would be a nice addition to any investigation on Number Theory – or indeed a good project for anyone interested in Computer Science as a possible future career.