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
1 year, 5 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

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 - 1 year, 5 months ago

Log in to reply

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 - 1 year, 5 months ago

Log in to reply

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

Mateo Matijasevick - 1 year, 5 months ago

Log in to reply

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 - 1 year, 5 months 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 - 1 year, 5 months 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 - 1 year, 5 months ago

Log in to reply

@Ameya Daigavane Got it. Good solution!

Mateo Matijasevick - 1 year, 5 months ago

Log in to reply

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

Sal Gard - 1 year, 5 months ago

Log in to reply

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

Mateo Matijasevick - 1 year, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...