Vtyjkyuk

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

Note that since $172 = 4 cdot 43$, we have
$$
beginalign 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)endalign
$$
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 pmodp$ and $16 cdot 23 cdot 213 equiv -k pmodp$, so that $13^3 + 16 cdot 23 cdot 213 equiv 0 pmodp$. 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 pmodp$, 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 pmod3$.

Testing $p = 61$, the other congruence yields $$(16 cdot 23) cdot 213 equiv 368 cdot 30 equiv 2 cdot 30 equiv -1 pmod61$$
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 sqrt1321 rfloor / 2$ odd candidate factors), which gives you all three prime factors.