Foreword

The International Mathematics Olympiad (IMO), in the last two decades,
has become an international institution with an impact in most countries
throughout the world, fostering young mathematical talent and promoting acertain approach to complex, yet basic, mathematics. It lays the ground foran open, unspecialized understanding of the field to those dedicated to thisancient art.
The tradition of mathematical competitions is sometimes traced back tonational contests which were organized in some countries of central Europe
already at the beginning of the last century. It is very likely that a slightvariation of the understanding of mathematical competition would reveal evenmore remote ancestors of the present IMO. It is, however, a fact that thepresent tradition was born after World War II in a divided Europe when thefirst IMO took place in Bucharest in 1959 among the countries of the Eastern
Block. As an urban legend would have it, it came about when a high schoolmathematics teacher from a small Romanian town began to pursue his vision
for an organized event that would help improve the teaching of mathematics.
Since the early beginnings, mathematical competitions of the international
olympiad type have established their own style of problems, which do not
require wide mathematical background and are easy to state. These problems
are nevertheless difficult to solve and require imagination plus a high degree oforiginal thinking. The Olympiads have reached full maturity and worldwide
status in the last two decades. There are presently over 100 participating
countries.
Accordingly, quite a few collections of Olympiad problems have been
published by various major publishing houses. These collections include
problems from past olympic competitions or from among problems proposedby various participating countries. Through their variety and required detailof solution, the problems offer valuable training for young students and acaptivating source of challenges for the mathematically interested adult.
In the so-called Hall of Fame of the IMO, which includes numerous
presently famous mathematicians and several Fields medalists, one finds axForeword

list of the participants and results of former mathematical olympiads (see[HF]). We find in the list of the participants for Greece, in the year 2003, thename of Michael Th. Rassias. At the age of 15 at that time, he won a silver
medal and achieved the highest score on the Greek team. He was the first
Greek of such a young age in over a decade, to receive a silver medal. He is
the author of the present book: one more book of Olympiad Problems among
other similar beautiful books.
Every single collection adds its own accent and focus. The one at hand
has a few particular characteristics which make it unique among similar
problem books. While most of these books have been written by experienced
mathematicians after several decades of practicing their skills as a profession, Michael wrote this present book during his undergraduate years in theDepartment of Electrical and Computer Engineering of the National Technical University of Athens. It is composed of some number theory fundamentals
and also includes some problems that he undertook while training for theolympiads. He focused on problems of number theory, which was the field ofmathematics that began to capture his passion. It appears like a confessionof a young mathematician to students of his age, revealing to them some ofhis preferred topics in number theory based on solutions of some particularproblems—most of which also appear in this collection. Michael does not limit
himself to just those particular problems. He also deals with topics in classicalnumber theory and provides extensive proofs of the results, which read like“all the details a beginner would have liked to find in a book” but are often
omitted.
In this spirit, the book treats Legendre symbols and quadratic reciprocity,
the Bertrand Postulate, the Riemann ζ-function, the Prime Number Theorem,
arithmetic functions, diophantine equations, and more. It offers pleasantreading for young people who are interested in mathematics. They will be
guided to an easy comprehension of some of the jewels of number theory. The
problems will offer them the possibility to sharpen their skills and to apply
the theory.
After an introduction of the principles, including Euclid’s proof of theinfinity of the set of prime numbers, follows a presentation of the extended
Euclidean algorithm in a simple matricial form known as the Blankinshipmethod. Unique factorization in the integers is presented in full detail, giving
thus the basics necessary for the proof of the same fact in principal ideal
domains. The next chapter deals with rational and irrational numbers andsupplies elegant comprehensive proofs of the irrationality of e and π, which
are a first taste of Rassias’s way of breaking down proofs in explicit, extendedsteps.
The chapter on arithmetic functions presents, along with the definition ofthe Möbius µ and Euler φ functions, the various sums of divisors!
σa (n) =da ,d|nForewordxi

as well as nice proofs and applications that involve the Möbius inversion
formula. We find a historical note on Möbius, which is the first of a sequenceof such notes by which the author adds a temporal and historical frame tothe mathematical material.
The third chapter is devoted to algebraic aspects, perfect numbers,
Mersenne and Fermat numbers, and an introduction to some open questions
related to these. The fourth deals with congruences, the Chinese Remainder
Theorem, and some results on the rings Z/(n · Z) in terms of congruences.
These results open the door to a large number of problems contained in thesecond part of the book.
Chapter 5 treats the symbols of Legendre and Jacobi and gives Gauss’s firstgeometric proof of the law of quadratic reciprocity. The algorithm of Solovayand Strassen—which was the seminal work leading to a probabilistic perspective of fundamental notions of number theory, such as primality—is described
as an application of the Jacobi symbol. The next chapters are analytic, introducing the ζ and Dirichlet series. They lead to a proof of the Prime NumberTheorem, which is completed in the ninth chapter. The tenth and eleventhchapters are, in fact, not only a smooth transition to the problem part of thebook, containing already numerous examples of solved problems, they also,
at the same time, lead up to some theorems. In the last two subsections of
the appendix, Michael discusses special cases of Fermat’s Last Theorem andCatalan’s conjecture.
I could close this introduction with the presentation of my favorite problem,
but instead I shall present and briefly discuss another short problem which isincluded in the present book. It is a conjecture that Michael Rassias conceivedof at the age of 14 and tested intensively on the computer before realizing its
intimate connection with other deep conjectures of analytic number theory.
These conjectures are still today considered as intractable.
Rassias Conjecture. For any prime p with p > 2 there are two primes p1 , p2 ,with p1 < p2 such thatp 1 + p2 + 1
p=.
(1)
p1
The conjecture was verified empirically on a computer and was publishedalong with a series of problems from international Olympiads (see [A]). The
purpose of this short note is to put this conjecture in its mathematical context
and relate it to further known conjectures.
At first glance, the expression (1) is utterly surprising and it could standfor some unknown category of problems concerning representation of primes.
Let us, though, develop the fraction in (1):(p − 1)p1 = p2 + 1.
Since p is an odd prime, we obtain the following slightly more general
conjecture: For all a ∈ N there are two primes p, q such thatxii

Foreword

2ap = q + 1.

(2)

Of course, if (2) admits a solution for any a ∈ N, then a fortiori (1) admits
a solution. Thus, the Rassias conjecture is true. The new question has theparticularity that it only asks to prove the existence of a single solution.
We note, however, that this question is related to some famous problems, inwhich one asks more generally to show that there is an infinity of primes
verifying certain conditions.
For instance, the question if there is an infinity of Sophie Germain primes
p, i.e., primes such that 2p + 1 is also a prime, has a similar structure. Whilein the version (2) of the Rassias conjecture, we have a free parameter a andsearch for a pair (p, q), in the Sophie Germain problem we may consider p itself
as a parameter subject to the constraint that 2p + 1 is prime, too. The factthat there is an infinity of Sophie Germain primes is an accepted conjecture,and one expects the density of such primes to be O(x/ ln2 (x)) [Du]. We obtainfrom this the modified Rassias conjecture by introducing a constant a as factorof 2 and replacing +1 by −1. Thus q = 2p + 1 becomes q = 2ap − 1, whichis (2). Since a is a parameter, in this case we do not know whether there are
single solutions for each a. When a is fixed, this may of course be verified on
a computer or symbolically.
A further related problem is the one of Cunningham chains. Given two
coprime integers m, n, a Cunningham chain is a sequence p1 , p2 , . . . , pk ofprimes such that pi+1 = mpi + n for i > 1. There are competitions for finding
the longest Cunningham chains, but we find no relevant conjectures related
to either length or frequencies of such chains. In relation to (2), one would
rather consider the Cunningham chains of fixed length 2 with m = 2a andn = −1. So the question (2) reduces to the statement: there are Cunningham
chains of length two with parameters 2a, −1, for any a ∈ N.
By usual heuristic arguments, one should expect that (2) has an infinityof solutions for every fixed a. The solutions are determined by one of p or q
via (2). Therefore, we may define
Sx = {p < ax : p is prime and verifies (2)}and the counting function πr (x) = |Sx |. There are O(ln(x)) primes p < x, and
2ap − 1 is an odd integer belonging to the class −1 modulo 2a. Assuming thatthe primes are equidistributed in the residue classes modulo 2a, we obtain theexpected estimate:πr (x) ∼ x/ ln2 (x)(3)

for the density of solutions to the extended conjecture (2) of Rassias.
Probably the most general conjecture on distribution of prime constellations is Schinzel’s Conjecture H :Conjecture H. Consider s polynomials fi (x) ∈ Z[X], i = 1, 2,". . . , s with posis
tive leading coefficients and such that the product F (X) = i=1 fi (x) is notForewordxiii

divisible, as a polynomial, by any integer different from ±1. Then there is atleast one integer x for which all the polynomials fi (x) take prime values.
Of course, the Rassias conjecture follows for s = 2 with f1 (x) = x andf2 (x) = 2ax − 1. Let us finally consider the initial problem. Can one provethat (2) has at least one solution in primes p, q, for arbitrary a? In [SW],Schinzel and Sierpiński show that Conjecture H can be stated for one value ofx or for infinitely many values of x, since the two statements are equivalent.
Therefore, solving the conjecture of Rassias is as difficult as showing that
there are infinitely many prime pairs verifying (2). Of course, this does not
exclude the possibility that the conjecture could be proved easier for certain
particular families of values of the parameter a.
The book is self-contained and rigorously presented. Various aspects of
it should be of interest to graduate and undergraduate students in number
theory, high school students and the teachers who train them for the Putnam
Mathematics Competition and Mathematical Olympiads as well as, naturally,
to scholars who enjoy learning more about number theory.

Bibliography[A] T Andreescu and D. Andrica, Number Theory, Birkhäuser, Boston,(2009), p. 12.
[Du] H Dubner, Large Sophie-Germain primes, Math. Comp., 65(1996),
pp. 393–396.
[HF] http://www.imo-official.org/country− hall.aspx?code=HEL[R] Michael Th. Rassias, Open Problem No. 1825, Octogon Mathematical
Magazine, 13(2005), p. 885. See also Problem 25, Newsletter of theEuropean Mathematical Society, 65(2007), p. 47.
[SW] A Schinzel and W. Sierpiński, Sur certaines hypothèses concernant lesnombres premiers, Acta Arith., 4(1958), pp. 185–208.

Preda Mihăilescu
Mathematics Institute
University of Göttingen
Germany