AIME PrActIcE QuEstIons
2014 AIME l, Problem "Consider having the same color as the union of two disjoint events Calculate the probability of each event " Solution Answer (144): The event "both balls have the same color" is the union of two disjoint events, "ball 1 and ball 2 are both green" and "ball 1 and ball 2 are both blue '
2021 INVITATIONAL COMPETITIONS
The AIME I is administered on Wednesday, March 10, 2021 The AIME II is administered on Thursday, March 18, 2021 Students who qualified for the AIME will automatically be registered to take the AIME I If a competition manager cannot administer the AIME I and needs to administer THE MATHEMATICAL ASSOCIATION OF AMERICA
Economic Evaluation of AIME Mentoring
AIME educational mentoring program and is intended to assist AIME in communicating the full impact of its mentoring program to key stakeholders The AIME program looks to deliver a range of benefits through addressing disadvantage The diagram below shows the key drivers/challenges, the strategic responses used and how AIME
Modular Arithmetic in the AMC and AIME
freeman66 (May 13, 2020) Modular Arithmetic in the AMC and AIME We consider all other cases according to the signs of aand b Case 1: b>0;a>0 In order to prove the theorem, there are two parts: rst, to show the existence of these integers q;r, and second, to show their uniqueness For the existence, for each n 0 de ne r n= a nb Let S= n jr
Common AIME Geometry Gems
Common AIME Geometry Gems Dennis Chen July 30, 2018 0 Preface Some geometry problems show up on a lot of AIME handouts This is either because they are strong openers, are particularly insightful, or are challenging closers This handout is a collection of the ones that appear most frequently, so expect this handout to be just a few pages
AIME Solution Set 2015 - David Altizios Web Page
AIME Solution Set 2015 David Altizio January 12, 2018 Abstract These problems are ones I have collected from my problem-solving over the past few years that resemble AIME level problems, except that none of them have actually appeared on the AIME Each problem (should)
AIME Practice Set 2015 - David Altizios Web Page
David Altizio AIME Practice Set 2015 Page 3 2 Combinatorics 1 A random pizza is made by ipping a fair coin to decide whether to include pepperoni, then doing the same for sausage, mushrooms, and onions The probability that two random pizzas have at least one topping in common can be written in the form m n where mand nare positive integers
AIME Strategies - Dylan Yu
AIME, where a lot of the older techniques / types of problems don’t show up as much, meaning the problems are a) harder and b) need more creativity Thus, it is a good idea
[PDF] 51 Leonardo » Détails » Couleurs
[PDF] 51 Lexique Anglais - Gas-Oil
[PDF] 51 Prévisions de menus
[PDF] 51 rue de la tuilerie 25250 L`Isle sur le Doubs
[PDF] 51 – MARNE - Anciens Et Réunions
[PDF] 51%? - Jessica Joslin
[PDF] 51- Marie Elisabeth fille de Marcel Emile Boehm née en France le
[PDF] 51-2015 - vide grenier - règlementation circulation et
[PDF] 51. rue de l`AmiraI-Mouchez - 75013 Paris - Deutsch
[PDF] 51. Rundbrief (Januar 2016)
[PDF] 51. Unerlaubtes Entfernen vom Unfallort, § 142 StGB
[PDF] 51.4 ko-PDF Résultats Etape 2 - Anciens Et Réunions
[PDF] 510 - Commune de Breitenbach - Anciens Et Réunions
[PDF] 510 KB - Frühgeborene und Bildung
AMC/AIME Handout
Modular Arithmetic in the AMC and AIME
Author:
freeman66For: AoPS Date:May 13, 20200
1 2 3 4 567891011It's time for modular arithmetic!"I have a truly marvelous demonstration of this proposition which this margin is too narrow to contain." -
Pierre de Fermat
freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIMEContents0 Acknowledgements3
1 Introduction4
1.1 Number Theory
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Bases
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Divisibility
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Introduction to Modular Arithmetic
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Modular Congruences7
2.1 Congruences
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Fermat's Little Theorem and Euler's Totient Theorem
. . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Residues10
3.1 Introduction
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Residue Classes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Operations in Modular Arithmetic
124.1 Modular Addition & Subtraction
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2 Modular Multiplication
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.3 Modular Exponentiation
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.4 Modular Division
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.5 Modular Inverses
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.6 The Euclidean Algorithm
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Chinese Remainder Theorem
175.1 Linear Congruences
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.2 Chinese Remainder Theorem
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.3 Chinese Remainder Theorem
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 Worked Out Examples24
7 Problems29
A Appendix A: List of Theorems, Corollaries, and Denitions 302
freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIME§0Ackno wledgementsThis was made for the Art of Problem Solving Community out there! I would like to thank Evan Chen for his
evan.sty code. In addition, all problems in the handout were either copied from the Art of Problem Solving
Wiki or made by myself.Art of Problem Solving CommunityEvan Chen's Personal Sty File
freeman66's Website - Say Hi! And Evan says he would like this here for evan.sty: Boost Software License - Version 1.0 - August 17th, 2003 Copyright (c) 2020 Evan Chen [evan at evanchen.cc] https://web.evanchen.cc/ || github.com/vEnhance He also helped me with the hint formatting. I do honestly think that Evan is a LATEXgod!
And nally, please do not make any copies of this document without referencing this original one. At least cite
me when you are using this document. 3 freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIME§1Intro duction§1.1Numb erTheo ry
Number theorydeals with the properties and relationships between numbers, especially positive integers.Denition 1.1
(Prime & Composite)|If an integer has no positive divisors other than 1 and itself, it issaid to beprime; otherwise, it is said to becomposite.Note that 1 is considered composite.Denition 1.2
(Multiples & Factors)|An integerais said to be amultipleof another integerbif thereexists an integerksuch thata=kb. The integerbhere is said to be called afactoror adivisorofa.From this, we see that ifais a multiple ofb, thenbis a factor ofa.Denition 1.3
(Prime Factorization)|Any integerNcan be written as the product of the primes it is divisible by. Theprime factorizationofNis N=Y p2Pp ei= 2e13e25e3:::;wherePis the set of positive primes andfeigis a sequence of integers determining how many times theith
prime number can be divided out ofN. For example, 144 = 2232and 35 = 5171.§1.2Bases To understand the notion ofbase numbers, we look at our own number system. We use the decimal, orbase-10, number system. To help explain what this means, consider the number 2746. This number can be
rewritten as 123410= 1103+ 2102+ 3101+ 4100:Note that each number in 1234 is actually just a placeholder which shows how many of a certain power of 10
there are. The rst digit to the left of the decimal place (recall that the decimal place is to the right of the 6, i.e.
2746.0) tells us that there are six 100's, the second digit tells us there are four 101's, the third digit tells us there
are seven 102's, and the fourth digit tells us there are two 103's.Base-10 uses digits 0-9. Usually, the base, orradix, of a number is denoted as a subscript written at the right
end of the number (e.g. in our example above, 274610, 10 is the radix).To learn how toconvertbases, readthis .
§1.3Divisibilit y
Let us rst formally denedivisibility.Denition 1.4
(Divisibility)|Leta;b2Z. We say thatbdividesaif there exists an integerksuch that a=kb. The numberbis called adivisororfactorofa, and the numberais called amultipleofb. We writebjato denote thatbdividesa.Theorem 1.5(Division Theorem)Leta;b2Zwithb6= 0. Then there exist unique integersq;r2Zsuch thata=bq+rand 0r freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIMEWe consider all other cases according to the signs ofaandb. Case 1:b >0;a >0. In order to prove the theorem, there are two parts: rst, to show the existence of these Leta;b2Z. Thenaandbhave a gcd.Proof.First, if bothaandbare 0, then 0 is a gcd foraandb, since 0 is divisible byqfor everyq2Z. Ifais negative, we can replaceawithawithout impacting the divisibility properties ofa. Likewise, ifbis negative, we can replace it withb. Hence, we may proceed assuming that bothaandbare nonnegative, and at freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIMEProof of Claim 1.By the Division Theorem, there exist uniqueq;r2Zsuch thata=qd+r, and Hence, we have thatdis a common divisor to bothaandb. It remains to establish the second property for a Therefore,dmeets the denition of a gcd fora;b, and thus a gcd must exist.Theorem 1.9(Properties of GCD) the greatest common factor, dened by its name. It is the smallest multiplemin whichajmandbjm.Theorem 1.11(Product of LCM and GCM) gcd(a;b)lcm(a;b) =ab:What happens when gcd(a;b) = 1? We call thatcoprime, orrelatively prime:Denition 1.12 Let us start with a motivating example.Remark 1.14.When learning a new topic, try to nd themotivationbehind every idea. This will allow you to The key to solving this problem is realizing that the times will repeat themselves every 12 hours. In What is the multiple of 12 that is closest to 1000? After some experimentation, we see that the closest multiple is 996, so 996 hours from now it will be 1 : 00 as well. Thus, exactly 1000 hours from now the time will be For example, because 4;16;1000;and 4252 all share the same remainder when divided by 12, the following We have a clock with six numbers on its face: 0;1;2;3;4;and 5. The clock only hand moves clockwise from freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIMESolution.We start by listing the rst 30 numbers in the list and the rst 30 positive integers side by side: the left grid is the remainder of each number on the right grid when divided by 6. Hence, we see that the answer to part 3 is the remainder when 426, which is 0, and that the answer to part 4 is 13376, which is 5.§2.1Congruences Denition 2.2 dierence is a multiple ofa.We shorten "modulo" to "mod", and use the symbolto denote congruence. For example, How many positive integers less than 12 are relatively prime to 12?§2.2F ermat'sLittle Theo remand Euler's T otientTheo rem What if we replaced 12 with 100? Or what if we used 10000? That would take averylong time. So instead •Ifpis prime andn1,then(pn) =pnpn1:There isn't much to learn about the Totient Function, since it appears very rarely. Let us turn to its relation withmodular arithmetic. There are always the problems that ask for the last two/three/four/etc. digits of some large operation (for example, 10243. Even using a calculator won't help. So instead, we use the following Notice how Fermat's Little Theorem doesn't directly answer the problem, but by taking out all the 26s, we were able to get our answer. However, this leaves us with an issue - what if the modulo isn't prime? For example, to (n)1 (modn):Remark 2.12.Notice that this is a generalized form of Fermat's Little Theorem.Let's turn to an example: so the last two digits are 27.§2.3Exercises Exercise 2.14.How many numbers under 1000 are relatively prime to 1000? List the integers between -70 and 70 whose modulo 12 residues are 10.Solution.An integer is congruent to 10 mod 12 if it can be written as 12a+ 10 for any integera. This gives us (Residue classes are also known as equivalence classes or congruence classes.)For example,f62;50;38;26;14;2;10;22;34;46;58gis a residue class of 10 (mod 12). freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIMEExercise 3.3.Determine the modulo-9 residue of each of the following.0;a >0. Note that any presentation ofa=qb+ralso impliesa= (q)(b) +r. The choice of
q;rare both exist and are unique by Case 1. Case 3:b >
0;a <0. By Case 1, we have a uniqueq;rsuch thata= (q)b+r, with 0r < b. Hence
there is a uniqueq;rsuch thata=qbr, with 0r < b. Ifr= 0, this is sucient for the problem. Ifr6= 0, we can writea= (q1)b+ (br), then, and 0< br < b. Uniqueness will follow by an argument identical to that in Case 1. Case 4:b <
0;a <0. By Case 2, we have a uniqueq;rsuch thata= (q)b+r, with 0r < b. Proceed
as in Case 3 to construct a solution fora.Denition 1.6 (Quotient & Remainder)|Leta;b2Z, withb6= 0 and letq;rbe numbers such that a=qb+r, wherer < b. We say thatqis thequotientofadivided byb, and theris theremainderofa divided byb.Denition 1.7 (Greatest Common Divisor)|Leta;b2Z. An integerdis called agreatest common divisor ofa;b, frequently abbreviated as a gcd ofa;bif the following two conditions are met: •djaanddjb, and •ifqjaandqjb, thenqjd.Theorem 1.8(Existence of GCD) Claim 1.dja.
5 0r < d. Moreover, asd2X, there existu;v2Zsuch thatd=au+bv. Hence, we have
r=aqd =aq(au+bv) = (1qu)a+ (qv)b: Hence, ifr >0, we must haver2X. However, sincer < d, we cannot haver2X, sinced=min(X). Therefore,r= 0, soa=qdanddja.By the same technique, we can establish the following claim: Claim 2.djb.
Leta2Z. Then
•gcd(a;0) =a. •gcd(a;1) = 1. •For allk2Z, gcd(a;ka) =aThere also exists theleast common multiple:Denition 1.10 (Least Common Multiple)|Theleast common multipleof two numbersa;bis, like For integersa;b,
Leta;b2Zbe nonzero, and letd= gcd(a;b). Then
ad andbd are coprime. •Writea=dkfor somek2Z. Then fory2Z, ifaj(dy), thenkjy.§1.4Intro ductionto Mo dularArithmetic 5 : 00:
41610004252 (mod 12):
§2Mo dularCongruences
Let us start with a problem involving congruences:Example 2.1 0 to 1 to 2 to 3 to 4 to 5 and back again to 0.
1. What n umberis the hand p ointingat after 12 tic ks? 2. What n umberis the hand p ointingat after 28 tic ks? 3. What n umberis the hand p ointingat after 42 tic ks? 4. What n umberis the hand p ointingat after 1337 tic ks?7 1 2 3 4 5 0 1 2 3 4 5 6
1 2 3 4 507 8 9 10 1112
1 2 3 4 5 0 13 14 15 16 17 18
1 2 3 4 5 0 19 20 21 22 23 24
1 2 345 0 25 26 272829 30We can see that the answers to parts 1 and 2 are0and4, respectively. We can also notice that each number on
120 (mod 6) and 3216 (mod 4):
For integersxandy,yx(moda) if and only ifmjxy. Hence, for an integerz, we havexy=za. Isolatingzgives usz=xya
. Ifzis an integer, thenyx(moda).Theorem 2.3(Congruence Condition) for positive integersxandy,xy(moda) if and only if x=z1a+w, and y=z2a+w, wherez1,z2, andware integers, and 0w < a.Example 2.4 Ifn=pe11pe22pemm, then(n)
(n) =n 11p 1 11p 2 11p m :Now for a few identities: •For primep,(p) =p1, because all numbers less thanpare relatively prime to it. •For relatively primea;b,(a)(b) =(ab). •In fact, we also have for anya;bthat(a)(b)gcd(a;b) =(ab)(gcd(a;b)). Example 2.10
Find the remainder when 2
304is divided by 7.Solution.Using Fermat's Little Theorem witha= 2 andp= 7, we get
2 61 (mod 7):
Note that
2 304= 230024= (26)5024;
so (2 6)502415016162 (mod 7):
Letaandnbe relatively prime integers. Then
a Example 2.13
Find the last two digits of 3
83.Solution.We know that this is the same as taking mod 100. Using Euler's Totient Theorem witha= 3 and
n= 100, we get 3 (100)1 (mod 100): Using the formula for nding(n), we get(100) = 40. Thus, 3 401 (mod 100):
Notice that
3 83= 38033= (340)233;
so (3 40)233122727 (mod 100);
Exercise 2.15.Find the value of(12) and(1001).
Exercise 2.16.Find the last two digits of 31284.
Exercise 2.17.
Find the last two digits of 640+840. (Note: this question is hard! You cannot apply any of the theorems listed above on your rst step, since 6 and 8 are not relatively prime to 100) Exercise 2.18.Find((1000)).
Exercise 2.19.
Jimmy takes a one digit number to the fourth power and the last digit is 1. He takes it to the fth power and the last digit is 3. What is his number?§3Residues §3.1Intro duction
We say thatbis the modulo-aresidue ofcwhencb(moda), and 0b < a. 10 freeman66(May 13, 2020)Modular Arithmetic in the AMC and AIME§3.2Residue Cl asses We begin with a problem.Example 3.1
70<12a+ 10<70:
Subtracting 10 from all sides gives us
80<12n <60;
and dividing by 12 gives 623
< n <5: Thus, we have
n=6 : 12(6) + 10 =62 n=5 : 12(5) + 10 =50 n=4 : 12(4) + 10 =38 n=3 : 12(3) + 10 =26 n=2 : 12(2) + 10 =14 n=1 : 12(1) + 10 =2 n= 0 : 12(0) + 10 = 10 n= 1 : 12(1) + 10 = 22 n= 2 : 12(2) + 10 = 34 n= 3 : 12(3) + 10 = 46 n= 4 : 12(3) + 10 = 58 Hence, all integersbsuch that70< b <70 andb10 (mod 12) are f62;50;38;26;14;2;10;22;34;46;58g:We can now dene a residue class. Denition 3.2
(Residue Class)|The integers congruent tox(moda) are known as aresidue class. §3.3Exercises
11
3. 23
4. 434
5. 42
6. 1337 Exercise 3.4.Write each of the following integers in the form 3a+b, whereaandbare integers and
0b <3.
1. 43
2. 4 3. 100
4. 98
5. 42
6. -34 7. 1337
Exercise 3.5.Show that ifxy(moda) andyz(moda), thenxz(moda).§4Op erationsin Mo dularArithm etic §4.1Mo dularAddition & Subtraction Theorem 4.1(Modular Addition and Subtraction) Leta1;a2;b1;andb2be integers such that
aquotesdbs_dbs12.pdfusesText_18