Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
+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) –  user17762 Mar 13 '12 at 22:28
add comment

3 Answers

up vote 20 down vote accepted

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

share|improve this answer
11  
It's not clear to me how you came up with $29$ here. –  Robert Israel Mar 13 '12 at 20:06
1  
Sometimes, "randomly" coming up with something like this (using exactly 29) is where experience with math problems is most important. –  Lazar Ljubenović Mar 13 '12 at 20:09
3  
What, for example, would you do with $18^{19}+19^{18}$? –  Robert Israel Mar 13 '12 at 20:10
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 there –  Kirthi Raman Mar 13 '12 at 20:10
    
@Robert Isreal: Sir, I would do this tinyurl.com/7um6zgf first to check and then find a proof –  Kirthi Raman Mar 13 '12 at 20:12
show 4 more comments

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

share|improve this answer
add comment

Hint: use the Sophie Germain identity which states

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

share|improve this answer
3  
That should be $2y^2$, not $y^2$. –  Robert Israel Mar 13 '12 at 20:32
    
Thanks, now edited. –  Perce Mar 13 '12 at 22:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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