Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 14 Feb '15 07:54
    How many solutions in natural numbers does x^a − y^b = 1 have, for x, a, y, b > 1? [I use ^ to indicate taking a power.]

    I have seen the answer to this, but not the proof. I am guessing the proof is quite difficult.

    So realistically, I am asking for you to be brave enough to estimate how many solutions there are. Infinitely many? If in fact a finite number, take a guess at how many. My motivation for posing this problem is I am just curious about your number theory intuition.
  2. 14 Feb '15 16:47
    Originally posted by Paul Dirac II
    How many solutions in natural numbers does x^a − y^b = 1 have, for x, a, y, b > 1? [I use ^ to indicate taking a power.
    Have you been browsing the same web pages I have? (I've been pottering about the edges of Fermat recently, for irrelevant reasons.)

    I know the answer, so I won't spoil it; but the coincidence of you asking this question just after I'd come across the answer is amusing.
  3. 14 Feb '15 17:41
    I did get this particular one from a web page, as it happens.

    I'll hold off longer on the answer in case anyone else wants to hazard a guess.
  4. Standard member forkedknight
    Defend the Universe
    15 Feb '15 05:37 / 2 edits
    does this assume a != b != x != y?
  5. 15 Feb '15 07:32
    Originally posted by forkedknight
    does this assume a != b != x != y?
    You do not have to assume those inequalities in this problem.

    I think we can see though that a=b is not actually going to get you anywhere, and likewise x=y is not going to get you anywhere.

    (But remember that all four of those things do need to be integers greater than 1.)
  6. 15 Feb '15 22:04
    3^2 - 2^3 = 1

    from this I conclude: at least one solution.
  7. 15 Feb '15 22:53 / 1 edit
    Originally posted by Bob Kramer
    3^2 - 2^3 = 1

    from this I conclude: at least one solution.
    Yep. Single-digit numbers give one "hit."

    Does anybody sense others are lurking at higher values of x, y, a or b?
  8. Standard member forkedknight
    Defend the Universe
    17 Feb '15 15:49
    there's nothing in the 2 <= a,b <= 10 and 2 <= x,y <= 1000 range

    I don't know how to go about a proof, though.
  9. 17 Feb '15 19:23
    I see forkedknight did some computer work. And it is true that there are no additional hits besides 9 - 8 = 1 in the range forkedknight checked.

    My intuition is such that I would find it very plausible that there are an infinite number of solutions. But my source says it was conjectured in 1844 that 9 - 8 = 1 is the only solution, and was proved in 2002. That it took more than a century means the proof (which I have not seen) is probably very advanced.
  10. 20 Feb '15 00:22
    Originally posted by Paul Dirac II
    But my source says it was conjectured in 1844 that 9 - 8 = 1 is the [b]only solution, and was proved in 2002. That it took more than a century means the proof (which I have not seen) is probably very advanced.[/b]
    It used to be Catalan's conjecture and now is Mihailescu's theorem. The 21st century has seen quite a bit of progress in number theory. The Green-Tao theorem was a 2004 achievement. In 2013, as far as I remember within a few days, preprints of two papers were published: one by Zhang, showing that there are infinitely many pairs of primes differing by 70,000,000 or less, and another one by Helfgott, proving the weak Goldbach conjecture.

    While it might sound as if the second one is more important, it is very much the opposite. The weak Goldbach conjecture is much less difficult than the Goldbach conjecture, and it had actually been "almost" proved in the 1930s: Vinogradov had shown that it is true for sufficiently large numbers.

    Zhang's theorem on the other hand was a shock to many who considered such a result out of reach. The number 70,000,000 is irrelevant and was very quickly improved upon. The important thing is that there actually is a number such that you can find infinitely many gaps between primes not exceeding it. That is, Zhang showed that, while prime gaps tend to get larger and larger on average, you can always find two primes "close" to one another, where, for Zhang, "close" means "70,000,000 or less apart". This is quite huge and gives some hope that humans might one day prove the twin prime conjecture, which says the same thing save for the definition of closeness. The twin prime conjecture considers primes to be close when they are 2 apart.

    Another thing that happened is that before Zhang's result a number of leading mathematicians had teamed up in 2009 to create the Polymath Project, an experiment in collaborative proof-making on the internet. It is an open project -- anyone can join in and try to do their part in solving a problem at hand. After Zhang issued his proof, it was proposed that they should try to lower Zhang's bound of 70,000,000. It turned out to be a success: the bound was lowered to 246 (!) and to 6 (!!) assuming a strong but widely believed conjecture.

    Another 21st century's remarkable achievement was the AKS algorithm, which establishes whether a given number n is prime in polynomial time (in the number of bits in the binary representation of n). Algorithms that achieved that were known before -- sort of. Some did it for only some numbers n, some did it non-deterministically (they ascertained that a number is prime with a very high probability) and the polynomial running time of some depended on the Riemann hypothesis. The AKS algorithm deals with all of these problems.