5 Number Theory.................................................
This chapter on number theory is truly elementary, although its problems are far from
easy. (In fact, here, as elsewhere in the book, we tried to follow Felix Klein’s advice:
“Don’t ever be absolutely boring.’’)^1 We avoided the intricacies of algebraic number
theory, and restricted ourselves to some basic facts about residue classes and divisibility:
Fermat’s little theorem and its generalization due to Euler, Wilson’s theorem, the Chinese
Remainder Theorem, and Polignac’s formula. From all Diophantine equations we discuss
linear equations in two variables and two types of quadratic equations: the Pythagorean
equation and Pell’s equation.
But first, three sections for which not much background is necessary.
5.1 Integer-Valued Sequences and Functions...........................
5.1.1 Some General Problems...................................
Here are some problems, not necessarily straightforward, that use only the basic properties
of integers.
Example.Find all functionsf:{ 0 , 1 , 2 ,...}→{ 0 , 1 , 2 ,...}with the property that for
everym, n≥0,
2 f(m^2 +n^2 )=(f (m))^2 +(f (n))^2.Solution.The substitutionm=n=0 yields
2 f( 02 + 02 )=(f ( 0 ))^2 +(f ( 0 ))^2 ,and this givesf( 0 )^2 =f( 0 ), hencef( 0 )=0orf( 0 )=1.
(^1) Seien Sie niemals absolut langweilig.