3.

PRIME NUMBERS 25

3. Prime Numbers
(135) Using computer software, write a program
(a) to generate all Mersenne primes up to 2525 − 1;
(b) to determine the smallest prime number larger than 10100 + 1.
(136) Write a program that generates prime numbers up to a given number N .
One can, of course, use Eratosthenes’ sieve.
(137) Use a computer to find four consecutive integers having the same number
of prime factors (allowing repetitions).
(138) (a) By reversing the digits of the prime number 1009, we obtain the num-
ber 9001, which is also prime. Write a program to find the prime numbers
in [1,10000] verifying this property.
(b) By reversing the digits of the prime number 163, we obtain the number
361, which is a perfect square. Using computer software, write a program
to find all prime numbers in [1, 10000] with this property.
(139) Using a computer, find all prime numbers p ≤ 10 000 with the property
that p, p + 2 and p + 6 are all primes.
(140) Let pk be the k-th prime number. Show that pk < 2k if k ≥ 2.
(141) If a prime number pk > 5 is equally isolated from the prime numbers
appearing before and after it, that is pk − pk−1 = pk+1 − pk = d, say, show
that d is a multiple of 6. Then, for each of the cases d = 6, 12 and 18, find,
by using a computer, the smallest prime number pk with this property.
(142) Prove that none of the numbers

12321, 1234321, 123454321, 12345654321, 1234567654321,

123456787654321, 12345678987654321
is prime.
(143) For each integer k ≥ 1, let nk be the k-th composite number, so that for
instance n1 = 4 and n10 = 18. Use computer software and an appropriate
algorithm in order to establish the value of nk , with k = 10α , for each
integer α ∈ [2, 10].
(144) For each integer k ≥ 1, let nk be the k-th number of the form pα , where
p is prime, α a positive integer, so that for instance n1 = 2 and n10 = 16.
Use computer software and an appropriate algorithm in order to establish
the value of nk , with k = 10α , for each integer α ∈ [2, 10].
(145) Find all positive integers n < 100 such that 2n + n2 is prime. To which
class of congruence modulo 6 do these numbers n belong?
(146) Show that if the integer n ≥ 4 is not an odd multiple of 9, then the
corresponding number an := 4n + 2n + 1 is necessarily composite. Then,
use a computer in order to find all positive integers n < 1000 for which
an is prime.
(147) Consider the sequence (an ) defined by a1 = a2 = 1 and, for n ≥ 3, by
an = n! − (n − 1)! + · · · + (−1)n 2! + (−1)n+1 1! . Use a computer in order
to find the smallest number n such that an is a composite number.
(148) The mathematicians Minác and Willans have obtained a formula for the
n-th prime number pn which is more of a theoretical interest than of a
26 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

practical interest:
⎡⎡ ⎤1/n ⎤

2n
⎢⎣
pn = 1 + ⎣
n
⎦ ⎥ ⎦,
m (j−1)!+1 (j−1)!
m=1 1+ j=2 j − j

where as usual [x] stands for the largest integer ≤ x. Prove this formula.
(149) Develop an idea used by Paul Erdős (1913–1996) to show that, for each
integer n ≥ 1,
p ≤ 4n .
p≤n
His idea was to write
p= p· p
p≤n p≤ n+1
2
n+1
2 <p≤n

and to use the fact that each prime number p > (n+ 1)/2 appears in the
n
factorization of the binomial coefficient . Provide the details.
(n + 1)/2
(150) Show that if four positive integers a, b, c, d are such that ab = cd, then the
number a2 + b2 + c2 + d2 is necessarily composite.
(151) Show that, for each integer n ≥ 1, the number 4n3 + 6n2 + 4n + 1 is
composite.
(152) Show that if p and q are two consecutive odd prime numbers, then p + q
is the product of at least three prime numbers (not necessarily distinct).
(153) Does there exist a positive integer n such that n/2 is a perfect square, n/3
a cube and n/5 a fifth power?
(154) Given any integer n ≥ 2, show that n42 − 27 is never a prime number.
(155) Let θ(x) := p≤x log p. Prove that Bertrand’s Postulate follows from the
fact that
c1 x < θ(x) < c2 x,
where c1 = 0.73 and c2 = 1.12.
(156) Use Bertrand’s Postulate to show that, for each integer n ≥ 4,
p2n+1 < p1 p2 · · · pn ,
where pn stands for the n-th prime number.
(157) Certain integers n ≥ 3 can be written in the form n = p + m2 , with p
prime and m ∈ N. This is the case for example for the numbers 3, 4, 6, 7,
8, 9, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21. Let q r be a prime power, where
r is a positive even integer such that 2q r/2 − 1 is composite. Show that
q r cannot be written as q r = p + m2 , with p prime and m ∈ N.
(158) Show that if p and 8p − 1 are primes, then 8p + 1 is composite.
(159) Show that all positive integers of the form 3k + 2 have a prime factor of
the same form, that all positive integers of the form 4k + 3 have a prime
factor of the same form, and finally that all positive integers of the form
6k + 5 have a prime factor of the same form.
(160) A positive integer n has a Cantor expansion if it can be written as
n = am m! + am−1 (m − 1)! + · · · + a2 2! + a1 1!,
where the aj ’s are integers satisfying 0 ≤ aj ≤ j.
(a) Find the Cantor expansion of 23 and of 57.
3. PRIME NUMBERS 27

(b) Show that all positive integers n have a Cantor expansion and more-
over that this expansion is unique.
(161) If p > 1 and d > 0 are integers, show that p and p + d are both primes if
and only if

1 (−1)d d! 1 1
(p − 1)! + + +
p p+d p p+d

is an integer.
(162) Find all prime numbers p such that p + 2 and p2 + 2p − 8 are primes.
(163) Is it true that if p and p2 + 8 are primes, then p3 + 4 is prime? Explain.
(164) Let n ≥ 2. Show that the integers n and n + 2 form a pair of twin primes
if and only if

4 ((n − 1)! + 1) + n ≡ 0 (mod n(n + 2)).

(165) Identify each prime number p such that 2p + p2 is also prime.

(166) For which prime number(s) p is 17p + 1 a perfect square?
(167) Given two integers a and b such that (a, b) = p, where p is prime, find all
possible values of:
(a) (a2 , b); (b) (a2 , b2 ); (c) (a3 , b); (d) (a3 , b2 ).
(168) Given two integers a and b such that (a, p2 ) = p and (b, p4 ) = p2 , where p
is prime, find all possible values of:
(a) (ab, p5 ); (b) (a + b, p4 ); (c) (a − b, p5 ); (d) (pa − b, p5 ).
(169) Given two integers a and b such that (a, p2 ) = p and (b, p3 ) = p2 , where p
is a prime number, evaluate the expressions (a2 b2 , p4 ) and (a2 + b2 , p4 ).
(170) Let p be a prime number and a, b, c be positive integers. For each of the
following statements, say if is true or false. If it is true, give a proof; if it
is false, provide a counter-example.
(a) If p|a and p|(a2 + b2 ), then p|b.
(b) If p|an , n ≥ 1, then p|a.
(c) If p|(a2 + b2 ) and p|(b2 + c2 ), then p|(a2 − c2 ).
(d) If p|(a2 + b2 ) and p|(b2 + c2 ), then p|(a2 + c2 ).
(171) Let a, b and c be positive integers. Show that abc = (a, b, c)[ab, bc, ac] =
(ab, bc, ac)[a, b, c].
(172) Let a, b and c be positive integers and assume that abc = (a, b, c)[a, b, c].
Show that this necessarily implies that (a, b) = (b, c) = (a, c) = 1.
(a, b)(b, c)(a, c)
(173) Let a, b and c be positive integers. Show that (a, b, c) =
(ab, bc, ac)
abc (a, b, c)
and that [a, b, c] = .
(a, b)(b, c)(a, c)
(174) Let a, b and c be positive integers. Show that

[a, b, c]2 (a, b, c)2

= .
[a, b][b, c][c, a] (a, b)(b, c)(c, a)

(175) Find three positive integers a, b, c such that

√
[a, b, c] · (a, b, c) = abc.
28 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

(176) Let #n = [1, 2, 3, . . . , n] be the lowest common multiple of the numbers

1, 2, . . . , n. Show that
p ≤ #n = p[log n/ log p] .
p≤n p≤n

(177) Let p be a prime number and r a positive integer. What are the possible
values of (p, p + r) and of [p, p + r]?
(178) Let p > 2 be a prime number such that p|8a − b and p|8c − d, where
a, b, c, d ∈ Z. Show that p|(ad − bc).
(179) Show that, if {p, p + 2} is a pair of twin primes with p > 3, then 12 divides
the sum of these two numbers.
(180) Let n be a positive integer. Show that if n is a composite integer, then
n|(n − 1)! except when n = 4.
(181) For which positive integers n is it true that
n
n

j j?
j=1 j=1

(182) Let π = 3.141592 . . . be Archimede’s constant, and for each positive real
number x, let π2 (x) be the function that counts the number of pairs of
twin primes {p, p + 2} such that p ≤ x. Show that

π n! π (n − 2)!
π2 (x) = 2 + sin (n + 2) · sin n ,
2 n+2 2 n
7≤n≤x

where [y] stands for the largest integer ≤ y.

(183) Given an integer n ≥ 2, show, without using Bertrand’s Postulate, that
there exists a prime number p such that n < p < n! .
(184) In 1556, Niccòlo Tartaglia (1500–1557) claimed that the sums
1 + 2 + 4, 1 + 2 + 4 + 8, 1 + 2 + 4 + 8 + 16, . . .
stood successively for a prime number and a composite number. Was he
right?
(185) Show that if an − 1 is prime for certain integers a > 1 and n > 1, then
a = 2 and n is prime.

Remark: The integers of the form 2p − 1, where p is prime, are called

Mersenne numbers. We denote them by Mp in memory of Marin Mersenne
(1588–1648), who had stated that Mp is prime for
p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257
and composite for all the other primes p < 257. This assertion of Mersenne
can be found in the preface of his book Cogita Physico-mathematica, pub-
lished in Paris in 1644. Since then, we have found a few errors in the com-
putations of Mersenne: indeed Mp is not prime for p = 67 and p = 257,
while Mp is prime for p = 61, p = 89 and p = 109. One can find in the
appendix C of the book of J.M. De Koninck and A. Mercier [8] the list
of Mersenne primes Mp corresponding to the prime numbers p satisfying
2 ≤ p ≤ 44 497. Note on the other hand that it has recently been discovered
that 232 582 657 − 1 is prime (in September 2006), which brings to 44 the
total number of known Mersenne primes. It is also known that the primes
3. PRIME NUMBERS 29

Mp are closely related to the perfect numbers, in the sense that, as

was shown by Leonhard Euler (1707–1783), n is an even perfect number
if and only if n = 2p−1 (2p − 1), where 2p − 1 is a Mersenne prime.
(186) Show that if there exists a positive integer n and an integer a ≥ 2 such
that an + 1 is prime, then a is even and n = 2r for a certain positive
integer r.
k
Remark: The prime numbers of the form 22 + 1, k = 0, 1, 2, . . ., are
called “Fermat primes”. The reason is that Pierre de Fermat claimed in
1640 (although saying he could not prove it) that all the numbers of the
k
form 22 + 1 are prime. One hundred years later, Euler proved that
5
22 + 1 = 4294967297 = 641 · 6700417.

As of today, we still do not know if, besides the cases k = 0, 1, 2, 3, 4,

k k
primes of the form 22 + 1 exist. Nevertheless, it is known that 22 +
1 is composite for 5 ≤ k ≤ 32; see H.C. Williams [41] and the site
www.prothsearch.net/fermat.html.
z
(187) Show that the equation (2x − 1)(2y − 1) = 22 + 1 is impossible for positive
integers x, y and z. (This implies in particular that a Fermat number, that
k
is a number of the form 22 + 1, cannot be the product of two Mersenne
numbers.)
(188) Prove by induction that, for each integer n ≥ 1,
F0 F1 F2 · · · Fn−1 = Fn − 2,
i
where Fi = 22 + 1, i = 0, 1, 2, . . . .
(189) Use the result of problem 188 in order to prove that if m and n are distinct
positive integers, then (Fm , Fn ) = 1.
(190) A positive integer n is said to be pseudoprime in basis a ≥ 2 if it is
composite and if an−1 ≡ 1 (mod n). Find the smallest number which is
pseudoprime in each of the bases 2, 3, 5 and 7.
(191) Use Problem 189 to prove that there exist infinitely many primes.
n
(192) Consider the numbers fn = 23 + 1, n = 1, 2, . . ., and show they are all
composite and in particular that, for each positive integer n,
(a) 3n+1 |fn ; (b) p|fn ⇒ p|fn+1 .
(193) Show that there exist infinitely many prime numbers p such that the
numbers p − 2 and p + 2 are both composite.
5
(194) Show that 641 divides F5 = 22 + 1 without doing the explicit division.
(195) Use an induction argument in order to prove that each Fermat number
n
Fn = 22 + 1, where n ≥ 2, ends with the digit 7.
(196) Let n be a positive integer and consider the set E = {1, 2, . . . , n}. Let
2k be the largest power of 2 which belongs to E. Show that for all m ∈
n
E \ {2k }, we have 2k | m. Using this result, show that j=1 1/j is not an
integer if n > 1.
(197) Show that, for each positive integer n, one can find a prime number p < 50
such that p|(25n − 1).
(198) Show that the integers defined by the sequence of numbers
Mk = p1 p2 · · · pk + 1 (k = 1, 2, . . .),
30 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

where pj stands for the j–th prime number, are prime numbers for 1 ≤
k ≤ 5 and composite numbers for k = 6, 7. What about M8 , M9 and
M10 ?
(199) Use the proof of Euclid’s Theorem on the infinitude of primes to show
r−1
that, if we denote by pr the r-th prime number, then pr ≤ 22 for each
r ∈ N.
(200) In Problem 199, we obtained an upper bound for pr , the r-th prime num-
r−1
ber, namely pr ≤ 22 . Use this inequality to obtain a lower bound for
π(x), the number of prime numbers ≤ x. More precisely, show that, for
x ≥ 3, π(x) ≥ log log x.
(201) Show that there exist infinitely many prime numbers of the form 4n + 3.
(202) Show that there exist infinitely many prime numbers of the form 6n + 5.
(203) Let f : N → R be the function defined by
f (x) = ar xr + ar−1 xr−1 + · · · + a1 x + a0 ,
where ar = 0 and where each ai , 0 ≤ i ≤ r, is an integer. Show that, by
an appropriate choice of ai , 0 ≤ i ≤ r, the set {f (n) : n ∈ N} contains at
least r prime numbers.
(204) Consider the positive integers which can be written as an alternating
sequence of 0’s and 1’s. The number 101 010 101 is such a number and
observe that 101 010 101 = 41 · 271 · 9091. Besides 101, do there exist other
prime numbers of this form?
n
(205) Find all prime numbers of the form 22 + 5, where n ∈ N. Would the
question be more difficult if one replaces the number 5 by another number
of the form 3k + 2? Explain.
(206) The largest gaps between two consecutive prime numbers pr < pr+1 < 100
occur successively when
pr+1 − pr = 5 − 3 = 2,
pr+1 − pr = 11 − 7 = 4,
pr+1 − pr = 29 − 23 = 6,
pr+1 − pr = 97 − 89 = 8.
Is it true that these constantly increasing gaps always occur by jumps of
length 2? In other words, does the first gap of length 2k always occur
before the first gap of length 2k + 2?
∞
1
(207) Show that < 1, where the inner sum runs over all the prime
α=2 p
pα
numbers p.
(208) Let
1 1 1
f (x) = π(x) + π(x1/2 ) + π(x1/3 ) + π(x1/4 ) + · · · ,
2 3 4
be a series which is in fact a finite sum for each real number x ≥ 1 since
π(x1/n ) = 0 as soon as n > log x/ log 2. Show that
∞
µ(n)
π(x) = f (x1/n ).
n=1
n
3. PRIME NUMBERS 31

Remark: It is possible$ x to show that f (x) is a better approximation of

dt
π(x) than Li(x) := (see H. Riesel [31]).
2 log t
(209) Let n ≥ 2 be an integer. Show that the interval [n, 2n] contains at least
one perfect square.
(210) If n is a positive integer such that 3n2 − 3n + 1 is composite, show that n3
cannot be written as n3 = p + m3 , with p prime and m a positive integer.
(211) It is conjectured that there exist infinitely many prime numbers p of the
form p = n2 + 1. Identify the primes p < 10 000 of this particular form.
Why is the last digit of such a prime number p always 1 or 7? Is there
any reasonable explanation for the fact that the digit 7 appears essentially
twice as often?
(212) Show that, for each integer n ≥ 2,
1
(n!)1/n ≤ p p−1 .
p≤n

(213) For each integer N ≥ 1, let SN = {n2 + 2 : 6 ≤ n ≤ 6N }. Show that no

more than 16 of the elements of SN are primes.
(214) Let p be a prime number and consider the integer N = 2 · 3 · 5 · · · p. Show
that the (p − 1) consecutive integers

N + 2, N + 3, N + 4, . . . , N + p

are composite.
(215) Let n > 1 be an integer with at least 3 digits. Show that
(a) 2|n if and only if the last digit of n is divisible by 2;
(b) 22 |n if and only if the number formed with the last two digits of n is
divisible by 4;
(c) 23 |n if and only if the number formed with the last three digits of n
is divisible by 8.
Can one generalize?
(216) For each integer n ≥ 2, let

1
P (n) = 1− .
p
p|n
p>log n

Show that lim P (n) = 1.

n→∞
(217) Prove that there exists an interval of the form [n2 , (n + 1)2 ] containing at
least 1000 prime numbers.
(218) Use the Prime Number Theorem (see Theorem 17) in order to prove that
the set of numbers of the form p/q (where p and q are primes) is dense in
the set of positive real numbers.
(219) Show that the sum of the reciprocals of a finite number of distinct prime
numbers cannot be an integer.
(220) Use the fact that there exists a positive constant c such that if x ≥ 100,
1 1
(1) = log log x + c + R(x) with |R(x)| <
p log x
p≤x
32 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

and moreover that, for x ≥ 2,

3 x
(2) π(x) := 1<
2 log x
p≤x

in order to prove that if P (n) stands for the largest prime factor of n, then
1 √ 9 1
(3) #{n ≤ x : P (n) > x} = log 2 + T (x) with |T (x)| < .
x 2 log x
Use this result to show that more than 23 of the integers have their largest
prime factor larger than their square root, or in√ other words that the
density of the set of integers n such that P (n) > n is larger than 23 .
(221) Prove the following formula (due to Adrien-Marie Legendre (1752–1833)):
√ x
π(x) = π( x) + µ(n) − 1,
n
n|p1 ···pr
√
where r = π( x).
(222) Consider the following two conjectures:
A. (Goldbach Conjecture) Each even integer ≥ 4 can be written as the
sum of two primes.
B. Each integer > 5 can be written as the sum of three prime numbers.
Show that these two conjectures are equivalent.
(223) Show that π(m), the number of prime numbers not exceeding the positive
integer m, satisfies the relation
m
(j − 1)! + 1 (j − 1)!
π(m) = − ,
j=2
j j

where [y] stands for the largest integer ≤ y.

(224) Given a sequence of natural numbers A, let A(n) = #{m ≤ n : m ∈ A},
and let us denote respectively by
A(n) A(n)
d A = lim inf and d A = lim sup
n→∞ n n→∞ n
the asymptotic lower density and asymptotic upper density of the sequence
A. On the other hand, if both these densities are equal, we say that the
sequence A has density d A = dA = dA. Prove that:
(a) the density of the sequence made up of all the multiples of a natural
number a is equal to 1/a;
(b) the density of the sequence made up of all the multiples of a natural
number a which are not divisible by the natural number a0 is equal
1 1
to − ;
a [a, a0 ]
(c) the density of the sequence made up of all natural numbers which
are not divisible by any of the prime numbers q1 , q2 , . . . , qr is equal
r
1
to 1− .
i=1
qi
(225) Let A be the set of natural numbers n such that 22k ≤ n < 22k+1 for a
certain integer k ≥ 0, so that
A = {1, 4, 5, 6, 7, 16, 17, . . . , 31, 64, 65, . . . , 127, 256, 257, . . .}.
3. PRIME NUMBERS 33

Show that
d A = d A.
(226) We say that a sequence of natural numbers A is primitive if no element of
A divides another one. Examples of such sequences are: the sequence of
prime numbers, the sequence of natural numbers having exactly k prime
factors (k fixed), and finally the sequence of integers n belonging to the
interval ]k, 2k] (k fixed). Show that if A is a primitive sequence, then
d A ≤ 12 .
(227) Let A be a primitive sequence (see Problem 226). Show that
1
< +∞.
a log a
a∈A
√
(228) Let E = {a + b −5 | a, b ∈ Z}.
(a) Show that the sum and the product of elements of √ E are in E.
(b) Define the norm of an element z ∈ E by z = a+b −5 = a2 +5b2 .
We say that an element p ∈ E is prime if it is impossible to write
p = n1 n2 , with n1 , n2 ∈ E, n1 > 1, n2 > 1; we say that it is
composite if it is not prime. Show that, in E, 3 is a prime number
and 29 is a composite number.
(c) Show that the factorization of 9 in E is not unique.
(229) Let A be a set of natural numbers and let A(x) = #{n ≤ x : n ∈ A}.
Show that, for all x ≥ 1,
1 A(n) A(x)
= + .
n n(n + 1) [x] + 1
n≤x n≤x
n∈A
128 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

(132) (Contribution of Imre Kátai, Budapest). Let

n
(1) (2) (1) (3)
S := (aj + aj )(aj + aj ).
j=1

Then,

n
(1)

n
(1) (3)

n
(2) (1)

n
(2) (3)
S= (aj )2 + aj aj + aj aj + aj aj = n.
j=1 j=1 j=1 j=1

(1) (2) (1) (3)

But since it is clear that the expression (aj +aj )(aj +aj ) is a multiple
of 4, the result follows.
(133) In order to show that a series made up of nonnegative real numbers con-
verges, we only need to bound it by a series which converges. So let (n)
be the number of digits of the positive integer n, in its decimal represen-
tation. We first observe that, for each positive integer r, we have

1 = 8 · 9r−1 .
n∈A
(n)=r

Hence, it follows from this that

1 ∞ ∞

1 1
= < r−1
1
n r=1 n∈A n r=1 10
n∈A n∈A
(n)=r (n)=r

∞
∞ r−1
8 · 9r−1 9
= =8 = 80,
r=1
10r−1 r=1
10
from which the result follows.
(134) If a > b, it is clear that a − b ≥ (a, b), and we know that (a, b)[a, b] = ab.
Hence, since
(un+1 − un )[un+1 , un ] ≥ (un+1 , un )[un+1 , un ] = un+1 · un ,
we obtain
1 un+1 − un 1 1
≤ = − .
[un+1 , un ] un+1 · un un un+1
Therefore the series is bounded above by a convergent series and this is
why it converges.
(135) (a) With Maple, we have > for i from 3 by 2 to 525 do
> if isprime(2∧ i-1)
> then print(2∧ i-1, ‘ is a prime number ‘)
> else fi; od;
(b) With Maple, we may use
> nextprime(10∧(100)+1);
We thus obtain the integer 10100 + 267.
(136) With Maple, the program below enumerates the first N (here N = 120)
prime numbers.
> for i to 120 do
> p.i :=ithprime(i) od;
For example, p.(1..120) gives the first 120 prime numbers.
SOLUTIONS 129

(137) In order to find four consecutive integers with the same number of prime
factors, we must use the function Ω. First we type in
> readlib(ifactors): with(numtheory):
and thereafter, we type in the following instructions:
> Omega:=n->sum(ifactors(n)[2][i][2],
> i=1..nops(factorset(n))):
> for n to 1000 do if Omega(n)=Omega(n+1) and
> Omega(n+1)=Omega(n+2) and Omega(n+2)=Omega(n+3)
> then print(n) else fi; od;
To find four consecutive integers having the same number of divisors, it
is enough to type in the instructions
> with(numtheory):
> for n to 1000 do
> if tau(n)=tau(n+1) and tau(n+1)=tau(n+2)
> and tau(n+2)=tau(n+3)
> then print(n) else fi; od;
(138) (a) With the procedure “return”, the search is easily done:
> return:=proc(n::integer)
> local m,s;
> m:=n; s:=0;
> while m<>0 do
> s:=10*s+irem(m,10);
> m:=iquo(m,10) od; s end:
And for our problem, we have the following procedure:
> invp:=proc(N::integer) local n;
> for n from 1 to N do if isprime(n)
> and isprime(return(n)) then
> print (n) fi; od; end:
Without the procedure “return”, we may proceed as follows:
> invp:=proc(N)
> for j from 169 to N do
> L:=convert(ithprime(j),base,10);# N <= 1229
> if type(1000*L[1]+100*L[2]+10*L[3]+L[4],prime)=true
> then print(ithprime(j)) else fi; od; end:

(b) > invp:=proc(N::integer)

> local n;
> for n from 1 to N do
> if isprime(n)=false then elif
> type(sqrt(return(n)),integer)=true
> then print(n) else fi; od; end:

If we do not use the procedure “return”, we may proceed as follows:

> invp:=proc(N) local j, L;

> for j from 26 to N
> do L:=convert(ithprime(j),base,10);# N <= 168
> if type(sqrt(100*L[1]+10*L[2]+L[3]),integer)=true then
> print(ithprime(j)) else fi; od; end:
130 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

or the following procedure:

> invp:=proc(N) local j, L;
> for j from 169 to N
> do L:=convert(ithprime(j),base,10);# N <= 1229
> if type(sqrt(1000*L[1]+100*L[2]+10*L[3]+L[4]),
> integer)=true
> then print(ithprime(j)) else fi; od; end:
(139) With Maple:
> for n from 3 by 2 to 10000 do
> if isprime(n) and isprime(n + 2) and isprime(n + 6)
> then print(n) else fi; od;
(140) We prove this result using induction on k. The result is immediate for
k = 2. Assume that the result is true for a certain integer k > 2, that is
for which we have pk < 2k . It is enough to show that pk+1 < 2k+1 . From
Bertrand’s Postulate, there exists a prime number between pk and 2pk , in
which case pk+1 < 2pk , and the result is proved.
(141) It is enough to show that d ≡ 2, 4 (mod 6). First of all, assume that d = 2:
if pk ≡ 1 (mod 3), then pk+1 = pk +2 ≡ 0 (mod 3), contradicting the fact
that pk+1 is prime; similarly if pk ≡ 2 (mod 3), then pk−1 = pk − 2 ≡ 0
(mod 3), contradicting the fact that pk−1 is prime. The same type of
contradiction emerges when we assume that d = 4. If d = 6k + 2 or 6k + 4
with k ≥ 1, the same argument works. For d = 6, it is p16 = 53; for
d = 12, it is p47 = 211; for d = 18, it is p2285 = 20 201.
Remark: It is interesting to observe that the gap d = 24 is reached earlier
than might be expected in the sequence of prime numbers, namely with
p1939 = 16 787.
(142) This statement follows from the fact that each of the listed numbers is a
perfect square, since
12321 = 1112 , 1234321 = 11112 , . . . ,
12345678987654321 = 1111111112 .
(143) Let k ≥ 2. Since each number ≤ nk is either 1, a prime number or else a
composite number, it is clear that
(1) nk = 1 + π(nk ) + k.
By using Mathematica and the program
n=1;Do[n=n+1;While[PrimePi[n]!=n-10^a-1,n++]; Print[10^a,
" ",n],{a,1,3}]
we obtain the table
10 18
100 133
1000 1197
This reveals that n10 = 18, n100 = 133 and n1000 = 1197. For values
of k larger than 1000, and to accelerate the computations, one can use
the approximation (guaranteed by the Prime Number Theorem) π(x) ≈
x x
log x + log2 x , so that (1) gives
nk nk
nk ≈ + +k
log nk log2 nk
SOLUTIONS 131

and therefore that

1 1
(2) nk 1 − − ≈ k,
log nk log2 nk
which in particular means that

(3) log nk ≈ log k.

Combining (2) and (3), we obtain the approximation

−1
1 1
(4) nk ≈ k · 1 − − .
log k log2 k

Setting sk (n) := 1 + π(n) + k − n, it follows that if a number n satisfies

sk (n) = 0, then n = nk .
First consider the case k = 104 . From (4), we have as a first approxi-
mation n104 ≈ 11 369. By using Mathematica and the program
n=11369;While[(a=s[n])!=0,n=n+a];Print[n]
where s(n) = s1000 (n), we obtain that n10000 = 11 374. Similarly, with
the approximation n105 ≈ 110 425, we obtain that n105 = 110 487. The
following is the table giving the values of n10α for 1 ≤ α ≤ 10.
α n10α α n10α
1 18 6 1 084 605
2 133 7 10 708 555
3 1 197 8 106 091 745
4 11 374 9 1 053 422 339
5 110 487 10 10 475 688 327
(144) Let k ≥ 2. Setting r = [log nk / log 2], it is clear that the number nk
satisfies
r
1/i
π(nk ) = k.
i=1
x
From this relation and the approximation π(x) ≈ (guaranteed by
log x
the Prime Number Theorem), it follows that
nk
≈ k,
log nk
so that log nk ≈ log k + log log nk ≈ log k and therefore that

nk ≈ k log nk ≈ k log k,

which gives a starting point for the computation of the exact value of nk .
Using Mathematica and the program
Do[k = 10^j; n = Floor[N[k*Log[k]]];
While[r = Floor[N[Log[n]/Log[2]]];
s=Sum[PrimePi[n^(1/i)],{i,1,r}];(a=k-s)!=0,n=n+a];
Print[j,"->", n,"=",FactorInteger[n]],{j,3,10}]
we finally obtain the following table:
132 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

α n10α α n10α
1 16 6 15 474 787
2 419 7 179 390 821
3 7 517 8 2 037 968 761
4 103 511 9 22 801 415 981
5 1 295 953 10 252 096 677 813
(145) If n is even, then 2n + n2 is also even and therefore not a prime. It follows
that n ≡ 1, 3 or 5 modulo 6. If n = 6k + 1 for a certain nonnegative
integer k, then 2n = 26k+1 ≡ 2 (mod 3) and n2 ≡ 1 (mod 3); in this case,
we have that 2n + n2 ≡ 2 + 1 ≡ 0 (mod 3). Similarly, if n = 6k + 5 for a
certain nonnegative integer k, we easily show that 3|2n + n2 . Therefore,
the only way that 2n + n2 can be a prime number is that n ≡ 3 (mod 6).
Thus, by considering all the positive integers n < 100 of the form
n = 6k + 3 and using a computer, we easily find that the only prime
numbers of the form 2n + n2 , with n < 100, are those corresponding to
n = 1, 9, 15, 21, 33.
(146) We will show that if n is of the form n = 3k + 1 or n = 3k + 2 with k ≥ 1,
then 7|an . Moreover, we will show that if n is of the form n = 3(3k + 1)
or n = 3(3k + 2) with k ≥ 1, then 73|an . Finally, since 3|an if n is even,
it will follow that, for an to be prime, n must be an odd multiple of 9.
So let n = 3k + a, with a = 1 or 2. Since 8k ≡ 1 (mod 7) for each
integer k ≥ 1, we have
an = 2n (2n + 1) + 1 = 23k+a (23k+a + 1) + 1
= 8k 2a (8k 2a + 1) + 1 ≡ 2a (2a + 1) + 1 (mod 7).
But
a a 7 ≡ 0 (mod 7) if a = 1,
2 (2 + 1) + 1 =
21 ≡ 0 (mod 7) if a = 2,
which establishes our first statement.
Let us now assume that n = 3(3k + a) with a = 1 or 2. Since 29 ≡ 1
(mod 73), we have
an = 2n (2n + 1) + 1 = 29k+3a (29k+3a + 1) + 1
= (29 )k 23a ((29 )k 23a + 1) + 1 ≡ 23a (23a + 1) + 1 (mod 73).
But

3a 3a 23 (23 + 1) + 1 = 73 ≡ 0 (mod 73) if a = 1,
2 (2 + 1) + 1 =
26 (212 + 1) + 1 = 4161 ≡ 0 (mod 73) if a = 2,
which establishes our second statement.
Having observed that an is prime for n = 1, 3 and 9, and then con-
sidering all the numbers of the form n = 9(2k + 1), we obtain using a
computer that an is composite for each integer n, 10 ≤ n < 1000.
(147) That number is n = 9; we then have a9 = 326981 = 79 · 4139.
(148) First observe that it follows from Wilson’s Theorem that
⎧
⎪⎨1 if j is prime,
(j − 1)! + 1 (j − 1)!
− =
j j ⎪
⎩
0 if j is composite.
SOLUTIONS 133

Hence, to obtain the formula of Minác and Willans, we only need to prove
that %
2n 1/n &
n
pn = 2 + .
m=2
1 + π(m)
But we easily prove that
⎧
% 1/n & ⎪
n ⎨1 if π(m) ≤ n − 1,
=
1 + π(m) ⎪
⎩
0 otherwise.
Now, as m varies from 2 to 2n , we have that π(m) ≤ n − 1 for m =
2, 3, . . . , pn − 1, that is a total of pn − 2 numbers. Therefore,
% 1/n &

2n
n
2+ = 2 + pn − 2 = pn ,
m=2
1 + π(m)
as was to be shown.
(149) We use an induction argument. The result is true for n = 1 and for n = 2.
So let n ≥ 3. Assume that the result is true for all natural numbers
≤ n − 1 and let us show that it implies that it must be true for n. Let
Pn = p≤n p. First of all, if n is even, then Pn = Pn−1 , so that the result
is true for n. Let us examine the case where n is odd, that is n = 2k + 1
for a certain positive integer k. It follows that each prime number p such
that k + 2 ≤ p ≤ 2k + 1 is a divisor of the number

2k + 1 (2k + 1)(2k)(2k − 1)(2k − 2) · · · (k + 2)
(∗) = .
k 1· 2 · 3···k
Since

2k + 1 2k + 1 2k + 1
22k+1 = (1 + 1)2k+1 > + =2 ,
k k+1 k
we obtain
2k + 1
< 4k .
k
It follows that the product of all the prime numbers p such that k + 2 ≤
2k + 1
p ≤ 2k + 1 is a divisor of and therefore smaller than 4k . On the
k
other hand, using the induction hypothesis, we have that Pk+1 ≤ 4k+1 .
This is why
Pn = P2k+1 = p· p < 4k+1 · 4k = 42k+1 = 4n ,
p≤k+1 k+2≤p≤2k+1

as was to be shown.
(150) Let m = (a, c). Then, there exist two integers u and v such that (u, v) = 1
and such that a = mu and c = mv. Hence, since ab = cd, we have
mub = mvd and therefore ub = vd. Since (u, v) = 1, we have u|d and this
is why there exists an integer n such that d = nu. Since ub = vnu, we
therefore have b = nv. It follows from these relations that
a2 + b2 + c2 + d2 = m2 u2 + n2 v 2 + m2 v 2 + n2 u2 = m2 (u2 + v 2 )
+n2 (u2 + v 2 ) = (u2 + v 2 )(m2 + n2 ),
134 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

a product of two integers larger than 1.

(151) Since
4n3 + 6n2 + 4n + 1 = n4 + 4n3 + 6n2 + 4n + 1 − n4 = (n + 1)4 − n4
= ((n + 1)2 − n2 )((n + 1)2 + n2 ) = (2n + 1)(2n2 + 2n + 1),
the product of two integers larger than 1, the result follows.
(152) First of all, since p + q is even, we can write
p+q
(∗) p+q =2· .
2
Since p+q
2 is an integer located between the two consecutive prime numbers
p and q, it must be composite, that is the product of at least two prime
numbers, and this is why the right-hand side of (∗) has at least three
prime factors.
(153) The answer is YES. We look for positive integers n, a, b and c such that
n n n
= a2 , = b3 , = c5 .
2 3 5
It is sufficient to find integers a, b and c such that
2a2 = 3b3 = 5c5 .
The task is therefore to find integers αi , βi and γi (i = 1, 2, 3) such that
2 3 5
2 2α1 3β1 5γ1 = 3 2α2 3β2 5γ2 = 5 2α3 3β3 5γ3 .
To do so, we must find integers αi , βi and γi (i = 1, 2, 3) such that
2α1 + 1 = 3α2 = 5α3 , 2β1 = 3β2 + 1 = 5β3 , 2γ1 = 3γ2 = 5γ3 + 1.
We easily find
α1 = 7, α2 = 5, α3 = 3, β1 = 5, β2 = 3, β3 = 2, γ1 = 3, γ2 = 2, γ3 = 1.
We then obtain that n = 2(27 · 35 · 53 )2 = 30 233 088 000 000 serves our
purpose.
(154) This follows from the identity
n42 − 27 = (n14 )3 − 33 = (n14 − 3)(n28 + 3n14 + 32 ).
(155) We proceed by contradiction by assuming that there does not exist any
prime number in the interval ]x, 2x], in which case we have θ(2x) = θ(x).
By using the inequalities 0.73x < θ(x) < 1.12x, we would then have
1.46x = 2(0.73)x < θ(2x) = θ(x) < 1.12x,
a contradiction.
(156) We proceed by induction. First of all, for n = 4, the result is true,
since 121 = 112 = p25 < p1 p2 p3 p4 = 210. Assume that the inequality
p2k < p1 p2 · · · pk−1 is true for a certain integer k ≥ 5. By using Bertrand’s
Postulate in the form pk+1 < 2pk , we then have
p2k+1 < 4p2k < 4p1 p2 · · · pk−1 < p1 p2 · · · pk ,
and the result then follows by induction.
SOLUTIONS 135

(157) If there exist q, r, a ∈ N such that q r = (q r/2 )2 = a2 , where r is even

and q r = p + m2 with p prime and m ∈ N, then a2 − m2 = p, so that
(a−m)(a+m) = p. Since p is prime, we must have a−m = 1 and a+m = p,
and therefore m = a − 1 and p = 2a − 1. Hence, if 2a − 1 = 2q r/2 − 1 is
composite, q r cannot be written as p + m2 , as was to be shown.
(158) For p = 3, the result is immediate. Assume that p ≥ 5. If p = 3k + 1
for a certain positive integer k, then 8k + 1 = 24k + 9, a multiple of 3.
Otherwise, that is if p = 3k − 1 for a certain positive integer k, then
8p − 1 = 24k − 9, a multiple of 3, which contradicts the fact that 8p − 1
is prime. In both cases, the result is proved.
(159) If a positive integer of the form 3k + 2 has no prime factor of the form
3k + 2, then all its prime factors are of the form 3k + 1. Since the product
of two integers of the form 3k + 1 is of the form 3k + 1, the result follows.
Since each product of prime numbers of the form 4k + 1 is of the same
form and since each product of prime numbers of the form 6k + 1 is of the
same form, the result follows.
(160) (a) We have 23 = 3 · 3! + 2 · 2! + 1 · 1! and 57 = 2 · 4! + 1 · 3! + 1 · 2! + 1 · 1!.
(b) To find the Cantor expansion of a positive integer n, we proceed as
follows. Let m be the largest positive integer such that m! ≤ n and
let am be the largest positive integer such that am · m! ≤ n. It is
clear that 0 < am ≤ m; otherwise, this would contradict the maximal
choice of m. If am · m! = n, then the Cantor expansion is given by
n = am ·m!. Otherwise, that is if am ·m! < n, let d1 = n−am ·m! > 0,
let m1 be the largest positive integer such that m1 ! ≤ d1 and let am1
be the largest positive integer such that am1 · m1 ! ≤ di . As above, we
have a < am1 ≤ m1 . If am1 · m1 ! = d1 ; then the Cantor expansion
is given by n = am · m! + am1 · m1 !, where 0 < am1 ≤ m1 < m. If
am1 · m1 ! < d1 , then we set d2 = d1 − am1 · m1 ! and we let m2 be
the largest positive integer such that m2 ! ≤ d2 . And so on. We thus
build a sequence of positive integers m > m1 > m2 > . . . with the
corresponding integers 0 < ami ≤ mi . Since the sequence of mi ’s is
decreasing, it must have an end. Let us show the uniqueness of this
representation. Assume that for 0 ≤ aj , bj ≤ j, we have
n = am m! + · · · + a1 1! = bm m! + · · · + b1 1!,
that is (am − bm )m! + · · · + (a1 − b1 )1! = 0. If both expansions are
different, then there exists a smaller integer j such that 1 ≤ j < m
and aj = bj . Hence,

m!
j! (am − bm ) + · · · + (aj+1 − bj+1 )(j + 1) + (aj − bj ) = 0
j!
and therefore
m!
bj − aj = (am − bm ) + · · · + (aj+1 − bj+1 )(j + 1)
j!

m!
= (j + 1) (am − bm ) + · · · + (aj+1 − bj+1 ) ,
(j + 1)!
which implies that (j + 1)|(bj − aj ). Since 0 ≤ aj , bj ≤ j, it follows
that aj = bj , a contradiction.
136 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

(161) (TYCM, Vol. 19, 1988, p. 191). The expression in the statement can be
written as
(p − 1)! + 1 (−1)d d!(p − 1)! + 1
+ .
p p+d
Since (p + d − 1)! = (p + d − 1)(p + d − 2) · · · (p + d − d)(p − 1)!, we
have (p + d − 1)! ≡ (−1)d d!(p − 1)! (mod p + d), and it follows that the
expression in the statement is an integer if and only if
(p − 1)! + 1 (p + d − 1)! + 1
(1) +
p p+d
is an integer. From Wilson’s Theorem, if p and p + d are two prime
numbers, then each of the terms of (1) is an integer, which proves the
necessary condition.
Conversely, assume that expression (1) is an integer. If p or p + d is
not a prime, then by Wilson’s Theorem, at least one of the terms of (1) is
not an integer. This implies that none of the terms of (1) is an integer or
equivalently neither of p and p + d is prime. It follows that both fractions
of (1) are in reduced form.
It is easy to see that if a/b and a /b are reduced fractions such that
a/b + a /b = (ab + a b)/(bb ) is an integer, then b|b and b |b.
Applying this result to (1), we obtain that (p + d)|p, which is impossi-
ble. We may therefore conclude that if (1) is an integer, then both p and
p + d must be primes.
(162) If p = 3, then p + 2 = 5 is prime and p2 + 2p − 8 = 7 is prime. It is the only
number with this property. Indeed, p = 2 does not have this property,
while if p > 3, then
p2 + 2p − 8 ≡ 1 + 2p − 2 ≡ 2(p + 1) ≡ 0 (mod 3) ⇐⇒ 3|(p + 1).
But for p > 3, p = 3k ± 1, and in each of the cases it is easily seen that at
least one of the two numbers p + 2 and p2 + 2p − 8 is not a prime.
(163) The answer is YES. If p = 3, then p2 + 8 = 17 is prime and p3 + 4 = 31 is
prime. It is the only prime number with this property. Indeed, p = 2 does
not have this property, while if p > 3, then p ≡ ±1 (mod 3), in which
case p2 ≡ 1 (mod 3), that is p2 + 8 ≡ 9 ≡ 0 (mod 3), so that p2 + 8 is not
a prime. Thus the result.
(164) (Ribenboim [28], p. 145). First assume that the congruence is satisfied.
Then n = 2, 4 and (n − 1)! + 1 ≡ 0 (mod n). Thus, using Wilson’s
Theorem, n is prime. Moreover, 4(n − 1)! + 2 ≡ 0 (mod n + 2); thus,
multiplying by n(n + 1) we obtain
4[(n + 1)! + 1] + 2n2 + 2n − 4 ≡ 0 (mod n + 2)
and therefore
4[(n + 1)! + 1] + (n + 2)(2n − 2) ≡ 0 (mod n + 2);
hence, 4[(n + 1)! + 1] ≡ 0 (mod n + 2). This is why, using Wilson’s
Theorem, n + 2 is also prime.
Conversely, if n and n + 2 are prime, then n = 2 and
(n − 1)! + 1 ≡ 0 (mod n),
(n + 1)! + 1 ≡ 0 (mod n + 2).
SOLUTIONS 137

But n(n + 1) = (n + 2)(n − 1) + 2, and this is why 2(n − 1)! + 1 = k(n + 2),
where k is an integer. From the relation (n − 1)! ≡ −1 (mod n), we
obtain 2k + 1 ≡ 0 (mod n). Now, 2(n − 1)! + 1 = k(n + 2) is equivalent to
4(n − 1)! + 2 ≡ 0 ≡ −(n + 2) (mod n + 2). Moreover, 4(n − 1)! + 2 ≡ 4k ≡
−2 ≡ −(n Hence, 4(n − 1)! + 2 ≡ −(n + 2) (mod (n(n + 2));
+ 2) (mod n).
that is 4 (n − 1)! + 1 + n ≡ 0 (mod n(n + 2)).
(165) The prime number p = 3 is the only one with this property, because if
p > 3, then p = 2k + 1 for a certain integer k ≥ 2, in which case
2p = 22k+1 = 4k · 2 ≡ 2 (mod 3)
while
p2 ≡ 1 (mod 3),
so that
2p + p2 ≡ 0 (mod 3).
(166) The answer is p = 19. Indeed, 17p + 1 = a2 ⇒ 17p = (a − 1)(a + 1). We
then have 17 = a − 1 and p = a + 1 or 17 = a + 1 and p = a − 1. The
first case yields a = 18 and p = 19, while the second case yields a = 16
and p = 15, which is to be rejected. Thus the result.
(167) (a) The possible values of (a2 , b) are p and p2 .
(b) The only possible value of (a2 , b2 ) is p2 .
(c) The possible values of (a3 , b) are p, p2 and p3 .
(d) The possible values of (a3 , b2 ) are p2 and p3 .
(168) (a) The only possible value is p3 .
(b) The only possible value is p.
(c) The only possible value is p.
(d) The possible values are p2 , p3 , p4 and p5 .
(169) We have (a2 b2 , p4 ) = p4 and (a2 + b2 , p4 ) = p2 .
(170) (a) True. (b) True. (c) True.
(d) False. Indeed, we have 13|22 + 32 and 13|32 + 22 , while 13 | 22 + 22 =
8.
(171) It is an immediate consequence of Theorem 12.
(172) Let ⎧
⎪
⎨a = p1 · · · pr ,
α1 αr
β1
b = p1 · · · pβr r ,
⎪
⎩
c = pγ11 · · · pγr r .
From Theorem 12,
min(α1 ,β1 ,γ1 )
(a, b, c) = p1 · · · prmin(αr ,βr ,γr )
and
max(α ,β ,γ )
[a, b, c] = p1 1 1 1
· · · prmax(αr ,βr ,γr ) .
To prove the result, we proceed by contradiction. Assume for example
that (a, b) > 1. Using the fact that (a, b, c)[a, b, c] = abc, it follows, using
the above notation, that
min(αi , βi , γi ) + max(αi , βi , γi ) = αi + βi + γi (i = 1, 2, . . . , r).
But it is easy to prove that for the sum of three nonnegative integers to
be equal to the sum of the smallest and of the largest of these same three
138 1001 PROBLEMS IN CLASSICAL NUMBER THEORY

numbers, at least two of these numbers must be 0. But this contradicts

the fact that (a, b) > 1, an inequality which means that there exists an i0
(1 ≤ i0 ≤ r) for which min(αi0 , βi0 ) ≥ 1. Hence, the result.
(173) We use Theorem 12 and the fact that
min{αi , βi , γi } = min{αi , βi } + min{βi , γi } + min{α, γi }
− min{αi + βi , βi + γi , αi + γi }.
The second part follows from the first part and Problem 171.
(174) Let
⎧
⎪
⎨a = p1 · · · pr ,
α1 αr
β1
b = p1 · · · pβr r ,
⎪
⎩
c = pγ11 · · · pγr r .
max{αi ,βi } min{αi ,βi }
Since [a, b] = ri=1 pi and (a, b) = r
i=1 pi , it is enough
to show that, for each i,
2 max{αi , βi , γi } − max{αi , βi } − max{βi , γi } − max{γi , αi }
= 2 min{αi , βi , γi } − min{αi , βi } − min{βi , γi } − min{γi , αi }.
Without loosing in generality, we may assume that, for a given i, αi ≥
βi ≥ γi , from which the result easily follows.
(175) Let a = ri=1 pai i , b = ri=1 pbi i , c = ri=1 pci i . Without loosing in gener-
ality, we may assume that ai ≤ bi ≤ ci . The equation of the statement
allows one to conclude that ci + ai = 12 (ai + bi + ci ) and therefore that
ai + ci = bi , which implies, since ci ≥ bi , that bi = ci and ai = 0. This
means that in order for the relation to be true, for the same prime num-
ber, two of the exponents must be equal while the third one should be
0. Hence, we can choose a = 21 · 31 · 50 = 6, b = 21 · 30 · 51 = 10 and
c = 20 · 31 · 51 = 15. Note that the numbers 42, 70, 15 will also do.
(176) The left inequality is obvious. To prove the right equality, first observe
that
#n = [1, 2, . . . , n] = pδp ,
p≤n
δp
where p is the largest power of p not exceeding n. In other words,
δp is defined implicitly by the inequalities pδp ≤ n < pδp +1 . It follows
successively that
δp log p ≤ log n < (δp + 1) log p,
log n
δp ≤ < δp + 1,
log p

log n
δp = .
log p
We have thus established that
#n = p[log n/ log p] ,
p≤n

which was to be shown.

Subject Index

algorithm of Euclid, 45 finite, 11

cycle of a, 7
Bernoulli Inequality, 104 period of a, 7
Bertrand’s Postulate, 5, 68, 244 function
binomial coefficients, 4 additive, 8
binomial theorem, 4 arithmetical, 8
completely additive, 8
canonical representation, 3
completely multiplicative, 8
Cantor expansion, 26
multiplicative, 8
Cassiny Identity, 83, 284
of Dirichlet, 99
Cauchy-Schwarz Inequality, 3
of Euler, 6, 8, 75
congruence, 6
of Liouville, 8, 61, 66, 72, 73, 75
conjecture
of Moebius, 8, 65, 75
abc, 12
of von Mangoldt, 8, 63, 67, 75
Carmichael, 81
totally additive, 8
Goldbach, 32
totally multiplicative, 8
criterion
Korselt’s, 186 greatest common divisor (GCD), 4
Euler, 10
cycle of a fraction, 7 harmonic mean of divisors, 61
hypothesis H, 12
derivative of an arithmetical
function, 72 inequality
determinant, Smith, 257 of Bernoulli, 104
(also see Smith determinant) of Cauchy-Schwarz, 3
dihedral group, 79 of the means, 3
Dirichlet product, 9, 65
Korselt’s Criterion, 186
divisor(s)
k–th convergent of a continued
greatest common (GCD), 4
fraction, 11
number of, 8
proper, 4 largest integer smaller
sum of, 8 or equal to, 7
law of quadratic reciprocity, 10
Eratosthenes, sieve of, 25 Legendre symbol, 10
Euclidean lowest common multiple (LCM), 5
algorithm, 4
division, 4 Moebius Inversion Formula, 9
Euler Criterion, 10
number(s)
Fermat equation, 89 abundant, 59, 82
Fermat’s Factorization Method, 45 algebraic, 12
Fermat’s Little Theorem, 6 aliquot, 9
fraction, amicable, 9
continued automorphic, 35
infinite, 12, 97 Canada perfect, 76

333
334 SUBJECT INDEX

Carmichael, 9, 46, 47, 83, 185 test

Catalan, 82 of divisibility, 41
complete, 34 of Fermat, 45
Cullen, 81 of Lucas, 47
deficient, 59 of Lucas-Lehmer, 45, 180, 181
dihedral perfect, 79 of Pepin, 48
of distinct prime factors, 8 of Pollard, 48
of divisors, 7 theorem
Fermat, 9, 29 Chinese Remainder, 7
Fibonacci, 17, 83 Dirichlet, 5
kernel of a, 8 Euclid, 5
k-hyperperfect, 81 Euler, 6
k-perfect, 9 fundamental of arithmetic, 5
k-powerful, 9 Lagrange, 12
Mersenne, 9, 28 Legendre, 7
Niven, 81 Mertens’, 6
perfect, 9, 29 prime number, 6
powerful, 9 Pythagorean triple, 85
prime, 3 Wilson, 7
Mersenne, 9, 25, 29, 37, 59, 140
Sophie Germain, 221
twin, 3
Wieferich, 177
Wilson, 81
pseudo-prime, 7, 29, 187
Psi-perfect, 71
Silverbach, 81
total of prime factors, 8
transcendental, 12
triangular, 9
tri-perfect, 59
vampire, 36

order of an integer, 47

palindrome, 34, 81
period of a fraction, 7
postulate of Bertrand, 5, 68, 244
primitive solution, 10
principle
inclusion-exclusion, 3
induction, 3
pigeonhole, 3
problem
Collatz, 55
Syracuse, 55
tower of Hanoi, 17
Waring, 36
product of Dirichlet, 9, 65

relatively prime integers, 5

residue(s), 6
complete system of, 6
nonquadratic, 10
quadratic, 10
reduced system of, 6

Smith determinant, 257

squarefree number, 8
Index of Authors

Amdeberban, T., 152 Jones, L., 284

Anglin, W.S., 152
Apéry, R., 306 Kátai, I., 128, 238, 239, 251
Apostol, T.M., 227, 313 Klamkin, M.S., 110, 250
Korrah, Thabit ben, 82
Barbeau, E.J., 110, 250 Korselt, A., 186
Bernoulli, J., 104 Kurepa, D., 19
Bombieri, E., 90
Borwein, J.W., 156 Lagrange, J.L., 36
Lambert, J.H., 125
Bradley, D., 156
Legendre, A.M., 32
Brillhart, J., 188, 294
Lehmer, D.H., 83, 188
Caldwell, C.K., 279 Levesque, C., 286
Carmosini, M., 288 London, H., 287
Cavior, S., 79 Lucas, E., 89
Cipolla, M., 187
Malo, E., 187
De Carufel, J.L., 160 Masser, D., 12
De Koninck, J.M., 28, 252 McCarthy, P.J., 236
Doolittle, E., 323 Mercier, A., 28
Doyon, N., 154, 155, 280 Mersenne, M., 28
Dudeney, H.E., 157 Mijajlović, Z., 19
Minác̆, J., 25, 133, 147
Erdős, P., 26, 47, 89, 123, 153, 204, 207 Montgomery, H.L., 12
Euler, J.A., 36 Moser, W.O.S., 110, 250, 302
Euler, L., 29, 213, 284 Myerson, G., 208

Fermat, P., 21, 29, 38 Newman, D.J., 141

Finkelstein, R., 287 Niven, I., 11

Oesterlé, J., 12
Gelfand, S.I., 105
Gel fond, A.O., 99, 326 Pascal, B., 16
Germain, S., 221 Pinner, C.G., 156
Giblin, P., 164, 185 Polezzi, M., 51
Grah, J., 252 Pomerance, C., 159
Guy, R.K., 123, 216
Ramanujan, S., 84
Halter-Kock, F., 287 Ribenboim, P., 136, 147
Hardy, G.H., 84 Riesel, H., 31
Hilbert, D., 36 Roberts, J., 287
Hlawka, E., 31
Hoffman, F., 261 St. Udrescu, V., 287
Huygens, C., 38 Sander, J.W., 208
Schinzel, A., 12, 154
Ivić, A., 19, 303 Schlafly, A., 81

335
336 INDEX OF AUTHORS

Schneider, T., 99, 326

Schroeppel, R., 261
Schwab, E.D., 243
Selfridge, J.L., 45, 188, 261
Shapiro, H.N., 257
Sica, F., 164
Sierpinski, W., 12, 45, 151, 152, 267, 280,
291, 312
Spence, G., 59
Sylvester, J.J., 34
Szekeres, G., 123

Tartaglia, N.F., 28

Wagon, S., 81
Walter, J., 302
Weisstein, E.W., 158
Willans, C.P., 25, 133
Williams, H.C., 29, 187

Zuckerman, H.S., 12