Mark Gritter (markgritter) wrote,
Mark Gritter

Generalized Fermat Through Brute Force

The generalized Fermat equation Ax^a + By^b = Cz^c has many integer solutions if 1/a + 1/b + 1/c > 1. It has rather fewer in the opposite case. I collected a bunch of references in this Quora question. The case a = 3, b = 2, c= 7 has been completely solved and there are a few "large" solutions including 9262^3+15312283^2=113^7.

Suppose you're not deep into analytic number theory and want to do a brute-force search for some more examples. A natural question to ask is whether some cases can be eliminated by a simple criteria that reduces the search space.

Take x^3 + y^11 = z^2, for example. If we calculate mod 4, then working through the 16 possibilities gives us only 7 cases that work:

y = 0 : x in { 0, 1 }
y = 1 : x in { 0, 2, 3 }
y = 2 : x = 1
y = 3 : x = 1

That means we can partition the search space and do only 7/16ths of the work, excluding all cases shown to be impossible mod 4. How well can we do with this approach? (In some cases we can get all the way to zero and prove impossibility! But not here.)

The farther out I search, the incrementally better "filters" I find. Calculating the possibilities mod 720 reduces the search space to about 4.3% of the possibilities. Improvements come at moduli 8, 12, 16, 24, 48, 72, 96, 120, 144, 240, 336, 480, and 672.

Now, I'm sure if I actually knew any analytic number theory this would be the point to say "aha! L-functions" or something like that. But perhaps there's an algebraic number theory reason for this sequence which some thought could discover.

When it comes time to do the brute force search, my favorite technique is Daniel Bernstein's heap-based approach which give us the candidate x^3 + y^11 values in order. Without using any of the above, I can tell you that there are no nontrivial solutions with |X| <= 1000000 and 0 < y < 300.
Tags: geek, mathematics
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.