PLS help me come up with a faster solution to this problem!

Art of Problem Solving

AoPS Online

Middle School Math Grades 5-8, Ages 10-13, MATHCOUNTS, AMC 8

Grades 5-8, Ages 10-13, MATHCOUNTS, AMC 8

3 M G

BBookmark VNew Topic kLocked

Middle School Math Grades 5-8, Ages 10-13, MATHCOUNTS, AMC 8

Grades 5-8, Ages 10-13, MATHCOUNTS, AMC 8

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

PLS help me come up with a faster solution to this problem!

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikemath247365

219 posts

ilikemath247365

#1 h Mar 13, 2025, 4:18 AM

Y by

2023 National Sprint Problem 30

Let $M = \frac{9^{40,000}}{9^{200} - 2}$ . If $M$ is rounded to the nearest integer and then divided by $100$ , what is the remainder?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

519 posts

#2 h Mar 13, 2025, 4:23 AM • 1 Y

Y by ilikemath247365

here is a good solution:

https://www.youtube.com/watch?v=f5VPfewADlM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikemath247365

219 posts

ilikemath247365

#3 h Mar 13, 2025, 4:24 AM

Y by

My solution:
Let $x = 9^{200}$ to make things easier. Now, let us consider the expression $\frac{x^{200}}{x - 2}$ . By doing polynomial long division on this expression, I realized that the expression was just:
$x^{199} + 2x^{198} + ..... + 2^{198}x^{2} + 2^{199}x$ plus some random fraction that we get. Since the person is rounding it to the nearest integer, we don't need to worry about that fraction. Now, we realize that $9^{200}$ leaves a remainder of $1$ when divided by $100$ (just by simple inspection). Therefore, plugging everything in and taking $mod(100)$ , we get the geometric series: $1 + 2 + 4 + 8 + ... + 2^{198} + 2^{199}$ . This simply evaluates to $2^{200} - 1$ . Now, $2^{200}$ leaves a remainder of $76$ when divided by a $100$ so our final answer should be $\boxed{75}$ .

Can someone help me come up with a faster solution under actual time pressure? Thanks!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1719 posts

#4 h Mar 13, 2025, 4:31 AM • 1 Y

Y by ilikemath247365

imma be fr that's basically how i did it when i solved it rn
um you don't have to expand it into the full polynomial form tho, you can leave it as $\frac{x^{200}-2^{200}}{x-2}$ , which might be a bit faster to think about
and to get that $2^{200}\equiv76\pmod{100}$ quickly, you can use euler's and crt to get 0 mod 4 and 1 mod 25 which gives 76 mod 100 (prob how you did it but wtv)

This post has been edited 1 time. Last edited by aidan0626, Mar 13, 2025, 4:36 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikemath247365

219 posts

ilikemath247365

#5 h Mar 13, 2025, 4:34 AM

Y by

Explanations to why $9^{200}$ is congruent to $1(mod 100)$ and e.t.c:
By the Euler Totient Function, we have:
$3^{40}$ leaves a remainder of $1$ when divided by $100$ . Since $9^{200}$ is equal to $3^{400}$ , this is just congruent to $1(mod 100)$ .
Now, $2^{10}$ leaves a remainder of $24$ when divided by $100$ . Now, we just need to simplify $24^{20}$ modulo $100$ . Notice $24^{2}$ leaves a remainder of $76$ . So now, we need to figure out $76^{10}$ modulo $100$ . Now, $76^{2}$ leaves a remainder of $76$ when divided by a $100$ . Therefore, we need to simplify $76^{5}$ modulo $100$ . We can simplify this by noting that $76^{4}$ leaves a remainder of $76$ when dividing by a $100$ . Lastly, we need to multiply by that last $76$ to get $76^{2}$ modulo $100$ which just simplifies to $76$ modulo $100$ as desired.
So you guys can see how long this problem took me to solve. Under real time pressure, I would take most of the time trying to solve this problem if I were crazy enough to attempt #30. This clearly doesn't help me time manage particularly well. If anyone has a simpler, basic solution that can be used to solve these type of problems really quickly, please let me know. Thanks again!

This post has been edited 1 time. Last edited by ilikemath247365, Mar 13, 2025, 4:39 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1719 posts

#6 h Mar 13, 2025, 4:38 AM

Y by

aidan0626 wrote:

and to get that $2^{200}\equiv76\pmod{100}$ quickly, you can use euler's and crt to get 0 mod 4 and 1 mod 25 which gives 76 mod 100 (prob how you did it but wtv)

this way is probably faster
since 0 mod 4 is very easy to see, and 2^20 is 1 mod 25 by euler's so 2^200 is also 1 mod 25

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikemath247365

219 posts

ilikemath247365

#7 h Mar 13, 2025, 4:40 AM

Y by

Oh yes, you're right! Thanks for the faster way to get $2^{200}$ modulo $100$ . I did it as shown above which took like 5 minutes!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

245 posts

#8 h Mar 13, 2025, 4:41 AM • 1 Y

Y by ilikemath247365

i like the sol

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a