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

**mlef** · April 18th 2012, 09:18 AM

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$

**alexmahone** · April 18th 2012, 12:40 PM

Originally Posted by mlef

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.

**NowIsForever** · April 22nd 2012, 10:30 AM

Originally Posted by alexmahone

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

**Petek** · April 22nd 2012, 01:03 PM

@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

2^N = (2³)¹⁰ 2⁴

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(3²) + 1² = 7(2²) + 6² = 2⁶

**alexmahone** · April 22nd 2012, 01:31 PM

@Petek - You really haven't addressed the concern I raised in the last line of my post.

**Petek** · April 22nd 2012, 02:27 PM

Originally Posted by alexmahone

@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, a₁ = a₂ = b₁ = b₂ = 1, then a₃ = 2, b₃ = 6 is a valid solution.

**alexmahone** · April 22nd 2012, 02:33 PM

Originally Posted by Petek

I guess I don't understand your concern. If, for example, a₁ = a₂ = b₁ = b₂ = 1, then a₃ = 2, b₃ = 6 is a valid solution.

No; the problem requires a and b to be odd.

**Petek** · April 22nd 2012, 04:40 PM

Originally Posted by alexmahone

No; the problem requires a and b to be odd.

OK, I overlooked that requirement.

**Petek** · April 24th 2012, 09:32 AM

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.

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

LinkBack

Thread Tools

Display

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

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

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

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

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

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

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

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

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

Search Tags