Difference between revisions of "2024 AMC 10B Problems/Problem 18"
(→Sidenote: Proof of Euler's Theorem) |
(→Sidenote: Proof of Euler's Theorem) |
||
Line 18: | Line 18: | ||
~lprado | ~lprado | ||
~edit by Elephant200 | ~edit by Elephant200 | ||
+ | |||
==Sidenote: Proof of Euler's Theorem== | ==Sidenote: Proof of Euler's Theorem== |
Revision as of 00:26, 17 November 2024
- The following problem is from both the 2024 AMC 10B #18 and 2024 AMC 12B #14, so both problems redirect to this page.
Contents
[hide]Problem
How many different remainders can result when the th power of an integer is divided by ?
Solution 1
First note that the Euler's totient function of is . We can set up two cases, which depend on whether a number is relatively prime to .
If is relatively prime to , then because of Euler's Totient Theorem.
If is not relatively prime to , it must be have a factor of . Express as , where is some integer. Then .
Therefore, can only be congruent to or . Our answer is .
~lprado ~edit by Elephant200
Sidenote: Proof of Euler's Theorem
Euler's Theorem states that , where is Euler's totient function, which counts the number of positive integers such that and . Note that this only works for positive integer such that
Consider the set such that and Multiply all terms by to create First, we prove that for any using contradiction. Let be a prime such that and This means that either or which is not possible since both and Next we show that no two elements in set are congruent modulo Let and exist such that Multiplying both sides by (which exists) gives This means that if then Now we multiply all terms in each set, and note that each residue appears exactly once in both sets, so we have: Because each has the property that we must have that Then multiplying both sides by the inverse of product thereof gives
Solution 2 (Euler Totient)
We split the cases into:
1. If is not a multiple of : we get
2. If is a multiple of : Clearly the only remainder provides
Therefore, the remainders can only be and , which gives the answer .
~mitsuihisashi14 ~BS2012 (Minor corrections) ~andliu766
Solution 3 (No Totient)
Note that
Taking this mod , we can ignore most of the terms except the for the last :
so . Substituting for , we get . Therefore, the remainders when divided by repeat every integers, so we only need to check the th powers of . But we have that and , so we really only need to check . We know that produce different remainders, so the answer to the problem is either or . But is not an answer choice, so the answer is .
Solution 4 (Totient)
Euler's Totient Function, returns as a product of each prime divisor of .
Euler's Totient Theorem states that if is an integer and is a positive integer relatively prime to , then .
In this case, , which is convenient because only has one prime factor, , therefore , so where . Every single number that isn't a multiple of is relatively prime to , therefore we have two cases:
1)
2)
The answer is ~Tacos_are_yummy_1
Solution 5 (Binomial Theorem)
~Kathan
Solution 7 (Guess)
(Do not use this solution unless you are low on time or do not know how to solve this problem.) Notice that all the answer choices are odd and have some relationship to the number except for . doesn't seem to fit in with the other answer choices, so the test writers likely put it there because they had to. You can assume that it is the answer: .
Written by ChristianZhang
Video Solution 1 by Pi Academy (Fast and Easy ⚡🚀)
https://youtu.be/c6nhclB5V1w?feature=shared
~ Pi Academy
Video Solution 2 (Fast!)
https://www.youtube.com/watch?v=S7l_Yv2Sd7E
See also
2024 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 17 |
Followed by Problem 19 | |
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 |
2024 AMC 12B (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 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.