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

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?)

• The number is small enough that you can just throw it at a computer, or as the second factor is also below $\sqrt{80581}\approx 284$ it wouldn't be too much work to just try the primes below that by hand. That leads to: Why do you need to factor this number, what factorisation algorithms do you know, how do you know there are three prime divisors? – Henrik Aug 18 '18 at 8:18
• $80581=284^2-3\cdot 5^2$ allows to further accelerate the search. You can concentrate on the primes having $3$ as a quadratic residue. – Peter Aug 18 '18 at 8:28
• To solve $x^2+y^2=80581$ , you can try to check the numbers ending with $09,41,59,91$ and in fact we have $$80581=241^2+150^2$$ showing that every prime factor of $80581$ must be of the form $12k+1$. Now, you soon should find $61\mid 80581$ – Peter Aug 18 '18 at 8:36
• Since $13,37,61$ do not divide the cofactor $1321$ and $61^2>1321$, $1321$ must be prime giving the final answer. – Peter Aug 18 '18 at 8:42
• @Henrik It's a sum from a PRMO paper, which is the first step to get to IMO from India. So I don't think it requires very advanced concepts unknown to highschool students. – redx Aug 18 '18 at 13:09

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.

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.