# Finding the prime factors of $2^{14}+3^{14}$ by hand

I need to find the prime factors of $$2^{14}+3^{14}$$ by hand (this was given in an exam at my university, so this is the motivation - I decided to state this because it may look unjustified to try to factor such a big number).

I began by noticing that $$2^{14}+3^{14}=4^7+9^7=13\cdot 369181$$ after applying a well known formula. So, it all boils down to finding the prime factors of $$369181$$.

Let $$p$$ be such a prime. Obviously, $$p$$ is not $$2$$ since our number is odd. We have $$p|2^{14}+3^{14}$$, so $$2^{14} \equiv -3^{14} (p)$$, where $$(p)$$ is shorthand for $$\operatorname{mod} p$$, so $$2^{28}\equiv 3^{28}(p)$$. Since $$p$$ is not equal to $$2$$, $$2$$ has an inverse modulo $$p$$, call it $$2^{-1}$$. Thus, $$(3\cdot 2^{-1})^{14}\equiv -1(p)$$ and $$(3\cdot 2^{-1})^{28}\equiv 1(p)$$. This easily implies that the order of $$3\cdot 2^{-1}$$ in the group $$\mathbb{Z}_p^{\times}$$ is $$28$$. So, $$28$$ divides $$\varphi(p)=p-1$$, that is $$p=1+28t$$ for some $$t\in \mathbb{N}$$.

This is where things got messy. I could only continue by taking the square root of $$369181$$, which is $$607$$ point something, so I have to check whether $$369181$$ is divisible by any prime of the form $$28t+1$$ that is less than $$607$$. These primes are $$29, 113, 197, 281, 337, 421$$ and $$449$$ if I didnt make any mistakes.

Now, I could do the computations, but they are really long. I wonder if there is some neat way to avoid doing this.

• You might already know the answer: $369181$ is prime. I doubt whether there exists a better method. There is obviously no general (fast) method for factorizing $a^{14}+b^{14}$ for arbitrary $a,b$. Dec 8, 2021 at 23:00
• @WhatsUp, a partial factorization is $a^{14}+b^{14}=(a^2 + b^2) (a^{12} - a^{10} b^2 + a^8 b^4 - a^6 b^6 + a^4 b^8 - a^2 b^{10} + b^{12})$. That's where $13=2^2+3^2$ comes from.
– lhf
Dec 8, 2021 at 23:14
• Note that your argument that $p=1+28t$ relies on the fact that $(3\cdot2^{-1})^2\not\equiv-1\pmod{p}$, or equivalently, that $p\neq13$. Dec 9, 2021 at 0:11
• I'd like to learn something new... what is the well known formula? Dec 9, 2021 at 0:43
• It is debatable whether such an exercise should occur in an exam , it is still time consuming and doing such divisions (even if they are in principle easy to do) needs much care without giving additional insights (assuming that electronic help as a table calculator was not allowed). Dec 10, 2021 at 10:10

I believe you have done the best you can at avoiding tedious calculations. You have narrowed down the list of prime divisors to check to just $$7$$ primes. From here, you can check each of them quite easily by means of long division.
Another way to proceed, is to check whether $$(3\cdot2^{-1})^{14}\equiv-1\pmod{p},$$ for each of these primes. For the primes with $$t$$ even, this means $$3\cdot2^{-1}$$ is a quadratic residue mod $$p$$, and for primes with $$t$$ odd, this means $$3\cdot2^{-1}$$ is a quadratic nonresidue mod $$p$$. So it remains to determine $$\left(\frac{6}{p}\right)$$ for these primes.