Waste less time on Facebook — follow Brilliant.
×

What?

Find the largest prime factor of \(16^5 + 13^4 - 172^2 \). Any ideas?

Note by Sal Gard
3 months, 3 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

I saw this same question on the AoPS forum (I believe it's from an ARML?), and realized no one has posted a solution, so if we're still interested,

\[16^5 + 13^4 - 172^2 = 2^{20} + 169^2 - 172^2 \]

\[ S = 2^{20} + -3(341) \]

\[ S = 2^{20} - 1023 = 2^{20} - 2^{10} + 1 \]

\[ S = \frac{2^{30} + 1}{2^{10} + 1} \]

\[ S = \frac{1 + 4(2^7)^{4}}{1 + 2^{10}} \]

We use Sophie-Germaine's identity to factorize \( a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab) \) and thus,

\[ S = \frac{ (2^{15} - 2^8 + 1)(2^{15} + 2^8 + 1)}{2^{10} + 1} \]

\[ S = 13 \cdot 61 \cdot 1321 \] and \( 1321 \) is prime. Ameya Daigavane · 3 months, 2 weeks ago

Log in to reply

@Ameya Daigavane Thanks for this great solution. Yes it was from the Arml in which I, for the first time, participated (I'm a sixth grader going into seventh.) I was trying to set up possible factors using Chinese remainder theorem systems. Are there any good approaches using this method? Either way, your solution is the most elegant. Sal Gard · 3 months, 1 week ago

Log in to reply

@Ameya Daigavane At the end, how did you factorize S? I mean, for me it is not obvious that 1321 is a factor. Mateo Matijasevick · 3 months, 2 weeks ago

Log in to reply

@Mateo Matijasevick You can get that \( 13 \) is a factor easily.
You can actually compute the terms in the numerator and note that \( 2^{10} + 1 = 25 * 41 \) so you know what factors to look out for. Ameya Daigavane · 3 months, 2 weeks ago

Log in to reply

@Ameya Daigavane I point that out from the beginning. It is easier to compute the original expression... but that's not the case of the problem. Mateo Matijasevick · 3 months, 2 weeks ago

Log in to reply

@Mateo Matijasevick It may be easier to compute, but not easier to factorise. We already have split the numerator into two factors, and we also know \( 25, 13 \) and \(41 \) are factors of their product - certainly that's progress?

Just for the sake of completeness, \[ \frac{2^{15} + 2^8 + 1}{25} = \frac{33025}{25} = 1321 \] Ameya Daigavane · 3 months, 2 weeks ago

Log in to reply

@Ameya Daigavane Got it. Good solution! Mateo Matijasevick · 3 months, 2 weeks ago

Log in to reply

What about the largest? I know there is a big one. Sal Gard · 3 months, 3 weeks ago

Log in to reply

Clearly 13 is a prime factor... does it help anything? Mateo Matijasevick · 3 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...