15
$\begingroup$

I tried to find cycles of powers, but they are too big. Also $65^{n} \equiv 1(\text{mod}64)$, so I dont know how to use that.

  • 5
    +1. $n^{n+1} + (n+1)^n$ turns out to be a composite number for $n$ from $3$ to $79$. For $n=80$, it turns out to be a prime. (from numerical computations)2012-03-13

3 Answers 3

18

Hint: use the Sophie Germain identity which states

$$x^4+4y^4=(x^2+2xy+2y^2)(x^2-2xy+2y^2)$$

  • 3
    That should be $2y^2$, not $y^2$.2012-03-13
25

Hint $\rm\ \ x^4 +\: 64\: y^4\ =\ (x^2+ 8\:y^2)^2 - (4xy)^2\ =\ (x^2-4xy + 8y^2)\:(x^2+4xy+8y^2)$

Thus $\rm\ x^{64} + 64\: y^{64} =\ (x^{32} - 4 x^{16} y^{16} + 8 y^{32})\:(x^{32} - 4 x^{16} y^{16} + 8 y^{32})$

Below are some other factorizations which frequently prove useful for integer factorization. Aurifeuille, Le Lasseur and Lucas discovered so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations:

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^2}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$

22

$$64^{65}+65^{64} = 6^{65}+7^{64} \pmod{29}$$

$65=2 \times 28+9, 64 = 2 \times 28 +8$, and also gcd$(29,36)$ = gcd$(29,49) = 1$

Therefore by Fermat's Little Theorem

If gcd$(a,p)= 1$, and $p$ is a prime then $a^{(p-1)} \hspace{3pt}\equiv \hspace{3pt}1 \pmod{p}$

$36^{29-1} \equiv 1 \pmod{29}, \hspace{5pt}49^{29-1} \equiv 1 \pmod{29} \hspace{3pt} \implies \hspace{3pt} (6^{2})^{28} \equiv 1 \pmod{29}, \hspace{5pt} (7^{2})^{28} \equiv 1 \pmod{29}$

Therefore $6^{65} = 6^{(56+9)} \equiv 6^9 \pmod{29}, \hspace{5pt} 7^{64} = 7^{(56+8)} \equiv 7^8 \pmod{29}$

$$64^{65}+65^{64} \equiv 6^9+7^8 \pmod{29} \hspace{5pt} \equiv 22+7 \pmod{29} \equiv 0 \pmod{29}$$

Which shows that $$29 | (65^{64}+64^{65})$$

Therefore $65^{64}+64^{65}$ is not a prime.

  • 12
    It's not clear to me how you came up with $29$ here.2012-03-13
  • 1
    Sometimes, "randomly" coming up with something like this (using _exactly_ 29) is where experience with math problems is most important.2012-03-13
  • 3
    What, for example, would you do with $18^{19}+19^{18}$?2012-03-13
  • 1
    I think I tried to find small factors first, then $65+64=129$ and I randomly subtracted $100$ and since $29$ is a prime, got ideas from there2012-03-13
  • 0
    @Robert Isreal: Sir, I would do this http://tinyurl.com/7um6zgf first to check and then find a proof2012-03-13
  • 0
    See also https://oeis.org/A0734992012-03-13
  • 0
    I find your use of `\hspace{3pt}` everywhere most curious. You can use `\pmod{29}` to get "$\pmod{29}$" with the right spacing. See the [Short Math Guide for LaTeX](ftp://ftp.ams.org/pub/tex/doc/amsmath/short-math-guide.pdf).2012-03-13
  • 0
    http://www.alpertron.com.ar/ECM.HTM is good for integer factorization. Useful in this case because it will tell you immediately that 29 is a factor.2012-03-14