I recently went to see the film x+y, which is really about autism, but centred on an autistic teenager who enters the Mathematical Olympiad, an international competition for high school students.

It’s a mass-market film, well done, so the maths is skimmed over lightly. At one point the storyline presents a problem clearly enough that the viewer can remember it. Are there infinitely many positive whole numbers m and n such that m divides n^{2}+1 and n divides m^{2}+1? Or, using the symbol | for “divides”, are there infinitely many positive whole numbers m and n such that m|n^{2}+1 and n|m^{2}+1?

I tried to solve the problem after coming home; failed; had to look it up; felt bad about failing. There are lessons from my failure.

I got stuck on trying to prove that there are *not* infinitely many such m and n. Since there are in fact infinitely many, no wonder I failed. Lesson one: if a problem looks intractable, turn it round. Try proving the opposite.

Lesson two: with a problem like this, check out simple cases more thoroughly. I saw that (1,2) and (2,5) fit the requirement. Then I couldn’t think of any more. But only a little mental arithmetic would have told me that (5,13) fits too.

Those three cases are enough to suggest a pattern.

Let n_{1}=the number of times n divides into m^{2}+1, and m_{1}=the number of times m divides into n^{2}+1

If m=1 and n= 2, then m_{1}= 5 and n_{1}=1

If m=2 and n= 5, then m_{1}=13 and n_{1}=1

If m=5 and n=13, then m_{1}=34 and n_{1}=2

Each case (m,n) seems to generate the next as (n,m_{1})

Does the pattern continue? (13,34) works; and so does the pair generated from that one, (34,89)

Can we *prove* the pattern continues? If so, then we’ve proved there are infinitely many (m,n)

m_{1}m=(a multiple of n)+1

Therefore

m_{1}^{2}m^{2}=(a multiple of n)+1

m_{1}^{2}(m^{2}+1)−m_{1}^{2}=(a multiple of n)+1

But (m^{2}+1) is a multiple of n, so

−m_{1}^{2}=(a multiple of n)+1

and so

m_{1}^{2}+1=(a multiple of n)

In other words, n|(m_{1}^{2}+1); and of course, also, m_{1}|(n^{2}+1)

Therefore the pattern continues, therefore there are infinitely many (m,n) ▇

[Here I’ve simplified the proof I found by looking up].

This argument also shows us that the pattern (1,2), (2,5), (5,13), (13,34), (34,89), etc. contains *all* the valid cases (m,n), or at least it does if we add one other “starting” pair, (1,1).

Each case (m,n) also generates the *previous* one as (n_{1},m). And if m≤n (we’ve assumed we write the pairs that way round), then n_{1}<m, unless m=n, in which case both m and n are 1.

Therefore every valid case (m,n) works back to (1,1); and every valid case is in the pattern starting from (1,1) and working forward. ▇

The numbers in the pattern are called Fibonacci numbers. More precisely, each valid pair (m,n) comprises an odd-numbered element of the Fibonacci series and the next odd-numbered element:

**1**, 1, **2**, 3, **5**, 8, **13**, 21, **34**, 55, **89**, 144, **233**, 377….

The series itself is defined by the rule that each element=the two elements before it added together

or F_{n}=F_{n−1}+F_{n−2}

There is a general rule for the Fibonacci series

F_{n}^{2}−F_{n+2}.F_{n−2}=−1 if n is odd, +1 if n is even

e.g. the square of 2(third Fibonacci number)=1(first Fibonacci number)×5(fifth Fibonacci number)−1

and the square of 3(fourth Fibonacci number=1(second Fibonacci number)×8(sixth Fibonacci number)+1

We can prove this by a bit of matrix algebra:

And so:

if n is odd F_{n} | F_{n+2}^{2}+1 and F_{n+2} | F_{n}^{2}+1

All the pairs (m,n) of *even*-numbered elements of the Fibonacci series with the next even-numbered element, e.g. (1,3), (3,8), (8,21), etc. have m|n^{2}−1 and n|m^{2}−1. There are more pairs than the Fibonacci ones in this case, because 1^{2}−1=0; and so (1,n) fits the requirements for *any* n. The new (m,n) pairs generated from (1,1), (1,2), (1,4), (1,5) and so on also fit the requirements.

For any whole number a>0, the pairs (m,n) such that m|n^{2}+a and n|m^{2}+a comprise:

(a+1,[a+1]^{2}+a) and all the pairs got from that by the process by which (m,n) generates (n,m_{1}) as the next pair, as described above for a=1.

([a+1]^{2}+a)^{2}+a=(multiple of [a+1])+a^{2}+a, and so is divisible by a+1.

Thus (3,11), (11,41), (41,153)… are the pairs for a=2

(4,19), (19,91), (91,436)… are the pairs for a=3

and so on.