Prove $13^{17} \ne x^2 + y^5$

I've been going in circles trying to prove $$13^{17} \ne x^2 + y^5$$

A friend of mine hinted to use modular arithmetic, but I'm not familiar with that field of study.

Any suggestions are appreciated.

Edit: $x,y \in\mathbb {N} $

Solution 1:

There is a simple solution using congruences. The set of quadratic residues modulo $11$ is $\{1,3,4,5,9\}$, the set of degree-$5$ residues is $\{1,10\}$; thus, $x^2\in\{0,1,3,4,5,9\}\pmod{11}$ and $y^5\in\{0,1,10\}\pmod{11}$ and consequently, for any integer $x$ and $y$, $$ x^2+y^5 \in \{0,1,3,4,5,9\} + \{0,1,10\} = \{0,1,2,3,4,5,6,8,9,10\} \pmod{11}. $$ Notice that $7$ is missing from the set in the right-hand side, meaning that an integer congruent to $7$ modulo $11$ cannot be represented in the form $x^2+y^5$ with $x$ and $y$ integer. However, using "Fermat's little theorem", $$ 13^{17} \equiv 2^{17} \equiv 2^7 \equiv -2^2 \equiv 7\pmod{11}. $$

Solution 2:

Check your equation mod 11:

$$13^{17} = 7 \pmod{11}$$ $$\begin{array} {r|r} X & X^2 \pmod{11} \\ \hline 0 & 0\\ 1 & 1\\ 2 & 4\\ 3 & 9\\ 4 & 5\\ 5 & 3\\ 6 & 3\\ 7 & 5\\ 8 & 9\\ 9 & 4\\ 10 & 1\\ \end{array}$$ $$\begin{array} {r|r} Y & Y^5 \pmod{11} \\ \hline 0 & 0\\ 1 & 1\\ 2 & 10\\ 3 & 1\\ 4 & 1\\ 5 & 1\\ 6 & 10\\ 7 & 10\\ 8 & 10\\ 9 & 1\\ 10 & 10\\ \end{array}$$

The java program I used to find $11$:

public class ThirteenSeventeen {

  public static void main(String[] args) {
    // does exist X,Y : 13^17 = x^2 + y^5

    for (int ModBase = 1; ModBase < 100; ModBase++) {
      boolean ExistFound = false;
      for (int X = 0; X < ModBase; X++) {
        for (int Y = 0; Y < ModBase; Y++) {
          if (ModExpt(13, 17, ModBase) == (ModExpt(X, 2, ModBase) + ModExpt(Y, 5, ModBase)) % ModBase) {
            ExistFound = true;
            break;
          }
        }
        if (ExistFound) break;
      }

      if (!ExistFound) {
        System.out.println("No Existance found for modular base: " + ModBase);
        System.out.println("13^17 = " + ModExpt(13, 17, 11));

        System.out.println("\\begin{array} {r|r} X & X^2 \\pmod{" + ModBase + "} \\\\ \\hline");
        for (int X = 0; X < ModBase; X++) {
          System.out.println("" + X + " & " + ModExpt(X, 2, ModBase) + "\\\\");
        }
        System.out.println("\\end{array}");

        System.out.println("\\begin{array} {r|r} Y & Y^5 \\pmod{" + ModBase + "} \\\\ \\hline");
        for (int Y = 0; Y < ModBase; Y++) {
          System.out.println("" + Y + " & " + ModExpt(Y, 5, ModBase) + "\\\\");
        }
        System.out.println("\\end{array}");

        break;
      }

    }

    System.out.println("Done");
  }

  // compute X^Y % P
  public static int ModExpt(int X, int Y, int P) {
    int R = 1;
    int S = X % P;
    while (Y > 0) {
      if (Y % 2 != 0) {
        R = (R * S) % P;
      }
      S = S * S % P;
      Y = Y / 2;
    }
    return R;
  }

}

Solution 3:

"mod 11" means "arithmetic where you ignore multiples of 11", so that 24 is the same as 2 (mod 11), because they differ by 22, which is a multiple of 11.

A cool fact: for any integer $n$, $n^{11}$ is the same as $n$ (mod 11)

So let's look at $13^{17}$ mod 11. Since $13 = 11 + 2$, this is the same as $2^{17}$ mod 11, which is the same as $2^{11} 2^6$, which is the same as $2\cdot 2^6 = 2^7$, which is $128$, which is the same as 7 (mod 11).

So mod 11, the left side of your equation is 7.

What about the right side? Well m if you look at the square of 0, 1, 2, 3, 4, ..., mod 11, you get $$ (0, 1, 4, 9, 16, 25, ...) \bmod 1 = (0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, 0, ...) $$ i.e., every square, mod 11, is $0, 1, 3, 4, 5,$ or $9$. Every 5th power, similarly, turns out to be either $0, 1,$ or $10$ (mod 11).

Now: If you take the numbers in the first list and add $0$ to them (mod 11), the results are not $7$ (mod 11). If you add $1$ to each, you get $1, 2, 4, 5, 10$, none of which is $7$ mod 11. And if you add $10$ to each, and simplify mod 11, you get $10, 0, 2, 3, 4$ and $8$, none of which is $7$ mod 11.

So since you can't make the left and right sides equal (mod 11), you can't make them equal at all.