10
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Ask your friend for another hint :) $\endgroup$ – Zubin Mukerjee Mar 8 '16 at 18:32
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}\ $ $\endgroup$ – Bill Dubuque Jul 20 '16 at 19:20
3
$\begingroup$

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

}
$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.