Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Note: Solution 1)
(→‎Solution 4)
(20 intermediate revisions by 6 users not shown)
Line 2: Line 2:
 
For each positive integer <math> n > 1 </math>, let <math>P(n)</math> denote the greatest prime factor of <math>n</math>. For how many positive integers <math>n</math> is it true that both <math> P(n) = \sqrt{n} </math> and <math> P(n+48) = \sqrt{n+48} </math>?
 
For each positive integer <math> n > 1 </math>, let <math>P(n)</math> denote the greatest prime factor of <math>n</math>. For how many positive integers <math>n</math> is it true that both <math> P(n) = \sqrt{n} </math> and <math> P(n+48) = \sqrt{n+48} </math>?
  
−
<math> \mathrm{(A) \ } 0\qquad \mathrm{(B) \ } 1\qquad \mathrm{(C) \ } 3\qquad \mathrm{(D) \ } 4\qquad \mathrm{(E) \ } 5 </math>
+
<math> \textbf{(A) } 0\qquad \textbf{(B) } 1\qquad \textbf{(C) } 3\qquad \textbf{(D) } 4\qquad \textbf{(E) } 5 </math>
  
 
==Solution 1==
 
==Solution 1==
Line 10: Line 10:
  
  
−
This means we just have to check for squares of primes, add 48 and look whether the root is a prime number.
+
This means we just have to check for squares of primes, add <math>48</math> 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,
+
We can easily see that the difference between two consecutive square after <math>576</math> is greater than or equal to <math>49</math>,
−
Hence we have to consider only the prime numbers till 23.
+
Hence we have to consider only the prime numbers till <math>23</math>.
  
−
 
+
Squaring prime numbers below <math>23</math> including <math>23</math> we get the following list.
−
Squaring prime numbers below 23 including 23 we get the following list.
 
  
 
<math>4 , 9 , 25 , 49 , 121, 169 , 289 , 361 , 529</math>
 
<math>4 , 9 , 25 , 49 , 121, 169 , 289 , 361 , 529</math>
  
−
 
+
But adding <math>48</math> to a number ending with <math>9</math> will result in a number ending with <math>7</math>, but we know that a perfect square does not end in <math>7</math>, so we can eliminate those cases to get the new list.
−
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.
 
  
 
<math>4 , 25 , 121 , 361</math>
 
<math>4 , 25 , 121 , 361</math>
  
−
 
+
Adding <math>48</math>, we get <math>121</math> as the only possible solution.
−
Adding 48, we get 121 as the only possible solution.
+
Hence the answer is <math>\boxed{\textbf{(B) }1}</math>.
−
Hence the answer is (B).
 
−
 
 
−
The only positive integer that satisfies both requirements is 11.
 
  
 
edited by mobius247
 
edited by mobius247
  
 
==Note: Solution 1==
 
==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 <math>(p+2)^2-p^2=4p+4</math>, where p is the smaller of the consecutive primes. For <math>p>11</math>, <math>4p+4>48</math>. This means that the difference between the squares of any two consecutive primes both greater than 11 is greater than 48, so <math>n</math> and <math>n+48</math> can't both be the squares of primes if <math>n=p^2</math> and p>11. So, we only need to check <math>n=2^2, 3^2, 5^2, 7^2, 11^2</math>.
+
Since all primes greater than <math>2</math> are odd, we know that the difference between the squares of any two consecutive primes greater than <math>2</math> is at least <math>(p+2)^2-p^2=4p+4</math>, where p is the smaller of the consecutive primes. For <math>p>11</math>, <math>4p+4>48</math>. This means that the difference between the squares of any two consecutive primes both greater than <math>11</math> is greater than <math>48</math>, so <math>n</math> and <math>n+48</math> can't both be the squares of primes if <math>n=p^2</math> and <math>p>11</math>. So, we only need to check <math>n=2^2, 3^2, 5^2, 7^2,</math> and <math>11^2</math>.
  
 
~apsid
 
~apsid
  
 
==Video Solution==
 
==Video Solution==
−
CHECK OUT Video Solution:https://youtu.be/IsqrsMkR-mA
+
https://youtu.be/IsqrsMkR-mA
  
−
~<i>rudolf1279<i>
+
~<i>rudolf1279</i>
  
 
==Solution 2==
 
==Solution 2==
Line 61: Line 56:
 
Looking at pairs of [[divisor]]s of <math>48</math>, we have several possibilities to solve for <math>p_{1}</math> and <math>p_{2}</math>:
 
Looking at pairs of [[divisor]]s of <math>48</math>, we have several possibilities to solve for <math>p_{1}</math> and <math>p_{2}</math>:
  
 +
(Note: you can skip several cases below by observing that <math>p_1+p_2</math> and <math>p_1-p_{2}</math> must be even, and <math>p_1+p_2  \neq  p_1-p_2 \pmod 4 </math>.)
  
 
<math> (p_{2}+p_{1}) = 48 </math>
 
<math> (p_{2}+p_{1}) = 48 </math>
  
−
<math> (p_{2}-p_{1}) = 1 </math>
+
<math> (p_{2}-p_{1}) = 1 </math> (impossible)
  
 
<math> p_{1} = \frac{47}{2} </math>
 
<math> p_{1} = \frac{47}{2} </math>
Line 77: Line 73:
 
<math> p_{1} = 11 </math>
 
<math> p_{1} = 11 </math>
  
−
<math> p_{2} = 13 </math>
+
<math> p_{2} = 13 </math> (Valid!)
  
  
 
<math> (p_{2}+p_{1}) = 16 </math>
 
<math> (p_{2}+p_{1}) = 16 </math>
  
−
<math> (p_{2}-p_{1}) = 3 </math>
+
<math> (p_{2}-p_{1}) = 3 </math> (impossible)
  
 
<math> p_{1} = \frac{13}{2} </math>
 
<math> p_{1} = \frac{13}{2} </math>
Line 89: Line 85:
  
  
−
<math> (p_{2}+p_{1}) = 12 </math>
+
<math> (p_{2}+p_{1}) = 12 </math>  
  
−
<math> (p_{2}-p_{1}) = 4 </math>
+
<math> (p_{2}-p_{1}) = 4 </math> (impossible)
  
 
<math> p_{1} = 4 </math>
 
<math> p_{1} = 4 </math>
Line 102: Line 98:
 
<math> (p_{2}-p_{1}) = 6 </math>
 
<math> (p_{2}-p_{1}) = 6 </math>
  
−
<math> p_{1} = 1 </math>
+
<math> p_{1} = 1 </math> (not prime)
  
 
<math> p_{2} = 7 </math>
 
<math> p_{2} = 7 </math>
Line 109: Line 105:
 
The only solution <math> (p_{1} , p_{2}) </math> where both numbers are primes is <math>(11,13)</math>.  
 
The only solution <math> (p_{1} , p_{2}) </math> where both numbers are primes is <math>(11,13)</math>.  
  
−
Therefore the number of [[positive integer]]s <math>n</math> that satisfy both statements is <math>1\Rightarrow \mathrm{(B)}</math>
+
Therefore the number of [[positive integer]]s <math>n</math> that satisfy both statements is <math>\boxed{\textbf{(B) }1}.</math>
 +
 
 +
==Solution 3==
 +
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.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Cxsmi cxsmi]
 +
 
 +
==Video Solution 2==
 +
https://youtu.be/-8t5xaths_Q
 +
 
 +
~savannahsolver
 +
 
 +
==Solution 4==
 +
We know that since it asks for <math>\sqrt{n}</math>, we know that <math>n</math> must be a perfect square. Plus, we need <math>n</math> to be a perfect square of a prime since otherwise <math>P(n)</math> won't be equal to the <math>\sqrt{n}</math>. We can apply the same logic to <math>\sqrt{n+48}</math>, and since we also the difference between two consecutive squares is an odd number, we must have an even number of consecutive odd numbers to sum up to <math>48</math> since it is even. Thus, this leads us to three cases, since if we split 48 into even more consecutive odd numbers we will go into the negatives:
 +
 
 +
<math>n + 48 = n + 23 + 25</math>
 +
 
 +
<math>n + 48 = n + 9 + 11 + 13 + 15</math>
 +
 
 +
<math>n + 48 = n + 3 + 5 + 7 + 9 + 11 + 13</math>
 +
 
 +
We know that an odd number, <math>n</math>, is equal to the difference of squares between <math>n/2 - 0.5</math> and <math>n/2 + 0.5</math>. This means we can test these cases and find <math>n</math> using the least odd number in each case. By looking at the first one, we see that <math>23/2 - 0.5 = 11</math>, and squaring it into <math>121</math> and setting it to <math>n</math>, we realize this works for the first part where <math>P(n)</math> is equal to the <math>\sqrt{n}</math>. Now, if we add <math>48</math> we get <math>169</math>, which works for the second part. If we do this for the second case, <math>9/2 - 0.5 = 4</math>, and square it and set it as <math>n</math>, we realize that since <math>\sqrt{n}</math> must be prime and <math>4</math> is composite, so this can't work. Finally for the last case, we do <math>3/2 - 0.5 = 1</math>, and since <math>1^2 = 1</math>, this case doesn't work since <math>n</math> must be greater than <math>1</math>. Thus, our only valid case is the first one and our answer is <math>\boxed{\textbf{(B)}~1}</math>.
 +
 
 +
~ neeyakkid23
  
 
==See Also==
 
==See Also==

Revision as of 14:18, 6 September 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

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}$:

(Note: you can skip several cases below by observing that $p_1+p_2$ and $p_1-p_{2}$ must be even, and $p_1+p_2 \neq p_1-p_2 \pmod 4$.)

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

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

$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$ (Valid!)


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

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

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

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


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

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

$p_{1} = 4$

$p_{2} = 8$


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

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

$p_{1} = 1$ (not prime)

$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

Solution 4

We know that since it asks for $\sqrt{n}$, we know that $n$ must be a perfect square. Plus, we need $n$ to be a perfect square of a prime since otherwise $P(n)$ won't be equal to the $\sqrt{n}$. We can apply the same logic to $\sqrt{n+48}$, and since we also the difference between two consecutive squares is an odd number, we must have an even number of consecutive odd numbers to sum up to $48$ since it is even. Thus, this leads us to three cases, since if we split 48 into even more consecutive odd numbers we will go into the negatives:

$n + 48 = n + 23 + 25$

$n + 48 = n + 9 + 11 + 13 + 15$

$n + 48 = n + 3 + 5 + 7 + 9 + 11 + 13$

We know that an odd number, $n$, is equal to the difference of squares between $n/2 - 0.5$ and $n/2 + 0.5$. This means we can test these cases and find $n$ using the least odd number in each case. By looking at the first one, we see that $23/2 - 0.5 = 11$, and squaring it into $121$ and setting it to $n$, we realize this works for the first part where $P(n)$ is equal to the $\sqrt{n}$. Now, if we add $48$ we get $169$, which works for the second part. If we do this for the second case, $9/2 - 0.5 = 4$, and square it and set it as $n$, we realize that since $\sqrt{n}$ must be prime and $4$ is composite, so this can't work. Finally for the last case, we do $3/2 - 0.5 = 1$, and since $1^2 = 1$, this case doesn't work since $n$ must be greater than $1$. Thus, our only valid case is the first one and our answer is $\boxed{\textbf{(B)}~1}$.

~ neeyakkid23

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AMC_10A_Problems/Problem_24&oldid=226620"