Show that 2^n=7*x^2+y^2 for some x,y odd.

[rbetan]

Homework Statement

Show that any power of two can be represented as 2^n=7*x^2+y^2 for some x,y odd.

This problem was given to us in preparation for the final for an undergraduate number theory class.

Homework Equations

The Attempt at a Solution

I tried numerical example to convince myself that it was true and to see if in the process i would get any ideas of how to approach this problem. But after many computations, i convince myself that it was true. but i could not come up with anything productive towards a proof.

Thanks for your help.

 

[Cyosis]

Could you show us some of those numerical examples you used?

 

[rbetan]

Here are some of the numerical examples... the higher the n the longer it took me to spot a solution.

Numerical Examples:

I could not get 2^1,2^2, but i did get the following

2^3=7(1)^2+(1)^2 so for n=3; one solution is x=1, y=1
2^4=7(1)^2+(3)^2 so for n=4; one solution is x=1, y=3
2^5=7(1)^2+(5)^2 so for n=5; one solution is x=1, y=5
2^6=7(3)^2+(1)^2 so for n=6; one solution is x=3, y=1
2^7=7(1)^2+(11)^2 so for n=7; one solution is x=1, y=11
2^8=7(5)^2+(9)^2 so for n=8; one solution is x=5, y=9
2^9=7(7)^2+(13)^2 so for n=9; one solution is x=7, y= 13
2^10=7(3)^2+(31)^2 so for n=10; one solution is x=3, y=31

I did not continue any further, since 2^10 is bigger than 1000 already. But i could not find any sol for n<3. so perhaps the instructor forgot to put the condition that n must be bigger than or equal to 3.

 

[snipez90]

I wouldn't feel too bad if you didn't get this one. IIRC the problem was proposed by Euler. I think the solution is to uncover a rather ingenious pattern from the following small cases:

2^3=7(1)^2+(1)^2 so for n=3; one solution is x=1, y=1
2^4=7(1)^2+(3)^2 so for n=4; one solution is x=1, y=3
2^5=7(1)^2+(5)^2 so for n=5; one solution is x=1, y=5
2^6=7(3)^2+(1)^2 so for n=6; one solution is x=3, y=1
2^7=7(1)^2+(11)^2 so for n=7; one solution is x=1, y=11
2^8=7(5)^2+(9)^2 so for n=8; one solution is x=5, y=9
2^9=7(7)^2+(13)^2 so for n=9; one solution is x=7, y= 13
2^10=7(3)^2+(31)^2 so for n=10; one solution is x=3, y=31

We first have to figure out how to get successive x values from previous (x,y) values. The first solution is (x,y) = (1,1). To get x = 1, the x value of the second solution, you can take the arithmetic mean of the values of the first solution. The second solution is (x,y) = (1,3), but to get x = 1, the x value of the third solution, you can't take the average of 1 and 3, but rather divide the absolute value of the difference by 2 to get |1-3| / 2 = 1. You can check for yourself that these two calculations generate successive x values from the previous x and y values (but the pattern does not always alternate between the two calculations).

Try to see if you can figure out the pattern for generating y values from previous (x,y) values on your own. Then try to correspond the resulting calculations so that you are able to transform a previous (x,y) pair to the next (x,y) pair. Once you can do this, it is clear what type of proof is needed to finish the problem.

 

[rbetan]

i see how to get the next X from the previous (x,y) from your hint.

if (x+y)/2= odd# ; keep it as the next X value and solve for the corresponding Y.if (x+y)/2= even#; then do |x-y|/2=odd#; keep this odd# as the next X value, solve for the corresponding Y.

It is also clear from this process, that the appropriate proof should be an induction proof. But, how to even start this proof is a mystery to me. I don't even see what would be an appropriate induction hypothesis.

the value of n is what increases by 1. but i don't see how to relate x,y values with the corresponding n value.

Any help with these please!

 

[gunch]

How about simply letting the induction hypothesis being:
P(n)=there exist positive odd integers x,y such that 2^n=7x^2+y^2?
You have shown P(3) and you are pretty close to showing that P(n) implies P(n+1). If you have shown that exactly (x+y)/2 or |x-y|/2 is odd you can chose one of those to get your new x, and from that find a new y. You then only need to show that the new y is an odd integer and that the new pair actually satisfies the equation.