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.

$\endgroup$
1
  • 5
    $\begingroup$ +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) $\endgroup$
    – user17762
    Mar 13, 2012 at 22:28

3 Answers 3

24
$\begingroup$

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\,$ (aka Aurifeuillean). 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}$$

$\endgroup$
22
$\begingroup$

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

$\endgroup$
8
  • 12
    $\begingroup$ It's not clear to me how you came up with $29$ here. $\endgroup$ Mar 13, 2012 at 20:06
  • 1
    $\begingroup$ Sometimes, "randomly" coming up with something like this (using exactly 29) is where experience with math problems is most important. $\endgroup$ Mar 13, 2012 at 20:09
  • 3
    $\begingroup$ What, for example, would you do with $18^{19}+19^{18}$? $\endgroup$ Mar 13, 2012 at 20:10
  • 1
    $\begingroup$ 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 there $\endgroup$ Mar 13, 2012 at 20:10
  • $\begingroup$ @Robert Isreal: Sir, I would do this tinyurl.com/7um6zgf first to check and then find a proof $\endgroup$ Mar 13, 2012 at 20:12
20
$\begingroup$

Hint: use the Sophie Germain identity which states

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

$\endgroup$
1
  • 3
    $\begingroup$ That should be $2y^2$, not $y^2$. $\endgroup$ Mar 13, 2012 at 20:32

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.