Difference between revisions of "2020 AIME I Problems/Problem 12"
Kevinmathz (talk | contribs) (→Solution 1) |
m (→Solution 2 (Simpler, just basic mods and Fermat's theorem)) |
||
Line 15: | Line 15: | ||
BY THE WAY, please feel free to correct my formatting. I don't know latex. | BY THE WAY, please feel free to correct my formatting. I don't know latex. | ||
− | Note that for all n, 149^n - 2^n is divisible by 149-2 = 147 because that is a factor. That is 3 | + | Note that for all <math>n</math>, <math>149^n - 2^n</math> is divisible by <math>149-2 = 147</math> because that is a factor. That is <math>3\cdot7^2</math>, so now we can clearly see that the smallest <math>n</math> to make the expression divisible by <math>3^3</math> is just <math>3^2</math>. Similarly, we can reason that the smallest <math>n</math> to make the expression divisible by <math>7^7</math> is just <math>7^5</math>. |
− | Finally, for 5^5, take mod | + | Finally, for <math>5^5</math>, take <math>(\text{mod} 5)</math> and <math>(\text{mod} 25)</math> of each quantity (They happen to both be <math>-1</math> and <math>2</math> respectively, so you only need to compute once). One knows from Fermat's theorem that the maximum possible minimum <math>n</math> for divisibility by <math>5</math> is <math>4</math>, and other values are factors of <math>4</math>. Testing all of them(just <math>1</math>,<math>2</math>,<math>4</math> using mods-not too bad), <math>4</math> is indeed the smallest value to make the expression divisible by <math>5</math>, and this clearly is NOT divisible by <math>25</math>. |
− | Therefore, the smallest n to make this expression divisible by 5^5 is 2^2 | + | Therefore, the smallest <math>n</math> to make this expression divisible by <math>5^5</math> is <math>2^2 \cdot 5^4</math>. |
− | Calculating the LCM of all these, one gets 2^2 | + | Calculating the LCM of all these, one gets <math>2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5</math>. Using the factor counting formula, |
− | the answer is 3 | + | the answer is <math>3\cdot3\cdot5\cdot6</math> = <math>\boxed{270}</math>. |
Can someone please format better for me? | Can someone please format better for me? | ||
-Solution by thanosaops | -Solution by thanosaops | ||
+ | -formatted by MY-2 | ||
==See Also== | ==See Also== |
Revision as of 23:05, 16 March 2020
Contents
Problem
Let be the least positive integer for which
is divisible by
Find the number of positive integer divisors of
Solution 1
Lifting the Exponent shows that so thus,
divides
. It also shows that
so thus,
divides
.
Now, multiplying by
, we see
and since
and
then
meaning that we have that by LTE,
divides
.
Since ,
and
all divide
, the smallest value of
working is their LCM, also
. Thus the number of divisors is
.
~kevinmathz
Solution 2 (Simpler, just basic mods and Fermat's theorem)
BY THE WAY, please feel free to correct my formatting. I don't know latex.
Note that for all ,
is divisible by
because that is a factor. That is
, so now we can clearly see that the smallest
to make the expression divisible by
is just
. Similarly, we can reason that the smallest
to make the expression divisible by
is just
.
Finally, for , take
and
of each quantity (They happen to both be
and
respectively, so you only need to compute once). One knows from Fermat's theorem that the maximum possible minimum
for divisibility by
is
, and other values are factors of
. Testing all of them(just
,
,
using mods-not too bad),
is indeed the smallest value to make the expression divisible by
, and this clearly is NOT divisible by
.
Therefore, the smallest
to make this expression divisible by
is
.
Calculating the LCM of all these, one gets . Using the factor counting formula,
the answer is
=
.
Can someone please format better for me?
-Solution by thanosaops -formatted by MY-2
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.