3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Henrik Aug 18 '18 at 8:18
  • 1
    $\begingroup$ $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. $\endgroup$ – Peter Aug 18 '18 at 8:28
  • 1
    $\begingroup$ 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$ $\endgroup$ – Peter Aug 18 '18 at 8:36
  • 1
    $\begingroup$ Since $13,37,61$ do not divide the cofactor $1321$ and $61^2>1321$, $1321$ must be prime giving the final answer. $\endgroup$ – Peter Aug 18 '18 at 8:42
  • $\begingroup$ @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. $\endgroup$ – redx Aug 18 '18 at 13:09
0
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.