## Maths challenge 3

Posted by Chris on May 5, 2011 – 5:47 pm

If m = 2 + 2 √(28 n² + 1) is an integer, where n is an integer, then show that m is a perfect square.

NB the convention is that the √ is positive.

I don’t know the solution.

May 6th, 2011 at 2:27 am

Don’t worry Chris – I know how to solve it

May 6th, 2011 at 6:49 am

Hi slavy. I don’t actually know how to solve it in a nice logical way. I have spent five minutes (tops) on it and have found several conditions that must be satisfied (so I got some pleasure from that). However, it’s pretty obvious that the problem is trivial

May 6th, 2011 at 9:08 am

Well … not the formula-savvy guy that you all are.

I did see only two solutions …

n:m:sqrt(m) = 0:4:2

n:m:sqrt(m) = 24:16129:127

.. and I checked n up to 59761 (Excel 2003)

I am curious to see how you guys solve this rather than my sample testing for a fitting solution.

Thanks!

May 6th, 2011 at 9:10 am

Hi Chris. I am not sure that the problem is trivial It is well-known though and I remember dealing with it long time ago when preparing for olympiads. I think there was some beautiful solution but I don’t have time to look for it right now so I just tested the standard semi-brute-force method. It works, the equation has infinitely many solutions and I can even find them explicitly. Hint: mod 2 and mod 7 arythmetic for proving the necessity m to be a perfect sqauare. Then Pell’s equation gives the explicit formula for all the solutions.

May 6th, 2011 at 9:28 am

Hi slavy. I had discovered the mod 7 bit. I’m very pleased to hear that there are infinitely many solutions. That makes the problem a good one IMHO.

PS I concluded trivial after only one coffee. I now realise that I could easily have jumped to a false conclusion. I saw that n = 0 gives one solution, but decided that there could only be one other value that gave a perfect square. I did that independently of my proper analysis (and dependently on a sleeping brain).

Hi cazayoux. Those are the only solutions I know (plus n = -24, but that’s trivial).

May 6th, 2011 at 1:24 pm

Hi slavy. Thanks for mentioning Pell’s equation. I think I’ve heard of it before. I’ve sped read a Wiki and was quite surprised at how much has been done with it.

May 6th, 2011 at 5:54 pm

Hi cazayoux. You have mistake somewhere in your program. When n=24 we have m=256=16^2. The next solution is n=6096 and m=64516=254^2. All these solutions are even written on the wiki page Chris looked at regarding the Pell’s equation. The next one is there, too so who will find it first

May 7th, 2011 at 3:25 am

OK, let me give another hint: Pell’s equation x^2-7y^2=1 has infinitely many solutions and is considered as an example at http://en.wikipedia.org/wiki/Pell%27s_equation The first three solutions are (1,0), (8,3), (127,48). Now, take n=x*y and m=(2*x)^2 and you will see it works for our equation, giving rise to the solutions (n=0, m=4), (n=24, m=256), and (n=6096, m=64516). Every next solution is significantly larger than the previous one, which (as in the Mathematicians problem of Karys) once again proves that computers are not comparable to human brains and in order to get the full picture and the right answer it is much better to think on it, rather than writing computer routines

May 8th, 2011 at 1:19 pm

I’m gutted that to solve this, it does seem necessary to put your faith in the Wiki article. I take it as read that the Pell’s equation solution techniques are guaranteed to produce all of the solutions.

The most obvious realisation is that to get an integer value of m, the 28n² +1 must be a perfect square = k² say. Then we can rewrite that as k² – 28n² = 1 and observe that 28 =2²*7 => k² -7q² = 1, where q = 2n. To find the first non-trivial solution I noted that the equation => k² = 1 (mod 7) and so tried n = 1,2,3,… and found that the modulo equation is satisfied by x = 1+7a and 6+7b. The first non-trivial value that satisfied k² -7q² = 1 was k = 8 => q = 3. But that’s no good as we need q even. The even q (k,q) values (found on the Wiki page) are (1,0),(127,48),(32257,12192),(8193151,3096720),…. They give m = 2²,16², 254²,4048², where I’ve included the trivial solution.

NB having got k

_{1}= 127 and q_{1}= 48, we can generate as many new values as we want (and missing none) with k_{t}+ q_{t}√7 = (127 + 48√7)^{t}. Sadly, I see no obvious/easy way to show that m will be square – but I’m being very lazy today.May 8th, 2011 at 4:50 pm

Hi slavy. I’m glad I posted this problem because that caused you to mention Pell’s equation: x² – ny² = 1. I like the look and feel of it, and am dying to know the theory behind it’s solution and to see a proof that it’s solvable for all (non-square?) natural numbers n (and possibly infinitely many, but not all, -ve values of n).

I find myself quite surprised and delighted that the posted problem is true and definitely not trivial

May 8th, 2011 at 5:19 pm

I’ve just read up a bit on the “Chakravala method” http://en.wikipedia.org/wiki/Chakravala_method. It’s quite impressive. Herman Hankel said “[it's] the finest thing achieved in the theory of numbers before Lagrange”. I can’t argue with that; I think the algorithm is supremely elegant – it blows Euclid’s division algorithm away.

May 9th, 2011 at 7:11 pm

Just as a minor (or possibly totally significant) curiosity, starting with m = 2 + 2 √(28 n² + 1) we get ((m-2)/2)² – 28n² = 1. If we replace (m-2)/2 with x and n with y/2, we get x² – 7y² = 1 (again).

May 10th, 2011 at 1:32 am

Chris is getting closer and closer Since nobody else seems to be interested in the problem, while Chris is its author and should not be the one to solve it, let me tell you how it is done (at least the brute force argument – I still believe I saw more elegant solutions in the past).

I start with the last post of Chris. Let p = √(28n² + 1) be an integer. Then we need to show that m = 2p+2 = 2(p+1) is a perfect square. But p² = 28n²+1, so 28n² = p²-1 = (p-1)(p+1). Let d be a common divisor of (p+1,p-1). Then d should divide its difference, as well, so d = 1 or 2. Moreover, 28 is even, so (p+1)(p-1) should be even, too, and thus, d = 2. Now the analysis becomes a bit subtler. 28 = 4*7 and in a perfect square all the prime factors involved appear at even power, so (p+1)(p-1) = 2

^{2k}*(odd number), meaning that in the factorizations of both p+1 and p-1 takes part at an odd power (first homework problem ). This is possible only if we split the two twos from the factor 28 into the two multiples. What remains in 7n² which we have to write as a product of two relatively prime numbers: (p+1)/2 and (p-1)/2. Since 7 is a prime number itself, there is only one way to do it: 7x²*y², where x*y = n. So there are two possibilities with respect to the order of the two multiples, i.e., we either have p+1 = 14x², p-1 = 2y² orp+1 = 2x², p-1=14y². The first option gives rise to

2 = (p+1)-(p-1) = 14x²-2y² or y² = 7x²-1 = -1 = 6 (mod 7)

But direct check with 1,2,3,4,5 and 6 tells us that the only (nonzero) quadratic remainders modulo 7 are 1 (1² and 6²), 2 (3² and 4²) and 4 (2² and 5²). So the equation y² = -1 = 6 (mod 7) does not admit integral solutions. Therefore, we are stuck with the second case, i.e., p+1 = 2x² and p-1 = 14y², which leads to

m = 2(p+1) = (2x)².

This is enough for the problem, but in order to analyze how many integral solutions the original equation has, we can do a step further and use the Pell’s equation through

2 = (p+1)-(p-1) = 2x²-14y² or x²-7y² = 1

which we know that has infinitely many integral solutions that are pretty easy to obtain – one just needs a generator, which in this case is the minimal solution (x

_{1}=8,y_{1}=3) ) and, using that(x

_{1}- √7y_{1})(x_{1}+√7y_{1}) = 1 = (x_{1}- √7y_{1})^{k}(x_{1}+√7y_{1})^{k}and that 7 is not a perfect square, so √7 is irrational, they create larges solutions via x

_{k}- √7y_{k}= (x_{1}- √7y_{1})^{k}for all natural numbers k. To show that those solutions are actually all the admissible ones is more complicated and I don’t want to deal with it hereMay 10th, 2011 at 5:17 am

Hi slavy. Thanks for that, I shall definitely read it properly tonight. I enjoy solving the problems too. Especially recently, I put up problems that I do not know or have access to the solution. So I’m in the same boat as everyone else.

I accept that proving that the methods of solving Pell’s equation actually do produce all the solutions is way beyond what I expect anyone here to show.

May 10th, 2011 at 4:54 pm

Hi slavy. I’ve now read your post. The only bit I don’t understand is (p+1)(p-1) = 2

^{2k}*(odd number). But I shall have a think on it as you’ve made it be our homework.I love the way you derived the generator. I’ve always thought of that sort of thing as being practically magic.

I guess you quite liked the problem. Thank you again for posting the analysis.

May 11th, 2011 at 3:39 pm

Hi Chris – you are welcome. Yes, I enjoyed the problem since I had the chance to check how worse I’ve become, since my active olympiad years. It’s good that the problem took me less than 15 minutes, but it is not good that I don’t remember the proof that those are all the integral solutions of the Pell’s equation, which I knew very well at that time

May 11th, 2011 at 4:28 pm

Hi slavy. Been too busy to really give this proper attention during the last couple of days. But tonight I thought I’d see why n can’t be a square.

If n = m², then x² – ny² = 1 => x² – (my)² = 1 => (x – my)(x + my) = 1. That can only be satisfied if both factors = 1 and so x = 1 and my = 0. Then the original equation has to be x² = 1.