Margin

Censored

Challenge

Many mathematicians tried to prove Fermat’s Last Theorem, and one even seemed to be able to, but it was so difficult and incomprehensible that many did not believe him anyway. One of these incredulous mathematicians hopes to find counterexamples, but such that everything immediately becomes obvious to everyone. Help him and disprove the theorem.

https://margin.q.2022.ugractf.ru/67fd475f286cd5d6/

Solution

This seems like one of the easiest challenge in the ctf since almost everyteam(on the scorecoard) solved it at the beginning, well except for us and because of a dumb reason too. Here goes

The challenge essentially ask us to disprove Fermat’s last theorem, and til this day, it hasnt been done mathematically, googling disprove fermat's last theorem, the seccond result gives us an idea on how it could be done

In the video Femat’s last theorem was seemingly proved using a calculator’s limitation on the storing of floating points values, coincidentally, python also has this limitation

Looking at the verification code

POWER_CUBIC = 3.0
POWER_QUARTIC = 4.0


def parse_number(text, errors_key, errors):
    try:
        value = int(str(text).strip())
    except ValueError:
        errors[errors_key] = "not-an-integer"
        return None
    if not value > 0:
        errors[errors_key] = "not-positive"
        return None
    return value


def validate(form):
    errors = {}

    x_cubic = parse_number(form.get("x-cubic"), "x-cubic", errors)
    y_cubic = parse_number(form.get("y-cubic"), "y-cubic", errors)
    z_cubic = parse_number(form.get("z-cubic"), "z-cubic", errors)

    if  x_cubic  is  not  None  and  y_cubic  is  not  None  and  z_cubic  is  not  None :
        if x_cubic ** POWER_CUBIC + y_cubic ** POWER_CUBIC != z_cubic ** POWER_CUBIC:
            errors["cubic"] = "not-a-counterexample"

    x_quartic = parse_number(form.get("x-quartic"), "x-quartic", errors)
    y_quartic = parse_number(form.get("y-quartic"), "y-quartic", errors)
    z_quartic = parse_number(form.get("z-quartic"), "z-quartic", errors)

    if  x_quartic  is  not  None  and  y_quartic  is  not  None  and  z_quartic  is  not  None :
        if x_quartic ** POWER_QUARTIC + y_quartic ** POWER_QUARTIC != z_quartic ** POWER_QUARTIC:
            errors["quartic"] = "not-a-counterexample"

    return errors

We can see that our points of interests are these peices of code

POWER_CUBIC = 3.0
POWER_QUARTIC = 4.0
.
.
.
x_cubic ** POWER_CUBIC + y_cubic ** POWER_CUBIC != z_cubic ** POWER_CUBIC
.
.
.
x_quartic ** POWER_QUARTIC + y_quartic ** POWER_QUARTIC != z_quartic ** POWER_QUARTIC

Notice how POWER_CUBIC and POWER_QUARTIC are floats? This makes it possible to trick the validator into thinking we have disproved Fermat’s last theorem with the limitations mentioned above

At this point we can simply search for fermat last theorem near misses, for some reason during the ctf i didnt think of this ;-;

Anyway the first result gives us a way to generate inaccurate solutions of the third degree with an arbitrarily small error. All we have to do is find m, for that simply bruteforce

POWER_CUBIC = 3.0
POWER_QUARTIC = 4.0
for m in range(1, 500):
    z_cubic = 3*(m**3) + 3*(m**2) + 2*m + 1
    y_cubic = 3*(m**3) + 3*(m**2) + 2*m
    x_cubic = 3*(m**2) + 2*m + 1
    if x_cubic ** POWER_CUBIC + y_cubic ** POWER_CUBIC == z_cubic ** POWER_CUBIC:
        print(f"Cubic done with m={m} - x={x_cubic} y={y_cubic} z={z_cubic}")

As you can see for some reason, a - b - c is the reversed of x - y -z

The seccond result is from a havard math professor, its pretty complicated but if you scroll down, you will see a section with n = 4, theres a lot of values but once again brute force will get the job done, simply copy the data and turn them into python 2D arrays and then test each one against the provided equation,

POWER_CUBIC = 3.0
POWER_QUARTIC = 4.0
data = [
[21,36,37],
[167,192,215],
[242,471,479],
[717,967,1033],
[2111,2285,2620],	
[8191,16253,16509],
[16893,27753,28660],
[16382,32506,33018],	
[24576,48767,49535],	
[64493,85903,92037],	
[49152,97534,99070],	
[74191,118430,122748],
[73728,146301,148605],
[34231,157972,158059],
[118138,189321,196122],
[98304,195068,198140],
[76215,311390,311669],
[228730,398176,408599],
[249308,288317,322171],
[152430,622780,623338],
[419904,1257767,1261655],	
[468750,1168121,1175621],
[1259712,3773301,3784965],	
[839808,2515534,252331],
[2519424,7546602,7569930],	
[2099520,6288835,6308275],
[1679616,5031068,5046620],
[2652287,5948932,6006844],
]
for case in data: 
    x_quartic = case[0]
    y_quartic = case[1]
    z_quartic = case[2]
    if x_quartic ** POWER_QUARTIC + y_quartic ** POWER_QUARTIC == z_quartic ** POWER_QUARTIC:
         print(f"Quartic done with  x={x_quartic} y={y_quartic} z={z_quartic}")

With this we have found mutiple solutions for the challenge, simply pick one and submit

Flag

ugra_i_wish_fermat_had_css_f7a4e43c9970