Subscribe via feed.

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.


This post is under “MathsChallenge” and has 17 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

17 Responds so far- Add one»

  1. 1. slavy Said:

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

  2. 2. Chris Said:

    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 :(

  3. 3. cazayoux Said:

    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!

  4. 4. slavy Said:

    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.

  5. 5. Chris Said:

    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).

  6. 6. Chris Said:

    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.

  7. 7. slavy Said:

    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 ;)

  8. 8. slavy Said:

    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 :P

  9. 9. Chris Said:

    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 k1 = 127 and q1 = 48, we can generate as many new values as we want (and missing none) with kt + qt √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.

  10. 10. Chris Said:

    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 :)

  11. 11. Chris Said:

    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.

  12. 12. Chris Said:

    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).

  13. 13. slavy Said:

    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) = 22k *(odd number), meaning that in the factorizations of both p+1 and p-1 takes part at an odd power (first homework problem :P ). 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² or
    p+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 (x1=8,y1=3) ) and, using that

    (x1- √7y1)(x1+√7y1) = 1 = (x1- √7y1)k(x1+√7y1)k

    and that 7 is not a perfect square, so √7 is irrational, they create larges solutions via xk- √7yk = (x1- √7y1)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 here ;)

  14. 14. Chris Said:

    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.

  15. 15. Chris Said:

    Hi slavy. I’ve now read your post. The only bit I don’t understand is (p+1)(p-1) = 22k *(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.

  16. 16. slavy Said:

    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 :(

  17. 17. Chris Said:

    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.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0