Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Olympiad (integers)

  1. Sep 14, 2008 #1
    Determine all pairs (x, y) of integers such that
    1 + 2^x + 2^(2x+1) = y^2.

  2. jcsd
  3. Sep 14, 2008 #2
    If you assume [tex]2^x=z[/tex] then the equation reduces to [tex]1+z+2z^2=y^2[/tex].
    Completing the square results in [tex](4z+1)^2+7=8y^2[/tex]. Substituting [tex]z=2^x[/tex] and taking log2 gives,

    [tex]x+2=log2(-1 +-\sqrt{8y^2-7})[/tex].

    For all integral values of x, LHS is an integer , say k.

    Now, this gives,

    [tex]2^k=-1+-\sqrt{8y^2-7}[/tex] which is also an integer (say k1) because 2k is also an integer. Which means that [tex]\sqrt{8y^2-7}[/tex] is also an integer (say k2).

    So thats the final condition you arrive at. For all integer values of y for which [tex]\sqrt(8y^2-7)[/tex] is an integer, x and y satisfy the above condition.
  4. Sep 14, 2008 #3
    Dont know how to get the latex code right, but -1+-\sqrt{8y^2-7} means the positive and negative root of 8y^2-7 subtracted by 1.
  5. Sep 14, 2008 #4
    By hand, y= 1,2,4 seems to satisfy the above condition, but analytically, maybe someone else could come up with a better solution. Dont know how to factor in the integer square condition.
  6. Sep 14, 2008 #5
    Here is an alternate (unfinished) route.

    A value of x = -1 will produce a LHS of 2, which is not a square; negative integers < -1 will not produce an integer LHS. Thus we need only be concerned with integers x >= 0.

    Trying out a few values by hand, we see that the pairs (0,2) and (4,23) are solutions, and x=1,2,3 are not. So now the question becomes, is there another solution for x > 4?

    With a little algebra (subtract 1 and expand the RHS) the equation becomes
    [tex]2^x (2^{x+1} + 1) = (y-1)(y+1)[/tex]​
    thus the RHS is the product of two consecutive evens, and y is odd. Let y = 2k+1; substituting, the RHS will become 2k(2k+1) = 4k(k+1). Dividing by 4 and replacing n = x-2 (with n > 2), we get
    [tex]2^n (2^{n+3} + 1) = k(k+1)[/tex]​
    Now one of k or k+1 is odd; the other will be divisible by 2^n (as a matter of fact, since 2^{n+3} + 1 is odd, 2^n is the greatest power of 2 that divides the RHS).

    If we could prove that no integer n > 2 satisfies the above, we would be done. The requirement of exactly n 2's among the prime factors of the RHS only sieves candidates, but does not provide a bound for k.

    My hunch is that something has to become broken when the powers of two get bigger, i.e. that the LHS cannot be expressed as a product of two consecutive integers (for n=2 it can, though).
  7. Sep 15, 2008 #6
    Ok, I will attempt to finish Dodo's solution. Just to recap, he subtracted 1 from both sides of the equation to factor the difference of squares. Since the LHS is even, it's not hard to see that y must be odd so he set y = 2k + 1 to arrive at

    [tex]2^x(2^{x+1} + 1) = 2k(2k+2) \Rightarrow 2^{x-2}(2^{x+1}+1) = k(k+1)[/tex].

    Furthermore, he set [tex]n = x - 2[/tex] but this time I'm going to put a different condition on n so that [tex]n \geq -2[/tex] because we want to find solutions for [tex]x \geq 0[/tex].

    So after applying the conditions, we have

    [tex]2^n(2^{n+3} + 1) = k(k+1), n \geq -2[/tex]

    Now consecutive integers are relatively prime and therefore, [tex]2^n | k[/tex] or [tex]2^n | k+1[/tex].

    Case 1: [tex]2^n | k \Rightarrow k = a2^n[/tex] for some integer [tex]a > 0[/tex]. Plugging this back into our last equation, we get [tex]2^n(2^{n+3}+1) = a2^n(a2^n + 1) \Rightarrow a^22^n + a = 2^{n+3} + 1 \Rightarrow 2^n(a^2 - 2^3) = 1 - a \Rightarrow 2^n = \frac{1-a}{a^2 - 8}[/tex]. For [tex]a > 2[/tex], the RHS is negative, which is a contradiction. [tex]a[/tex] cannot be 1 either, but for [tex]a = 2[/tex], we have [tex]2^n = \frac{1}{4} \Rightarrow n = -2 \Rightarrow x = 0[/tex]. Hence (0,2) and (0, -2) are solutions.

    Case 2: [tex]2^n | k + 1 \Rightarrow k = b2^n - 1[/tex] for some integer [tex] b > 0[/tex]. Applying the same technique as in the first case, we have [tex]2^n(2^{n+3} + 1) = (b2^n - 1)(b2^n) \Rightarrow b^22^n - b = 2^{n+3} + 1 \Rightarrow 2^n(b^2 - 8) = 1 + b \Rightarrow 2^n = \frac{1+b}{b^2 - 8}[/tex]. For [tex]b > 3[/tex], it's easy to see we won't find any solutions for n. Similarly, we won't find any solutions for [tex]b < 3[/tex] since the RHS will be negative (except our trivial solution which occurs when [tex]b = -2[/tex], but we assumed allowably [tex]b > 0[/tex]). Thus, we find that [tex]b = 3 \Rightarrow n = 2 \Rightarrow x = 4[/tex] gives us our other pair of solutions, (4, 23) and (4, -23)

    Note that we find our solutions in pairs because of the [tex]y^2[/tex] term in the original equation so (x, -y) is a solution whenever (x, y) is. Thus our solutions are (0, 2), (0, -2), (4, 23), and (4, -23)
  8. Sep 15, 2008 #7
    There is a small mistake in Dodo, where he says: the RHS will become 2k(2k+1) = 4k(k+1), since he really means 2k(2k+2) = 4k(k+1).

    I dont understand this use of RHS, or is it LHS? Oh! From reading snipez90, I see it means nothing more than left or right side of the equation.
    Last edited: Sep 15, 2008
  9. Sep 15, 2008 #8
    Thanks for answer(and for solution)
    CORRECT ANSWER :(x, y)- (0, 2), (0,−2), (4, 23), (4,−23)
  10. Sep 15, 2008 #9
    Thats it? Just 4 solutions? Shouldnt there be a general formula or something?
  11. Sep 17, 2008 #10
    chaoseverlasting: Thats it? Just 4 solutions? Shouldnt there be a general formula or something?

    Snipez90 did good work on that problem, I don't find any errors. So I guess we just have to accept it.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Olympiad (integers)
  1. Mathematics olympiad (Replies: 4)

  2. Olympiad geometry (Replies: 1)

  3. Olympiad Question: (Replies: 1)

  4. Math Olympiad (Replies: 11)