6
$\begingroup$

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.

$\endgroup$
14
  • 2
    $\begingroup$ 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$. $\endgroup$
    – WhatsUp
    Dec 8, 2021 at 23:00
  • 4
    $\begingroup$ @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. $\endgroup$
    – lhf
    Dec 8, 2021 at 23:14
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Servaes
    Dec 9, 2021 at 0:11
  • 1
    $\begingroup$ I'd like to learn something new... what is the well known formula? $\endgroup$
    – lesath82
    Dec 9, 2021 at 0:43
  • 2
    $\begingroup$ 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). $\endgroup$
    – Peter
    Dec 10, 2021 at 10:10

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks for the alternative method! $\endgroup$
    – MathIsCool
    Dec 9, 2021 at 15:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .