Learning from failure

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.

X-Y

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 n2+1 and n divides m2+1? Or, using the symbol | for “divides”, are there infinitely many positive whole numbers m and n such that m|n2+1 and n|m2+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 n1=the number of times n divides into m2+1, and m1=the number of times m divides into n2+1

If m=1 and n= 2, then m1= 5 and n1=1
If m=2 and n= 5, then m1=13 and n1=1
If m=5 and n=13, then m1=34 and n1=2

Each case (m,n) seems to generate the next as (n,m1)

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)

m1m=(a multiple of n)+1
Therefore
m12m2=(a multiple of n)+1
m12(m2+1)−m12=(a multiple of n)+1
But (m2+1) is a multiple of n, so
−m12=(a multiple of n)+1
and so
m12+1=(a multiple of n)
In other words, n|(m12+1); and of course, also, m1|(n2+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 (n1,m). And if m≤n (we’ve assumed we write the pairs that way round), then n1<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….

fibonacci-spiral

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

or Fn=Fn−1+Fn−2

There is a general rule for the Fibonacci series

Fn2−Fn+2.Fn−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:

fibon-matrix

And so:

if n is odd Fn | Fn+22+1 and Fn+2 | Fn2+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|n2−1 and n|m2−1. There are more pairs than the Fibonacci ones in this case, because 12−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|n2+a and n|m2+a comprise:

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

([a+1]2+a)2+a=(multiple of [a+1])+a2+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.