2005 AMC 10A Problems/Problem 24
Contents
Problem
For each positive integer , let
denote the greatest prime factor of
. For how many positive integers
is it true that both
and
?
Solution 1
If , then
, where
is a prime number.
If , then
is a square, but we know that n is
.
This means we just have to check for squares of primes, add and look whether the root is a prime number.
We can easily see that the difference between two consecutive square after
is greater than or equal to
,
Hence we have to consider only the prime numbers till
.
Squaring prime numbers below including
we get the following list.
But adding to a number ending with
will result in a number ending with
, but we know that a perfect square does not end in
, so we can eliminate those cases to get the new list.
Adding , we get
as the only possible solution.
Hence the answer is
.
edited by mobius247
Note: Solution 1
Since all primes greater than are odd, we know that the difference between the squares of any two consecutive primes greater than
is at least
, where p is the smaller of the consecutive primes. For
,
. This means that the difference between the squares of any two consecutive primes both greater than
is greater than
, so
and
can't both be the squares of primes if
and
. So, we only need to check
and
.
~apsid
Video Solution
~rudolf1279
Solution 2
If , then
, where
is a prime number.
If , then
, where
is a different prime number.
So:
Since :
.
Looking at pairs of divisors of , we have several possibilities to solve for
and
:
(Note: you can skip several cases below by observing that and
must be even, and
.)
(impossible)
(Valid!)
(impossible)
(impossible)
(not prime)
The only solution where both numbers are primes is
.
Therefore the number of positive integers that satisfy both statements is
Solution 3
For the statement to be true, we must have both and
be squares of primes. Support we have the number
, where
is a positive integer. Then the next perfect square,
, is
greater than
. The next perfect square after that will be
greater than
. In general, the prime
will be
greater than
. However, we must have that
.
can take on any value between
and
(if
is equal to
, we have
, where
would have to be negative for the difference to be
). However, we can eliminate all the cases where
is odd, because we would then have a number of the form
, which is odd because
can take only integral values. As such, we consider
,
, and
. If
, then
. Then our squares are
and
, both of which are squares of primes. If
, then
. However,
isn't prime, so we discard this case. Finally, if
, then
. Again,
isn't prime, so we discard this case as well. Thus, we only have
valid case.
~ cxsmi
Video Solution 2
~savannahsolver
Solution 4
We know that since it asks for , we know that
must be a perfect square. Plus, we need
to be a perfect square of a prime since otherwise
won't be equal to the
. We can apply the same logic to
, 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 substitute
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:
Now, we realize that an odd number, , is equal to the difference of squares between
and
. This means we can test these cases and find
using the least odd number in each case. By looking at the first one, we see that
, and squaring it into
and setting it to
, we realize this works for the first part where
is equal to the
. Now, if we add
we get
, which works for the second part. If we do this for the second case,
, and square it and set it as
, we realize that since
must be prime and
is composite, so this can't work. Finally for the last case, we do
, and since
, this case doesn't work since
must be greater than
. Thus, our only valid case is the first one and our answer is
.
~ 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.