文档介绍：Number Theory for Mathematical Contests
David A. SANTOS
August 13, 2005 REVISION
Contents
Preface iii 5 Linear Diophantine Equations 48
Euclidean Algorithm . . . . . . . . . . . . . 48
1 Preliminaries 1 Practice . . . . . . . . . . . . . . . . . . . . . . . 50
Introduction . . . . . . . . . . . . . . . . . . 1 Linear Congruences . . . . . . . . . . . . . . 51
Well-Ordering . . . . . . . . . . . . . . . . . 1 Practice . . . . . . . . . . . . . . . . . . . . . . . 52
A theorem of Frobenius . . . . . . . . . . . . 52
Practice . . . . . . . . . . . . . . . . . . . . . . . 3
Practice . . . . . . . . . . . . . . . . . . . . . . . 54
Mathematical Induction . . . . . . . . . . . . 3 Chinese Remainder Theorem . . . . . . . . . 55
Practice . . . . . . . . . . . . . . . . . . . . . . . 7 Practice . . . . . . . . . . . . . . . . . . . . . . . 56
i Numbers . . . . . . . . . . . . . . 9
Practice . . . . . . . . . . . . . . . . . . . . . . . 11 6 Number-Theoretic Functions 57
Greatest Integer Function . . . . . . . . . . . 57
Pigeonhole Principle . . . . . . . . . . . . . 13
Practice . . . . . . . . . . . . . . . . . . . . . . . 60
Practice . . . . . . . . . . . . . . . . . . . . . . . 14 De Polignac’s Formula . . . . . . . . . . . . 62
Practice . . . . . . . . . . . . . . . . . . . . . . . 64
2 Divisibility 17 Sequences . . . . . . . . . . 64
Divisibility . . . . . . . . . . . . . . . . . . 17 Practice . . . . . . . . . . . . . . . . . . . . . . . 65
Practice . . . . . . . . . . . . . . . . . . . . . . . 18 Arithmetic Functions . . . . . . . . . . . . . 66
Division Algorithm . . . . . . . . . . . . . . 19 Practice . . . . . . . . . . . . . . . . . . . . . . . 68
Practice . . . . . . . . . . . . . . . . . . . . . . . 20 Euler’s Function. Reduced Residues . . . . . 69
Some Algebraic Identities . . . . . . . . . . . 21 Practice . . . . . . . . . . . .