Prove that if is any integer greater than 2 then there exist odd integers and such that

Printable View

- Apr 18th 2012, 09:18 AMmlef7a^2+b^2=2^N
Prove that if is any integer greater than 2 then there exist odd integers and such that

- Apr 18th 2012, 12:40 PMalexmahoneRe: 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,

where and

So, since and can be written in the form , so can , where N > 5.

Edit: On second thoughts, this doesn't seem to work because if are odd, and are even. - Apr 22nd 2012, 10:30 AMNowIsForeverRe: 7a^2+b^2=2^N
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);

}

}

}

}

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

2^{N}= (2^{3})^{10}2^{4}

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^{2}) + 1^{2}= 7(2^{2}) + 6^{2}= 2^{6} - Apr 22nd 2012, 01:31 PMalexmahoneRe: 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 PMPetekRe: 7a^2+b^2=2^N
- Apr 22nd 2012, 02:33 PMalexmahoneRe: 7a^2+b^2=2^N
- Apr 22nd 2012, 04:40 PMPetekRe: 7a^2+b^2=2^N
- Apr 24th 2012, 09:32 AMPetekRe: 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 .

Solution: Let N > 2 be given and suppose that x and y are odd integers such that . I claim that one of the following pairs of integers satisifies with both and odd.

Either and

or and

Suppose for the moment that the claim is true. We can then begin with the solution x = y = 1 for , use that solution to construct one for , and so on.

Proof of claim: Straightforward calculations show that

and

as required. We now argue that in one of the pairs both and will be odd.

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

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 or both elements must be odd.

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

Write . Let . We'll now work in the ring of integers of . can be described as the set of all elements of the form

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

Now calculate in two different ways:

and

These calculations yield

This completes the solution.