2019 AIME I Problems/Problem 14
Contents
Problem
Find the least odd prime factor of .
Video Solution & More by MegaMath
https://www.youtube.com/watch?v=E6Vs5uf49Fc
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
. Because
, and
, each possible value of
must be verified by manual calculation to make sure that
. 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
Solution 3 (Official MAA)
Suppose prime divides
Then
Squaring gives
If
for some
it follows that
But
so
cannot divide
which is a contradiction. Thus
is the least positive power congruent to
By Fermat's Little Theorem,
It follows that
for some positive integer
The least two primes of this form are
and
The least odd factor of
is not
because
which implies
But
so
Thus the least odd prime factor is
In fact, where
is the
-digit prime
Solution 4
Let represent the least odd prime that the question is asking for.
We can see that
Squaring both sides we get
From Fermat's Little Theorem , we know that
has to be a multiple of 16. So we want to test prime numbers that fit this.
The first prime we get is 17 and when we try it in
We see that 17 does not work. The next number that works from the application of Fermat's Little Theorem is 97 and when we try that,
Thus our answer is .
~pengf
Video Solution
On The Spot STEM:
https://youtu.be/_vHq5_5qCd0 ghhghghghg
Video Solution by The Power Of Logic
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.