Exam (elaborations)
Modular_Arithmetic_in_the_AMC_and_AIME.
- Institution
- Nursing 220 Final Exam Review
Modular_Arithmetic_in_the_AMC_and_AIME.
[Show more]
Seller
Follow
Content preview
AMC/AIME HandoutModular Arithmetic in the AMC and AIME
Author: For:
freeman66 AoPS
Date:
May 13, 2020
0
11 1
10 2
9 3
8 4
7 5
6
It’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 AIME
Contents
0 Acknowledgements 3
1 Introduction 4
1.1 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Introduction to Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Modular Congruences 7
2.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Fermat’s Little Theorem and Euler’s Totient Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Residues 10
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Residue Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Operations in Modular Arithmetic 12
4.1 Modular Addition & Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Modular Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3 Modular Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.4 Modular Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5 Modular Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.6 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Chinese Remainder Theorem 17
5.1 Linear Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Worked Out Examples 24
7 Problems 29
A Appendix A: List of Theorems, Corollaries, and Definitions 30
2
,freeman66 (May 13, 2020) Modular Arithmetic in the AMC and AIME
§0 Acknowledgements
This 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 Community
Evan 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 finally, 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
§1 Introduction
§1.1 Number Theory
Number theory deals with the properties and relationships between numbers, especially positive integers.
Definition 1.1 (Prime & Composite) — If an integer has no positive divisors other than 1 and itself, it is
said to be prime; otherwise, it is said to be composite. Note that 1 is considered composite.
Definition 1.2 (Multiples & Factors) — An integer a is said to be a multiple of another integer b if there
exists an integer k such that a = kb. The integer b here is said to be called a factor or a divisor of a.
From this, we see that if a is a multiple of b, then b is a factor of a.
Definition 1.3 (Prime Factorization) — Any integer N can be written as the product of the primes it is
divisible by. The prime factorization of N is
Y
N= pei = 2e1 · 3e2 · 5e3 · . . . ,
p∈P
where P is the set of positive primes and {ei } is a sequence of integers determining how many times the ith
prime number can be divided out of N . For example, 144 = 22 · 32 and 35 = 51 · 71 .
§1.2 Bases
To understand the notion of base numbers, we look at our own number system. We use the decimal, or
base-10, number system. To help explain what this means, consider the number 2746. This number can be
rewritten as 123410 = 1 · 103 + 2 · 102 + 3 · 101 + 4 · 100 .
Note that each number in 1234 is actually just a placeholder which shows how many of a certain power of 10
there are. The first 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, or radix, 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 to convert bases, read this.
§1.3 Divisibility
Let us first formally define divisibility.
Definition 1.4 (Divisibility) — Let a, b ∈ Z. We say that b divides a if there exists an integer k such that
a = kb. The number b is called a divisor or factor of a, and the number a is called a multiple of b. We
write b|a to denote that b divides a.
Theorem 1.5 (Division Theorem)
Let a, b ∈ Z with b 6= 0. Then there exist unique integers q, r ∈ Z such that a = bq + r and 0 ≤ r < |b|.
Proof. First, note that if a = 0, then q = 0, r = 0 is the unique solution to the equation given.
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller modockochieng06. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £6.28. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
77333 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now