1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 13, 2009 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Jun 13, 2009 #2


    User Avatar
    Homework Helper

    Could you show us some of those numerical examples you used?
  4. Jun 13, 2009 #3
    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.
  5. Jun 13, 2009 #4
    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:

    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.
  6. Jun 14, 2009 #5
    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!
  7. Jun 15, 2009 #6
    How about simply letting the induction hypothesis being:
    P(n)=there exist positive odd integers x,y such that [tex]2^n=7x^2+y^2[/tex]?
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook