文档介绍：i
”God made the integers, all else is the work of man.”
Leopold Kronecker
ii
NUMBER THEORY
Structures, Examples, and Problems
Titu Andreescu Dorin Andrica
Contents
Foreword 7
Acknowledgments 9
Notation 11
I STRUCTURES, EXAMPLES,
AND PROBLEMS 13
1 Divisibility 15
Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Prime numbers . . . . . . . . . . . . . . . . . . . . . . . . . 21
The mon divisor . . . . . . . . . . . . . . . . . 30
Odd and even . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Modular arithmetics . . . . . . . . . . . . . . . . . . . . . . 42
Chinese remainder theorem . . . . . . . . . . . . . . . . . . 47
Numerical systems . . . . . . . . . . . . . . . . . . . . . . . 50
Representation of integers in an arbitrary base . . . 50
Divisibility criteria in the decimal system . . . . . . 51
2 Contents
2 Powers of Integers 61
Perfect squares . . . . . . . . . . . . . . . . . . . . . . . . . 61
Perfect cubes . . . . . . . . . . . . . . . . . . . . . . . . . . 70
kth powers of integers, k 4 . . . . . . . . . . . . . . . . . . 72
≥
3 Floor Function and Fractional Part 77
General problems . . . . . . . . . . . . . . . . . . . . . . . . 77
Floor function and integer points . . . . . . . . . . . . . . . 83
An useful result . . . . . . . . . . . . . . . . . . . . . . . . . 88
4 Digits of Numbers 91
The last digits of a number . . . . . . . . . . . . . . . . . . 91
The sum of the digits of a number . . . . . . . . . . . . . . 94
Other problems involving digits . . . . . . . . . . . . . . . . 100
5 Basic Principles in Number Theory 103
Two simple principles . . . . . . . . . . . . . . . . . . . . . 103
Extremal arguments . . . . . . . . . . . . . . . . . . 103
Pigeonhole principle . . . . . . . . . . . . . . . . . . 105
Mathematical induction . . . . . . . . . . . . . . . . . . . . 1