2005 AMC 10A Problem 24

P21-25~5 minPrint

Primes Diophantine Equations Apply an identity: SFFT, sum of squares, difference of cubes, Vieta Use an invariant, parity, or coloring argument

For each positive integer $m > 1$ , let $P(m)$ denote the greatest prime factor of $m$ . For how many positive integers $n$ is it true that both $P(n) = \sqrt{n}$ and $P(n+48) = \sqrt{n+48}$ ?

Show solution without answering

Key insight

The largest prime factor equals the square root only for a prime squared. So look for two prime squares 48 apart: 121 and 169.

Solution

First decode the strange condition $P(m) = \sqrt{m}$ .

1. What does the condition mean? $P(m)$ is a prime, so $\sqrt{m}$ must be a prime $p$ , and then $m = p^2$ . And for $m = p^2$ the only prime factor is $p$ , so the condition holds. For example, $P(49) = 7 = \sqrt{49}$ , but $P(36) = 3$ while $\sqrt{36} = 6$ . So the condition just says: $m$ is the square of a prime.
2. Restate the problem. We need primes $p$ and $q$ with $n = p^2$ and $n + 48 = q^2$ . So
$q^2 - p^2 = 48.$
3. Factor. $q^2 - p^2 = (q - p)(q + p)$ , so $48$ must be split as (small factor) $\times$ (big factor) with small $= q - p$ and big $= q + p$ .
4. Both factors are even. The two factors differ by $2p$ , which is even, so they are both even or both odd. Their product $48$ is even, so both are even. The even pairs for $48$ are $2 \times 24$ , $4 \times 12$ , $6 \times 8$ .
5. Solve each pair. $q$ is half the sum and $p$ is half the difference:

pair	$q$	$p$	both prime?
$2 \times 24$	$13$	$11$	yes
$4 \times 12$	$8$	$4$	no
$6 \times 8$	$7$	$1$	no

Answer. Only $n = 11^2 = 121$ works, and $121 + 48 = 169 = 13^2$ .

The answer is $\boxed{\textbf{(B)}\ 1}$ .

Why this works

The fancy notation hides a simple idea: "largest prime factor equals the square root" means "square of a prime." Two squares with a fixed difference are handled by factoring the difference of squares, and the both-even rule cuts the list of factor pairs down to three.

Alternative approach

Check small primes. If $p < q$ are primes, the gap $q^2 - p^2$ grows as the primes grow. For odd $p$ , the next possible prime is at least $p + 2$ , and $(p + 2)^2 - p^2 = 4p + 4$ . That is more than $48$ once $p$ is bigger than $11$ . So test only $p = 2, 3, 5, 7, 11$ : adding $48$ to $4, 9, 25, 49, 121$ gives $52, 57, 73, 97, 169$ . Only $169 = 13^2$ is a prime squared.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Decode the condition. If $P(m) = \sqrt{m}$ , then $\sqrt{m}$ is an integer and is prime, say $\sqrt{m} = p$ , so $m = p^2$ . Conversely $P(p^2) = p = \sqrt{p^2}$ . Thus the condition says exactly that $m$ is the square of a prime.

So we need primes $p, q$ with $n = p^2$ and $n + 48 = q^2$ , i.e.
$q^2 - p^2 = (q - p)(q + p) = 48.$

The factors $q - p$ and $q + p$ differ by $2p$ , an even number, so they have the same parity; since their product is even, both are even. The factor pairs of $48$ with both entries even are $(2, 24)$ , $(4, 12)$ , $(6, 8)$ . Solving $q = \frac{\text{sum}}{2}$ , $p = \frac{\text{difference}}{2}$ :

$(2, 24)$ : $q = 13$ , $p = 11$ , both prime.
$(4, 12)$ : $q = 8$ , not prime.
$(6, 8)$ : $q = 7$ , $p = 1$ , not prime.

Only $n = 11^2 = 121$ works (and indeed $121 + 48 = 169 = 13^2$ ).

The answer is $\boxed{\textbf{(B)}\ 1}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Number Theory, Chapter 7: Algebra With Integers
Introduction to Algebra, Chapter 11: Special Factorizations
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.2, §4.4)