What?

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

#NumberTheory

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 5 years ago

At the end, how did you factorize S? I mean, for me it is not obvious that 1321 is a factor.

Mateo Matijasevick - 5 years ago

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 - 5 years ago

@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 - 5 years ago

@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 - 5 years ago

@Ameya Daigavane – Got it. Good solution!

Mateo Matijasevick - 5 years ago

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 - 4 years, 12 months ago

Clearly 13 is a prime factor... does it help anything?

Mateo Matijasevick - 5 years ago

What about the largest? I know there is a big one.

Sal Gard - 5 years ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$