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

• Apr 18th 2012, 09:18 AM
mlef
7a^2+b^2=2^N
Prove that if $\displaystyle N$ is any integer greater than 2 then there exist odd integers $\displaystyle a$ and $\displaystyle b$ such that $\displaystyle 7a^2+b^2=2^N$
• Apr 18th 2012, 12:40 PM
alexmahone
Re: 7a^2+b^2=2^N
Quote:

Originally Posted by mlef
Prove that if $\displaystyle N$ is any integer greater than 2 then there exist odd integers $\displaystyle a$ and $\displaystyle b$ such that $\displaystyle 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, $\displaystyle 2^N=2^{3p}2^{4q}=2^32^3\ldots 2^3(\text{p times})*2^42^4\ldots 2^4(\text{q times})$

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

So, since $\displaystyle 2^3$ and $\displaystyle 2^4$ can be written in the form $\displaystyle 7a^2+b^2$, so can $\displaystyle 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 $\displaystyle a_1,\ a_2,\ b_1,\ b_2$ are odd, $\displaystyle a_3$ and $\displaystyle b_3$ are even.
• Apr 22nd 2012, 10:30 AM
NowIsForever
Re: 7a^2+b^2=2^N
Quote:

Originally Posted by alexmahone
....On second thoughts, this doesn't seem to work because if $\displaystyle a_1,\ a_2,\ b_1,\ b_2$ are odd, $\displaystyle a_3$ and $\displaystyle 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
• Apr 22nd 2012, 01:03 PM
Petek
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
• Apr 22nd 2012, 01:31 PM
alexmahone
Re: 7a^2+b^2=2^N
@Petek - You really haven't addressed the concern I raised in the last line of my post.
• Apr 22nd 2012, 02:27 PM
Petek
Re: 7a^2+b^2=2^N
Quote:

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, a1 = a2 = b1 = b2 = 1, then a3 = 2, b3 = 6 is a valid solution.
• Apr 22nd 2012, 02:33 PM
alexmahone
Re: 7a^2+b^2=2^N
Quote:

Originally Posted by Petek
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.
• Apr 22nd 2012, 04:40 PM
Petek
Re: 7a^2+b^2=2^N
Quote:

Originally Posted by alexmahone
No; the problem requires a and b to be odd.

OK, I overlooked that requirement.
• Apr 24th 2012, 09:32 AM
Petek
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 $\displaystyle x^2 + 7y^2 = 2^N$.

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

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

or $\displaystyle x_1 = \frac{x+7y}{2}$ and $\displaystyle 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 $\displaystyle x^2 + 7y^2 = 2^3$, use that solution to construct one for $\displaystyle x_1^2 + 7y_1^2 = 2^4$, and so on.

Proof of claim: Straightforward calculations show that

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

and

$\displaystyle (\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 $\displaystyle (x_1, y_1)$ both $\displaystyle x_1$ and $\displaystyle y_1$ will be odd.

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

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

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

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

$\displaystyle \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 $\displaystyle (\frac{x-7y}{2}, \frac{x+y}{2})$ or $\displaystyle (\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 $\displaystyle x_1$ and $\displaystyle y_1$.

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

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

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

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

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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.