Exam (elaborations)
SatoNT.
- Course
- Institution
Exam of 45 pages for the course Modular_Arithmetic_in_the_AMC_and_AIME. at Modular_Arithmetic_in_the_AMC_and_AIME. (SatoNT.)
[Show more]
Seller
Follow
modockochieng06
Content preview
Number TheoryNaoki Sato <sato@artofproblemsolving.com>
0 Preface
This set of notes on number theory was originally written in 1995 for students
at the IMO level. It covers the basic background material that an IMO
student should be familiar with. This text is meant to be a reference, and
not a replacement but rather a supplement to a number theory textbook;
several are given at the back. Proofs are given when appropriate, or when
they illustrate some insight or important idea. The problems are culled from
various sources, many from actual contests and olympiads, and in general
are very difficult. The author welcomes any corrections or suggestions.
1 Divisibility
For integers a and b, we say that a divides b, or that a is a divisor (or
factor) of b, or that b is a multiple of a, if there exists an integer c such
that b = ca, and we denote this by a | b. Otherwise, a does not divide b, and
we denote this by a - b. A positive integer p is a prime if the only divisors of
p are 1 and p. If pk | a and pk+1 - a where p is a prime, i.e. pk is the highest
power of p dividing a, then we denote this by pk ka.
Useful Facts
• If a, b > 0, and a | b, then a ≤ b.
• If a | b1 , a | b2 , . . . , a | bn , then for any integers c1 , c2 , . . . , cn ,
n
X
a| bi c i .
i=1
Theorem 1.1. The Division Algorithm. For any positive integer a and
integer b, there exist unique integers q and r such that b = qa + r and
0 ≤ r < a, with r = 0 iff a | b.
1
, Theorem 1.2. The Fundamental Theorem of Arithmetic. Every integer
greater than 1 can be written uniquely in the form
pe11 pe22 · · · pekk ,
where the pi are distinct primes and the ei are positive integers.
Theorem 1.3. (Euclid) There exist an infinite number of primes.
Proof. Suppose that there are a finite number of primes, say p1 , p2 , . . . ,
pn . Let N = p1 p2 · · · pn + 1. By the fundamental theorem of arithmetic, N
is divisible by some prime p. This prime p must be among the pi , since by
assumption these are all the primes, but N is seen not to be divisible by any
of the pi , contradiction.
Example 1.1. Let x and y be integers. Prove that 2x + 3y is divisible
by 17 iff 9x + 5y is divisible by 17.
Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒
17 | (9x + 5y), and conversely, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], or
17 | (36x + 20y) ⇒ 17 | (2x + 3y).
Example 1.2. Find all positive integers d such that d divides both n2 +1
and (n + 1)2 + 1 for some integer n.
Solution. Let d | (n2 + 1) and d | [(n + 1)2 + 1], or d | (n2 + 2n + 2).
Then d | [(n2 + 2n + 2) − (n2 + 1)], or d | (2n + 1) ⇒ d | (4n2 + 4n + 1), so
d | [4(n2 +2n+2)−(4n2 +4n+1)], or d | (4n+7). Then d | [(4n+7)−2(2n+1)],
or d | 5, so d can only be 1 or 5. Taking n = 2 shows that both of these
values are achieved.
Example 1.3. Suppose that a1 , a2 , . . . , a2n are distinct integers such
that the equation
(x − a1 )(x − a2 ) · · · (x − a2n ) − (−1)n (n!)2 = 0
has an integer solution r. Show that
a1 + a2 + · · · + a2n
r= .
2n
(1984 IMO Short List)
Solution. Clearly, r 6= ai for all i, and the r − ai are 2n distinct integers,
so
|(r − a1 )(r − a2 ) · · · (r − a2n )| ≥ |(1)(2) · · · (n)(−1)(−2) · · · (−n)| = (n!)2 ,
2
,with equality iff
{r − a1 , r − a2 , . . . , r − a2n } = {1, 2, . . . , n, −1, −2, . . . , −n}.
Therefore, this must be the case, so
(r − a1 ) + (r − a2 ) + · · · + (r − a2n )
= 2nr − (a1 + a2 + · · · + a2n )
= 1 + 2 + · · · + n + (−1) + (−2) + · · · + (−n) = 0
a1 + a2 + · · · + a2n
⇒ r= .
2n
Example 1.4. Let 0 < a1 < a2 < · · · < amn+1 be mn + 1 integers. Prove
that you can select either m + 1 of them no one of which divides any other,
or n + 1 of them each dividing the following one.
(1966 Putnam Mathematical Competition)
Solution. For each i, 1 ≤ i ≤ mn + 1, let ni be the length of the longest
sequence starting with ai and each dividing the following one, among the
integers ai , ai+1 , . . . , amn+1 . If some ni is greater than n then the problem
is solved. Otherwise, by the pigeonhole principle, there are at least m + 1
values of ni that are equal. Then, the integers ai corresponding to these ni
cannot divide each other.
Useful Facts
• Bertrand’s Postulate. For every positive integer n, there exists a prime
p such that n ≤ p ≤ 2n.
• Gauss’s Lemma. If a polynomial with integer coefficients factors into
two polynomials with rational coefficients, then it factors into two poly-
nomials with integer coefficients.
Problems
1. Let a and b be positive integers such that a | b2 , b2 | a3 , a3 | b4 , b4 | a5 ,
. . . . Prove that a = b.
2. Let a, b, and c denote three distinct integers, and let P denote a poly-
nomial having all integral coefficients. Show that it is impossible that
P (a) = b, P (b) = c, and P (c) = a.
(1974 USAMO)
3
, 3. Show that if a and b are positive integers, then
n n
1 1
a+ + b+
2 2
is an integer for only finitely many positive integers n.
(A Problem Seminar, D.J. Newman)
4. For a positive integer n, let r(n) denote the sum of the remainders when
n is divided by 1, 2, . . . , n respectively. Prove that r(k) = r(k − 1) for
infinitely many positive integers k.
(1981 Kürschák Competition)
5. Prove that for all positive integers n,
n
X g(k) 2n 2
0< − < ,
k=1
k 3 3
where g(k) denotes the greatest odd divisor of k.
(1973 Austrian Mathematics Olympiad)
6. Let d be a positive integer, and let S be the set of all positive integers
of the form x2 + dy 2 , where x and y are non-negative integers.
(a) Prove that if a ∈ S and b ∈ S, then ab ∈ S.
(b) Prove that if a ∈ S and p ∈ S, such that p is a prime and p | a,
then a/p ∈ S.
(c) Assume that the equation x2 + dy 2 = p has a solution in non-
negative integers x and y, where p is a given prime. Show that if
d ≥ 2, then the solution is unique, and if d = 1, then there are
exactly two solutions.
2 GCD and LCM
The greatest common divisor of two positive integers a and b is the great-
est positive integer that divides both a and b, which we denote by gcd(a, b),
and similarly, the lowest common multiple of a and b is the least positive
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 or Stuvia-credit 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 $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
79978 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now