Exam (elaborations)
Problems in Elementary Number Theory
- Institution
- Nursing 220 Final Exam Review
Problems in Elementary Number Theory
[Show more]
Seller
Follow
Content preview
Problems in Elementary Number TheoryPeter Vandendriessche
Hojoo Lee
July 11, 2007
God does arithmetic. C. F. Gauss
,Chapter 1
Introduction
The heart of Mathematics is its problems. Paul Halmos
Number Theory is a beautiful branch of Mathematics. The purpose of this book is to present
a collection of interesting problems in elementary Number Theory. Many of the problems
are mathematical competition problems from all over the world like IMO, APMO, APMC,
Putnam and many others. The book has a supporting website at
http://www.problem-solving.be/pen/
which has some extras to offer, including problem discussion and (where available) solutions,
as well as some history on the book. If you like the book, you’ll probably like the website.
I would like to stress that this book is unfinished. Any and all feedback, especially about
errors in the book (even minor typos), is appreciated. I also appreciate it if you tell me about
any challenging, interesting, beautiful or historical problems in elementary number theory
(by email or via the website) that you think might belong in the book. On the website you
can also help me collecting solutions for the problems in the book (all available solutions will
be on the website only). You can send all comments to both authors at
peter.vandendriessche at gmail.com and ultrametric at gmail.com
or (preferred) through the website.
The author is very grateful to Hojoo Lee, the previous author and founder of the book, for
the great work put into PEN. The author also wishes to thank Orlando Doehring , who
provided old IMO short-listed problems, Daniel Harrer for contributing many corrections
and solutions to the problems and Arne Smeets, Ha Duy Hung , Tom Verhoeff , Tran
Nam Dung for their nice problem proposals and comments.
Lastly, note that I will use the following notations in the book:
Z the set of integers,
N the set of (strictly) positive integers,
N0 the set of nonnegative integers.
Enjoy your journey!
1
,Contents
1 Introduction 1
2 Divisibility Theory 3
3 Arithmetic in Zn 17
3.1 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Primes and Composite Numbers 22
5 Rational and Irrational Numbers 27
5.1 Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Irrational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Diophantine Equations 33
7 Functions in Number Theory 43
7.1 Floor Function and Fractional Part Function . . . . . . . . . . . . . . . . . . 43
7.2 Divisor Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.3 Functional Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8 Sequences of Integers 52
8.1 Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
8.2 Recursive Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
8.3 More Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
9 Combinatorial Number Theory 62
10 Additive Number Theory 70
11 Various Problems 76
11.1 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
11.2 The Geometry of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
11.3 Miscellaneous problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
12 References 84
2
, Chapter 2
Divisibility Theory
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful.
If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t
beautiful, nothing is. Paul Erdös
A 1. Show that if x, y, z are positive integers, then (xy + 1)(yz + 1)(zx + 1) is a perfect
square if and only if xy + 1, yz + 1, zx + 1 are all perfect squares.
Kiran S. Kedlaya
A 2. Find infinitely many triples (a, b, c) of positive integers such that a, b, c are in arithmetic
progression and such that ab + 1, bc + 1, and ca + 1 are perfect squares.
AMM, Problem 10622, M. N. Deshpande
A 3. Let a and b be positive integers such that ab + 1 divides a2 + b2 . Show that
a2 + b2
ab + 1
is the square of an integer.
IMO 1988/6
A 4. If a, b, c are positive integers such that
0 < a2 + b2 − abc ≤ c,
show that a2 + b2 − abc is a perfect square. 1
CRUX, Problem 1420, Shailesh Shirali
A 5. Let x and y be positive integers such that xy divides x2 + y 2 + 1. Show that
x2 + y 2 + 1
= 3.
xy
1 a2 +b2
This is a generalization of A3 ! Indeed, a2 + b2 − abc = c implies that ab+1
= c ∈ N.
3
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.56. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67096 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