Find the largest of the three prime divisors of the number $13^4 + 16^5 - 172^2$

Question

I was able to factor out only the prime 13,thus $13^4 + 16^5 - 172^2=13\cdot 80581$ What should be done to solve it? (Maybe some clever factorization, modulo, or anything else?)

Answer 1

Since $13^4−172^2 = (13^2-172)(13^2+172) = -3 \times 341 = -1023 = 1-2^{10}$ we see that

$$13^4+16^5−172^2 = 2^{20}-2^{10}+1.$$

Next, since

$$\frac{1+x^{30}}{1+x^{10}} = x^{20}-x^{10}+1,$$

then, using the Sophie Germain identity on both numerator and denominator, we have that

$$2^{20}-2^{10}+1 = \frac{1+4 \times (2^7)^4}{1+4 \times (2^2)^4} = \frac{1-2^8+2^{15}}{1+2^3+2^5} \times \frac{1+2^8+2^{15}}{1-2^3+2^5}= \frac{32513}{41} \times \frac{33025}{25}=793 \times 1321.$$

It's easy to see that $793 = 13 \times 61$ and, as the solution is a product of three primes, we are done. So the largest prime divisor is 1321.

Answer 2

Note that since $172 = 4 \cdot 43$, we have $$ \begin{align} 13^4 + 16^5 - 172^2 &= 13^4 + 16(16^4 - 43^2) \\ &= 13^4 + 16 (16^2 - 43)(16^2 + 43) \\ &= 13^4 + 16(213)\underbrace{(299)}_{13 \cdot 23} \\ &= 13(13^3 + 16 \cdot 23 \cdot 213)\end{align} $$ From here, there are several methods already stated in the comments, but one that worked particularly well for me (read: I got lucky with) is to look for primes $p$ such that for some $k$, $13^3 \equiv k \pmod{p}$ and $16 \cdot 23 \cdot 213 \equiv -k \pmod{p}$, so that $13^3 + 16 \cdot 23 \cdot 213 \equiv 0 \pmod{p}$. If we could find some such $p$, it would mean that $p \mid 13^3 + 16 \cdot 23 \cdot 213 \mid 13^4 + 16^5 - 172^2$.

Trying for small values of $k$, we first see that $k = 0$ is not helpful since $13 \nmid 16 \cdot 23 \cdot 213$, so next we try $k = 1$. To see what primes satisfy $13^3 \equiv 1 \pmod{p}$, we look at the factorization $$13^3 - 1 = (13 - 1)(13^2 + 13 + 1) = (2^2 \cdot 3)(3 \cdot 61) = 2^2 \cdot 3^2 \cdot 61$$ which yields $2, 3, 61$ as candidate solutions for $p$. However, it's clear that $p=2$ is not a solution since $13^3 + 16 \cdot 23 \cdot 213$ is odd, and $p = 3$ is not a solution since $13^3 + 16 \cdot 23 \cdot 213 \equiv 1 + 1 \cdot 2 \cdot 0 \equiv 1 \pmod{3}$.

Testing $p = 61$, the other congruence yields $$(16 \cdot 23) \cdot 213 \equiv 368 \cdot 30 \equiv 2 \cdot 30 \equiv -1 \pmod{61}$$ which is exactly the kind of result we were looking for. This proves $61 \mid 13^4 + 16^5 - 172^2$, and then it only remains to see what factors $80581/61 = 1321$ has. It is easy enough to check by hand that this is prime (using Peter's analysis for example, or just brute force all $18 = \lfloor \sqrt{1321} \rfloor / 2$ odd candidate factors), which gives you all three prime factors.