Difference between revisions of "2005 AMC 10A Problems/Problem 24"

Revision as of 12:52, 4 April 2024

Problem

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

$\textbf{(A) } 0\qquad \textbf{(B) } 1\qquad \textbf{(C) } 3\qquad \textbf{(D) } 4\qquad \textbf{(E) } 5$

Solution 1

If $P(n) = \sqrt{n}$ , then $n = p_{1}^{2}$ , where $p_{1}$ is a prime number.

If $P(n+48) = \sqrt{n+48}$ , then $n + 48$ is a square, but we know that n is $p_{1}^{2}$ .

This means we just have to check for squares of primes, add $48$ and look whether the root is a prime number. We can easily see that the difference between two consecutive square after $576$ is greater than or equal to $49$ , Hence we have to consider only the prime numbers till $23$ .

Squaring prime numbers below $23$ including $23$ we get the following list.

$4 , 9 , 25 , 49 , 121, 169 , 289 , 361 , 529$

But adding $48$ to a number ending with $9$ will result in a number ending with $7$ , but we know that a perfect square does not end in $7$ , so we can eliminate those cases to get the new list.

$4 , 25 , 121 , 361$

Adding $48$ , we get $121$ as the only possible solution. Hence the answer is $\boxed{\textbf{(B) }1}$ .

edited by mobius247

Note: Solution 1

Since all primes greater than $2$ are odd, we know that the difference between the squares of any two consecutive primes greater than $2$ is at least $(p+2)^2-p^2=4p+4$ , where p is the smaller of the consecutive primes. For $p>11$ , $4p+4>48$ . This means that the difference between the squares of any two consecutive primes both greater than $11$ is greater than $48$ , so $n$ and $n+48$ can't both be the squares of primes if $n=p^2$ and $p>11$ . So, we only need to check $n=2^2, 3^2, 5^2, 7^2,$ and $11^2$ .

~apsid

Video Solution

CHECK OUT Video Solution:https://youtu.be/IsqrsMkR-mA

~rudolf1279

Solution 2

If $P(n) = \sqrt{n}$ , then $n = p_{1}^{2}$ , where $p_{1}$ is a prime number.

If $P(n+48) = \sqrt{n+48}$ , then $n+48 = p_{2}^{2}$ , where $p_{2}$ is a different prime number.

So:

$p_{2}^{2} = n+48$

$p_{1}^{2} = n$

$p_{2}^{2} - p_{1}^{2} = 48$

$(p_{2}+p_{1})(p_{2}-p_{1})=48$

Since $p_{1} > 0$ : $(p_{2}+p_{1}) > (p_{2}-p_{1})$ .

Looking at pairs of divisors of $48$ , we have several possibilities to solve for $p_{1}$ and $p_{2}$ :

$(p_{2}+p_{1}) = 48$

$(p_{2}-p_{1}) = 1$

$p_{1} = \frac{47}{2}$

$p_{2} = \frac{49}{2}$

$(p_{2}+p_{1}) = 24$

$(p_{2}-p_{1}) = 2$

$p_{1} = 11$

$p_{2} = 13$

$(p_{2}+p_{1}) = 16$

$(p_{2}-p_{1}) = 3$

$p_{1} = \frac{13}{2}$

$p_{2} = \frac{19}{2}$

$(p_{2}+p_{1}) = 12$

$(p_{2}-p_{1}) = 4$

$p_{1} = 4$

$p_{2} = 8$

$(p_{2}+p_{1}) = 8$

$(p_{2}-p_{1}) = 6$

$p_{1} = 1$

$p_{2} = 7$

The only solution $(p_{1} , p_{2})$ where both numbers are primes is $(11,13)$ .

Therefore the number of positive integers $n$ that satisfy both statements is $\boxed{\textbf{(B) }1}.$

Solution 3

For the statement to be true, we must have both $n$ and $n + 48$ be squares of primes. Support we have the number $x^2$ , where $x$ is a positive integer. Then the next perfect square, $(x+1)^2$ , is $(x+1)^2 - x^2 = 2x+1$ greater than $x^2$ . The next perfect square after that will be $(x+2)^2 = 4x + 4$ greater than $x^2$ . In general, the prime $(x+n)^2$ will be $nx + n^2$ greater than $x^2$ . However, we must have that $nx + n^2 = 48$ . $n$ can take on any value between $1$ and $6$ (if $n$ is equal to $7$ , we have $14x + 49$ , where $x$ would have to be negative for the difference to be $48$ ). However, we can eliminate all the cases where $n$ is odd, because we would then have a number of the form $even + odd$ , which is odd because $x$ can take only integral values. As such, we consider $n = 2$ , $n = 4$ , and $n = 6$ . If $n = 2$ , then $4x + 4 = 48 \implies x = 11$ . Then our squares are $11^2$ and $13^2$ , both of which are squares of primes. If $n = 4$ , then $8x + 16 = 48 \implies x = 4$ . However, $4$ isn't prime, so we discard this case. Finally, if $n = 6$ , then $12x + 36 = 48 \implies x = 1$ . Again, $1$ isn't prime, so we discard this case as well. Thus, we only have $\boxed{\textbf{(B)}~1}$ valid case.

~ cxsmi

Video Solution 2

https://youtu.be/-8t5xaths_Q

~savannahsolver

@@ Line 108: / Line 108: @@
 For the statement to be true, we must have both <math>n</math> and <math>n + 48</math> be squares of primes. Support we have the number <math>x^2</math>, where <math>x</math> is a positive integer. Then the next perfect square, <math>(x+1)^2</math>, is <math>(x+1)^2 - x^2 = 2x+1</math> greater than <math>x^2</math>. The next perfect square after that will be <math>(x+2)^2 = 4x + 4</math> greater than <math>x^2</math>. In general, the prime <math>(x+n)^2</math> will be <math>nx + n^2</math> greater than <math>x^2</math>. However, we must have that <math>nx + n^2 = 48</math>. <math>n</math> can take on any value between <math>1</math> and <math>6</math> (if <math>n</math> is equal to <math>7</math>, we have <math>14x + 49</math>, where <math>x</math> would have to be negative for the difference to be <math>48</math>). However, we can eliminate all the cases where <math>n</math> is odd, because we would then have a number of the form <math>even + odd</math>, which is odd because <math>x</math> can take only integral values. As such, we consider <math>n = 2</math>, <math>n = 4</math>, and <math>n = 6</math>. If <math>n = 2</math>, then <math>4x + 4 = 48 \implies x = 11</math>. Then our squares are <math>11^2</math> and <math>13^2</math>, both of which are squares of primes. If <math>n = 4</math>, then <math>8x + 16 = 48 \implies x = 4</math>. However, <math>4</math> isn't prime, so we discard this case. Finally, if <math>n = 6</math>, then <math>12x + 36 = 48 \implies x = 1</math>. Again, <math>1</math> isn't prime, so we discard this case as well. Thus, we only have <math>\boxed{\textbf{(B)}~1}</math> valid case.
-~ cxsmi
+~ [https://artofproblemsolving.com/wiki/index.php/User:Cxsmi cxsmi]
 ==Video Solution 2==

2005 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search