Results 1 to 9 of 9
Like Tree5Thanks
  • 1 Post By alexmahone
  • 1 Post By NowIsForever
  • 1 Post By Petek
  • 2 Post By Petek

Math Help - 7a^2+b^2=2^N

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    london
    Posts
    8

    Question 7a^2+b^2=2^N

    Prove that if N is any integer greater than 2 then there exist odd integers a and b such that 7a^2+b^2=2^N
    Last edited by mlef; April 18th 2012 at 09:38 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: 7a^2+b^2=2^N

    Quote Originally Posted by mlef View Post
    Prove that if N is any integer greater than 2 then there exist odd integers a and b such that 7a^2+b^2=2^N
    Test manually for N = 3, 4, 5.

    Any N > 5 can be written in the form 3p+4q, where p and q are non-negative integers. So, 2^N=2^{3p}2^{4q}=2^32^3\ldots 2^3(\text{p times})*2^42^4\ldots 2^4(\text{q times})

    (7a_1^2+b_1^2)(7a_2^2+b_2^2)=7a_3^2+b_3^2 where a_3=a_1b_2+a_2b_1 and b_3=7a_1a_2-b_1b_2

    So, since 2^3 and 2^4 can be written in the form 7a^2+b^2, so can 2^32^3\ldots 2^3(\text{p times})*2^42^4\ldots 2^4(\text{q times})=2^N, where N > 5.

    Edit: On second thoughts, this doesn't seem to work because if a_1,\ a_2,\ b_1,\ b_2 are odd, a_3 and b_3 are even.
    Last edited by alexmahone; April 18th 2012 at 05:23 PM.
    Thanks from mlef
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member NowIsForever's Avatar
    Joined
    May 2010
    From
    Norman, OK
    Posts
    43
    Thanks
    1

    Re: 7a^2+b^2=2^N

    Quote Originally Posted by alexmahone View Post
    ....On second thoughts, this doesn't seem to work because if a_1,\ a_2,\ b_1,\ b_2 are odd, a_3 and b_3 are even.
    Perhaps you can patch up your proof with minor alternations. I'll be looking to do this myself since this problem interests me. FWIW, I computed the results for N up to 30 using the C program below. Taking it beyond 30 will require a Bignum library, and while I'm looking for one so as not to have to reinvent the wheel, so far I haven't had any luck. What I've found seems rather obscure since it's not well documented, and I'm only interested in integer arithmetic—not floating point. Besides, if I implement one myself I'll have a working knowledge of how to extend it in various ways that may be more useful to its application re number theory.

    I've noticed that there is only one solution for every case of N < 30. Perhaps there is always a unique solution. It would be interesting to show that. Furthermore, if this is true, the property of integers could prove useful in cryptography, since it would assign a unique pair of odd numbers to every power of 2 >= 8. I'm not saying how it would be useful, I'm just speculating that it might be.

    The program:

    Code:
    #include <math.h>
    #include <stdio.h>
    
    int main()
    {
     int N;
     unsigned long a, b, L = 4, M, P;
    
     for (N = 3; N < 31; N++)
     {
      L *= 2; //note: L = 2^N
      M = sqrt((double)L);
      for (b = 1; b < M; b += 2)
      {
       P = L - b*b;
       if (!(P % 7))
       {
        a = sqrt((double)(P = P/7));
        if (P == a*a) printf("N = %i, 2^N = %i, a = %i, b = %i\n", N, L, a, b);
       }
      }
     }
    }
    The output:

    N = 3, 2^N = 8, a = 1, b = 1
    N = 4, 2^N = 16, a = 1, b = 3
    N = 6, 2^N = 64, a = 3, b = 1
    N = 8, 2^N = 256, a = 5, b = 9
    N = 9, 2^N = 512, a = 7, b = 13
    N = 10, 2^N = 1024, a = 3, b = 31
    N = 11, 2^N = 2048, a = 17, b = 5
    N = 12, 2^N = 4096, a = 11, b = 57
    N = 13, 2^N = 8192, a = 23, b = 67
    N = 14, 2^N = 16384, a = 45, b = 47
    N = 16, 2^N = 65536, a = 91, b = 87
    N = 17, 2^N = 131072, a = 89, b = 275
    N = 18, 2^N = 262144, a = 93, b = 449
    N = 19, 2^N = 524288, a = 271, b = 101
    N = 20, 2^N = 1048576, a = 85, b = 999
    N = 21, 2^N = 2097152, a = 457, b = 797
    N = 22, 2^N = 4194304, a = 627, b = 1201
    N = 23, 2^N = 8388608, a = 287, b = 2795
    N = 24, 2^N = 16777216, a = 1541, b = 393
    N = 25, 2^N = 33554432, a = 967, b = 5197
    N = 26, 2^N = 67108864, a = 2115, b = 5983
    N = 27, 2^N = 134217728, a = 4049, b = 4411
    N = 28, 2^N = 268435456, a = 181, b = 16377
    N = 29, 2^N = 536870912, a = 8279, b = 7555
    N = 30, 2^N = 1073741824, a = 7917, b = 25199
    Last edited by NowIsForever; April 22nd 2012 at 10:43 AM.
    Thanks from mlef
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: 7a^2+b^2=2^N

    @alexmahone - I think your method can be made to work. As you observed, we manually compute solutions for N = 3, 4, 5. If N > 5, then we can write N in one of the forms

    N = 3k + 3
    N = 3k + 4
    N = 3k + 5

    for k = 1, 2, 3, ... . We then use your product formula to derive solutions for larger values of N from the solutions for N = 3, 4, 5. For example, if N = 34 = (3)(10) + 4, we see that

    2N = (23)10 24

    and repeated application of the product formula to the solutions for N = 3, 4 yields the desired result.

    @NowIsForever - Sometimes there are multiple solutions to the equation:

    7(32) + 12 = 7(22) + 62 = 26
    Thanks from mlef
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: 7a^2+b^2=2^N

    @Petek - You really haven't addressed the concern I raised in the last line of my post.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: 7a^2+b^2=2^N

    Quote Originally Posted by alexmahone View Post
    @Petek - You really haven't addressed the concern I raised in the last line of my post.
    I guess I don't understand your concern. If, for example, a1 = a2 = b1 = b2 = 1, then a3 = 2, b3 = 6 is a valid solution.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: 7a^2+b^2=2^N

    Quote Originally Posted by Petek View Post
    I guess I don't understand your concern. If, for example, a1 = a2 = b1 = b2 = 1, then a3 = 2, b3 = 6 is a valid solution.
    No; the problem requires a and b to be odd.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: 7a^2+b^2=2^N

    Quote Originally Posted by alexmahone View Post
    No; the problem requires a and b to be odd.
    OK, I overlooked that requirement.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: 7a^2+b^2=2^N

    I think that I now have a valid solution. It uses some algebraic number theory, but nothing too advanced. Let me rephrase the problem as follows:

    Let N be an integer greater than two. Show that there exist odd integers x, y such that x^2 + 7y^2 = 2^N.

    Solution: Let N > 2 be given and suppose that x and y are odd integers such that x^2 + 7y^2 = 2^N. I claim that one of the following pairs of integers (x_1, y_1) satisifies x_1^2 + 7y_1^2 = 2^{N+1} with both x_1 and y_1 odd.

    Either x_1 = \frac{x-7y}{2} and y_1 = \frac{x+y}{2}

    or x_1 = \frac{x+7y}{2} and y_1 = \frac{x-y}{2}

    Suppose for the moment that the claim is true. We can then begin with the solution x = y = 1 for x^2 + 7y^2 = 2^3, use that solution to construct one for x_1^2 + 7y_1^2 = 2^4, and so on.

    Proof of claim: Straightforward calculations show that

    (\frac{x-7y}{2})^2 + 7(\frac{x+y}{2})^2 = 2(x^2 + 7y^2) = 2^{N+1}

    and

    (\frac{x+7y}{2})^2 + 7(\frac{x-y)}{2})^2 = 2(x^2 + 7y^2) = 2^{N+1}

    as required. We now argue that in one of the pairs (x_1, y_1) both x_1 and y_1 will be odd.

    Let x = 2n + 1 and y = 2m + 1. Then

    \frac{x-7y}{2} = n - 7m -3

    \frac{x+y}{2} = n + m +1

    \frac{x+7y}{2} = n + 7m + 4

    \frac{x-y}{2} = n -m

    Simple calculations mod 2 show that n - 7m - 3 and n + m + 1 have the same parity. The same is true of n + 7m + 4 and n - m. Similarly, n - 7m - 3 and n + 7m + 4 have opposite parity, as do n + m + 1 and n - m. Therefore, in one of the pairs (\frac{x-7y}{2}, \frac{x+y}{2}) or (\frac{x+7y}{2}, \frac{x-y}{2}) both elements must be odd.

    The solution in now complete, except for an explanation of how we derived the definitions of x_1 and y_1.

    Write x^2 + 7y^2 = (x + \sqrt{-7}y)(x - \sqrt{-7}y). Let K = \mathbb{Q}(\sqrt{-7}). We'll now work in the ring of integers A of K. A can be described as the set of all elements of the form

    \frac{u + v\sqrt{-7}}{2}

    where u and v are rational integers such that u \equiv v\pmod2. We can factor 2 in A as follows:

    2 = \frac{1 + \sqrt{-7}}{2}\times \frac{1 - \sqrt{-7}}{2}

    Now calculate 2(x^2 + 7y^2) in two different ways:

    2(x^2 +7y^2) = \frac{(1+\sqrt{-7})(x + \sqrt{-7}y)}{2} \times \frac{(1-\sqrt{-7})(x - \sqrt{-7}y)}{2}

    and

    2(x^2 +7y^2) = \frac{(1-\sqrt{-7})(x + \sqrt{-7}y)}{2} \times \frac{(1+\sqrt{-7})(x - \sqrt{-7}y)}{2}

    These calculations yield

    2(x^2 + 7y^2) = (\frac{x-7y}{2})^2 + 7(\frac{x+y}{2})^2 = (\frac{x+7y}{2})^2 + 7(\frac{x-y}{2})^2

    This completes the solution.
    Thanks from NowIsForever and mlef
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum