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}$

• Ask your friend for another hint :) – Zubin Mukerjee Mar 8 '16 at 18:32

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}.$$

• Said simpler, integers of form $\,x^2+y^5\,$ are, mod $11,\,$ squares or their neighbors, i.e. squares plus ${-}1,0\,$ or $1.\,$ So if consecutive squares mod $11$ differ by more than $\,3\,$ then some residue is not of that form, which happens in our case for $5$ and $9$, i.e. $\,5+1 < 7 < 9-1,\,$ so $7$ is not a square or neighbor, so $\,x^2+y^5\not\equiv 7\pmod{11}\$ – Bill Dubuque Jul 20 '16 at 19:20

$$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;
}

}


"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.