Difference between revisions of "2019 AIME I Problems/Problem 14"
(→Solution 2 (Basic Modular Arithmetic)) |
(→Solution 2 (Basic Modular Arithmetic)) |
||
Line 39: | Line 39: | ||
<cmath>Solution 3</cmath> | <cmath>Solution 3</cmath> | ||
+ | |||
+ | Use the formula | ||
+ | <cmath>n = (\pi)*x + \sqrt{x}</cmath> | ||
==Video Solution== | ==Video Solution== |
Revision as of 15:53, 25 January 2021
Contents
Problem 14
Find the least odd prime factor of .
Solution
We know that for some prime
. We want to find the smallest odd possible value of
. By squaring both sides of the congruence, we find
.
Since , the order of
modulo
is a positive divisor of
.
However, if the order of modulo
is
or
then
will be equivalent to
which contradicts the given requirement that
.
Therefore, the order of modulo
is
. Because all orders modulo
divide
, we see that
is a multiple of
. As
is prime,
. Therefore,
. The two smallest primes equivalent to
are
and
. As
and
, the smallest possible
is thus
.
Note to solution
is the Euler Totient Function of integer
.
is the number of positive integers less than
relatively prime to
. Define the numbers
to be the prime factors of
. Then, we have
A property of the Totient function is that, for any prime
,
.
Euler's Totient Theorem states thatif
.
Furthermore, the order modulo
for an integer
relatively prime to
is defined as the smallest positive integer
such that
. An important property of the order
is that
.
Solution 2 (Basic Modular Arithmetic)
In this solution, will represent an arbitrary nonnegative integer.
We will show that any potential prime must be of the form
through a proof by contradiction. Suppose that there exists some prime
that can not be expressed in the form
that is a divisor of
. First, note that if the prime
is a divisor of
, then
is a multiple of
and
is not. Thus,
is not a divisor of
.
Because is a multiple of
,
. This means that
, and by raising both sides to an arbitrary odd positive integer, we have that
.
Then, since the problem requires an odd prime, can be expressed as
, where
is an odd integer ranging from
to
, inclusive. By Fermat's Little Theorem,
, and plugging in values, we get
, where
and is thus an even integer ranging from
to
, inclusive.
If , then
, which creates a contradiction. If
is not a multiple of
but is a multiple of
, squaring both sides of
also results in the same contradictory equivalence. For all remaining
, raising both sides of
to the
th power creates the same contradiction. (Note that
and
can both be expressed in the form
.)
Since we have proved that no value of can work, this means that a prime must be of the form
in order to be a factor of
. The smallest prime of this form is
, and testing it, we get
so it does not work. The next smallest prime of the required form is
, and testing it, we get
so it works. Thus, the answer is
. ~emerald_block
Use the formula
Video Solution
On The Spot STEM:
See Also
2019 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.