In recent times the we witnessed an explosion of Number Theory prob- [613778]
Preface
In recent times the we witnessed an explosion of Number Theory prob-
lems that are solved using mathematical software and powerful comput-
ers. The observation that the number of transistors packed on integrated
circuits doubles every two years made by Gordon E. Moore in 1965 is still
accurate to this day. With ever increasing computing power more and
more mathematical problems can be tacked using brute force. At the same
time the advances in mathematical software made tools like Maple, Math-
ematica, Matlab or Mathcad widely available and easy to use for the vast
majority of the mathematical research community. This tools don’t only
perform complex computations at incredible speeds but also serve as a
great tools for symbolic computation, as proving tools or algorithm de-
sign.
The online meeting of the two authors lead to lively exchange of ideas,
solutions and observation on various Number Theory problems. The ever
increasing number of results, solving techniques, approaches, and algo-
rithms led to the the idea presenting the most important of them in in
this volume. The book offers solutions to a multitude of –Diophantine
equation proposed by Florentin Smarandache in previous works [Smaran-
dache, 1993, 1999b, 2006] over the past two decades. The expertise in tack-
ling Number Theory problems with the aid of mathematical software such
as [Cira and Cira, 2010], [Cira, 2013, 2014a, Cira and Smarandache, 2014,
Cira, 2014b,c,d,e] played an important role in producing the algorithms
and programs used to solve over 62–Diophantine equation. There are
numerous other important publications related to Diophantine Equations
iii
iv
that offer various approaches and solutions. However, this book is differ-
ent from other books of number theory since it dedicates most of its space
to solving Diophantine Equations involving the Smarandache function. A
search for similar results in online resources like The On-Line Encyclopedia
of Integer Sequences reveals the lack of a concentrated effort in this direction.
The brute force approach for solving –Diophantine equation is a well
known technique that checks all the possible solutions against the problem
constrains to select the correct results. Historically, the proof of concept
was done by Appel and Haken [1977] when they published the proof for
thefour color map theorem. This is considered to be the the first theorem
that was proven using a computer. The approach used both the computing
power of machines as well as theoretical results that narrowed down infi-
nite search space to 1936 map configurations that had to be check. Despite
some controversy in the ’80 when a masters student: [anonimizat], the initial results was correct. Ap-
pel and Haken went on to publish a book [Appel and Haken, 1989] that
contained the entire and correct prof that every planar map is four-colorable.
Recently, in 2014 an empirical results of Goldbach conjecture was pub-
lished in Mathematics of Computation where Oliveira e Silva et al. [2013],
[Oliveira e Silva, 2014], confirm the theorem to be true for all even num-
bers not larger than 41018.
The use of Smarandache function that involves the set of all prime
numbers constitutes one of the main reasons why, most of the problems
proposed in this book do not have a finite number of cases. It could be
possible that the unsolved problems from this book could be classified in
classes of unsolved problems, and thus solving a single problem will help
in solving all the unsolved problems in its class. But the authors could not
classify them in such classes. The interested readers might be able to do
that. In the given circumstances the authors focused on providing the most
comprehensive partial solution possible, similar to other such solutions in
the literature like:
Goldbach’s conjecture. In 2003 Oliveira e Silva announced that all
even numbers21016can be expressed as a sum of two primes.
v
In 2014 the partial result was extended to all even numbers smaller
then 41018, [Oliveira e Silva, 2014].
For any positive integer n, letf(n)denote the number of solutions
to the Diophantine equation 4=n= 1=x+ 1=y + 1=z withx,y,zposi-
tive integers. The Erd˝ os-Straus conjecture, [Obl ´ath, 1950, Rosati, 1954,
Bernstein, 1962, Tao, 2011], asserts that f(n)1for everyn2.
Swett [2006] established that the conjecture is true for all integers for
anyn1014. Elsholtz and Tao [2012] established some related re-
sults onfand related quantities, for instance established the bound
f(p)p3=5+O
1=log(log(p))
for all primes p.
Tutescu [1996] stated that (n)6=(n+ 1) for anyn2N. On March
3rd, 2003 Weisstein published a paper stating that all the relation is
valid for all numbers up to 109, [Sondow and Weisstein, 2014].
A numbernisk–hyperperfect for some integers kifn= 1 +ks(n),
wheres(n) is the sum of the proper divisors of n. Allk–hyperperfect
numbers less than 1011have been computed. It seems that the con-
jecture ”all k–hyperperfect numbers for odd k > 1are of the form p2q,
withp= (3k + 4)=4 prime andq= 3k + 4 = 2p + 3 prime” is false
[McCranie, 2000].
This results do not offer the solutions to the problems but they are impor-
tant contributions worth mentioning.
The emergence of mathematical software generated a new wave of
mathematical research aided by computers. Nowadays it is almost impos-
sible to conduct research in mathematics without using software solutions
such as Maple, Mathematica, Matlab or Mathcad, etc. The authors used
extensively Mathcad to explore and solve various Diophantine equations
because of the very friendly nature of the interface and the powerful pro-
gramming tools that this software provides. All the programs presented
in the following chapters are in their complete syntax as used in Mathcad.
The compact nature of the code and ease of interpretation made the choice
of this particular software even more appropriate for use in a written pre-
sentation of solving techniques.
vi
The empirical search programs in this book where developed and exe-
cuted in Mathcad. The source code of this algorithms can be interpreted as
pseudo code (the Mathcad syntax allows users to write code that is very
easy to read) and thus translated to other programming languages.
Although the intention of the authors was to provide the reader with
a comprehensive book some of the notions are presented out of order. For
example the book the primality test that used Smarandache’s function is
extensively used. The first occurrences of this test preceded the definition
the actual functions and its properties. However, overall, the text covers
all definition and proves for each mathematical construct used. At the
same time the references point to the most recent publications in literature,
while results are presented in full only when the number of solutions is
reasonable. For all other problems, that generate in excess of 100double,
triple or quadruple pairs, only partial results are contained in the sections
of this book. Nevertheless, anyone interested in the complete list should
contact the authors to obtain a electronic copy of it. Running the programs
in this book will also generate the same complete list of possible solutions
for any odd the problems in this book.
Authors
Acknowledgments
We would like to thank all the collaborators that helped putting to-
gether this book, especially to Codrut ¸a Stoica and Cristian Mihai Cira, for
the important comments and observations.
Contents
Preface iii
Contents vii
List of figure xii
List of table xiii
Introduction xiv
1 Prime numbers 1
1.1 Generating prime numbers . . . . . . . . . . . . . . . . . . . 2
1.2 Primality tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 The test of primality . . . . . . . . . . . . . . . . . . 14
1.2.2 Deterministic tests . . . . . . . . . . . . . . . . . . . . 15
1.2.3 Smarandache’s criteria of primality . . . . . . . . . . 24
1.3 Decomposition product of prime factors . . . . . . . . . . . . 32
1.3.1 Direct factorization . . . . . . . . . . . . . . . . . . . . 35
1.3.2 Other methods of factorization . . . . . . . . . . . . . 37
1.4 Counting of the prime numbers . . . . . . . . . . . . . . . . . 39
1.4.1 Program of counting of the prime numbers . . . . . . 39
1.4.2 Formula of counting of the prime numbers . . . . . . 40
vii
viii CONTENTS
2 Smarandache’s function 42
2.1 The properties of function . . . . . . . . . . . . . . . . . . . 45
2.2 Programs for Kempner’s algorithm . . . . . . . . . . . . . . . 50
2.2.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . 53
2.2.2 Calculation the of values function . . . . . . . . . . 54
3 Divisor functions 58
3.1 The divisor function . . . . . . . . . . . . . . . . . . . . . . 58
3.1.1 Computing the values of kfunctions . . . . . . . . . 62
3.2k–hyperperfect numbers . . . . . . . . . . . . . . . . . . . . . 63
4 Euler’s totient function ' 64
4.1 The properties of function '. . . . . . . . . . . . . . . . . . . 65
4.1.1 Computing the values of 'function . . . . . . . . . . 67
4.2 A generalization of Euler’s theorem . . . . . . . . . . . . . . 68
4.2.1 An algorithm to solve congruences . . . . . . . . . . . 72
4.2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Generalization of congruence theorems 75
5.1 Notions introductory . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Theorems of congruence of the Number Theory . . . . . . . 78
5.3 A unifying point of convergence theorems . . . . . . . . . . . 81
5.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6 Analytical solving 87
6.1 General Diophantine equations . . . . . . . . . . . . . . . . . 87
6.2 General linear Diophantine equation . . . . . . . . . . . . . . 89
6.2.1 The number of solutions of equation . . . . . . . . . . 90
6.2.2 Diophantine equation of first order with two unknown 92
6.3 Solving the Diophantine linear systems . . . . . . . . . . . . 98
6.3.1 Procedure of solving with row–reduced echelon form 98
6.3.2 Solving with Smith normal form . . . . . . . . . . . . 105
6.4 Solving the Diophantine equation of order n. . . . . . . . . 107
6.5 The Diophantine equation of second order . . . . . . . . . . 113
CONTENTS ix
6.5.1 Existence and number of solutions . . . . . . . . . . . 113
6.5.2 Method of solving . . . . . . . . . . . . . . . . . . . . 115
6.5.3 Procedure for solving . . . . . . . . . . . . . . . . . . 118
6.5.4 Generalizations . . . . . . . . . . . . . . . . . . . . . . 124
6.6 The Diophantine equation x2 2y4+ 1 = 0 . . . . . . . . . . 127
7 Partial empirical solving 130
7.1 Empirical determination of solutions . . . . . . . . . . . . . . 130
7.1.1 Partial empirical solving of Diophantine equations . 131
7.2 The–Diophantine equations . . . . . . . . . . . . . . . . . . 135
7.2.1 Partial empirical solving of –Diophantine equations 137
7.2.2 The equation 2069 . . . . . . . . . . . . . . . . . . . . 137
7.2.3 The equation 2070 . . . . . . . . . . . . . . . . . . . . 140
7.2.4 The equation 2071 . . . . . . . . . . . . . . . . . . . . 141
7.2.5 The equation 2072 . . . . . . . . . . . . . . . . . . . . 143
7.2.6 The equation 2073 . . . . . . . . . . . . . . . . . . . . 145
7.2.7 The equation 2074 . . . . . . . . . . . . . . . . . . . . 146
7.2.8 The equation 2075 . . . . . . . . . . . . . . . . . . . . 149
7.2.9 The equation 2076 . . . . . . . . . . . . . . . . . . . . 151
7.2.10 The equation 2077 . . . . . . . . . . . . . . . . . . . . 154
7.2.11 The equation 2078 . . . . . . . . . . . . . . . . . . . . 157
7.2.12 The equation 2079 . . . . . . . . . . . . . . . . . . . . 157
7.2.13 The equation 2080 . . . . . . . . . . . . . . . . . . . . 160
7.2.14 The equation 2081 . . . . . . . . . . . . . . . . . . . . 163
7.2.15 The equation 2082 . . . . . . . . . . . . . . . . . . . . 164
7.2.16 The equation 2083 . . . . . . . . . . . . . . . . . . . . 165
7.2.17 The equation 2084 . . . . . . . . . . . . . . . . . . . . 165
7.2.18 The equation 2085 . . . . . . . . . . . . . . . . . . . . 167
7.2.19 The equation 2086 . . . . . . . . . . . . . . . . . . . . 169
7.2.20 The equation 2087 . . . . . . . . . . . . . . . . . . . . 169
7.2.21 The equation 2088 . . . . . . . . . . . . . . . . . . . . 169
7.2.22 The equation 2089 . . . . . . . . . . . . . . . . . . . . 170
7.2.23 The equation 2090 . . . . . . . . . . . . . . . . . . . . 171
7.2.24 The equation 2091 . . . . . . . . . . . . . . . . . . . . 172
x CONTENTS
7.2.25 The equation 2092 . . . . . . . . . . . . . . . . . . . . 174
7.2.26 The equation 2093 . . . . . . . . . . . . . . . . . . . . 174
7.2.27 The equation 2094 . . . . . . . . . . . . . . . . . . . . 175
7.2.28 The equation 2095 . . . . . . . . . . . . . . . . . . . . 177
7.3 The–s–Diophantine equations . . . . . . . . . . . . . . . . . 179
7.3.1 Empirical solving of –s–Diophantine equations . . . 181
7.3.2 The equation 2124 . . . . . . . . . . . . . . . . . . . . 181
7.3.3 The equation 2125 . . . . . . . . . . . . . . . . . . . . 183
7.3.4 The equation 2126 . . . . . . . . . . . . . . . . . . . . 183
7.3.5 The equation 2127 . . . . . . . . . . . . . . . . . . . . 184
7.3.6 The equation 2128 . . . . . . . . . . . . . . . . . . . . 185
7.3.7 The equation 2129 . . . . . . . . . . . . . . . . . . . . 186
7.3.8 The equation 2130 . . . . . . . . . . . . . . . . . . . . 187
7.4 The––Diophantine equations . . . . . . . . . . . . . . . . . 187
7.4.1 Empirical solving of ––Diophantine equations . . . 187
7.4.2 The equation 2152 . . . . . . . . . . . . . . . . . . . . 188
7.4.3 The equation 2153 . . . . . . . . . . . . . . . . . . . . 189
7.4.4 The equation 2154 . . . . . . . . . . . . . . . . . . . . 190
7.4.5 The equation 2155 . . . . . . . . . . . . . . . . . . . . 191
7.4.6 The equation 2156 . . . . . . . . . . . . . . . . . . . . 193
7.4.7 The equation 2157 . . . . . . . . . . . . . . . . . . . . 193
7.4.8 The equation 2158 . . . . . . . . . . . . . . . . . . . . 194
7.5 The–k–Diophantine equations . . . . . . . . . . . . . . . . 194
7.5.1 Empirical solving of –k–Diophantine equations . . 195
7.5.2 The equation 2166 . . . . . . . . . . . . . . . . . . . . 196
7.5.3 The equation 2167 . . . . . . . . . . . . . . . . . . . . 200
7.5.4 The equation 2168 . . . . . . . . . . . . . . . . . . . . 200
7.5.5 The equation 2169 . . . . . . . . . . . . . . . . . . . . 202
7.5.6 The equation 2170 . . . . . . . . . . . . . . . . . . . . 204
7.5.7 The equation 2171 . . . . . . . . . . . . . . . . . . . . 207
7.5.8 The equation 2172 . . . . . . . . . . . . . . . . . . . . 207
7.6 The–'–Diophantine equations . . . . . . . . . . . . . . . . 208
7.6.1 Empirical solving of –'–Diophantine equations . . . 208
7.6.2 The equation 2187 . . . . . . . . . . . . . . . . . . . . 209
CONTENTS xi
7.6.3 The equation 2188 . . . . . . . . . . . . . . . . . . . . 210
7.6.4 The equation 2189 . . . . . . . . . . . . . . . . . . . . 210
7.6.5 The equation 2190 . . . . . . . . . . . . . . . . . . . . 211
7.6.6 The equation 2191 . . . . . . . . . . . . . . . . . . . . 212
7.6.7 The equation 2192 . . . . . . . . . . . . . . . . . . . . 212
7.6.8 The equation 2193 . . . . . . . . . . . . . . . . . . . . 212
7.7 Guy type Diophantine equations . . . . . . . . . . . . . . . . 213
7.7.1 Empirical solving Guy type Diophantine equations . 213
7.7.2 The equation 7.21 . . . . . . . . . . . . . . . . . . . . . 214
7.7.3 The equation 7.24 . . . . . . . . . . . . . . . . . . . . . 214
7.7.4 The equation 7.27 . . . . . . . . . . . . . . . . . . . . . 215
7.7.5 The equation 7.30 . . . . . . . . . . . . . . . . . . . . . 216
7.7.6 The equations 7.31–7.32 . . . . . . . . . . . . . . . . . 216
7.7.7 The equation 7.33 . . . . . . . . . . . . . . . . . . . . . 216
Conclusions 219
Indexes 220
Bibliography 236
List of Figures
1.1 The ratio of the numbers of operations . . . . . . . . . . . . . 10
1.2 Functions M(n),(n)andm(n). . . . . . . . . . . . . . . . 17
1.3 The graph of function nt(10n)forn= 2;3;:::; 8. . . . . . . 19
2.1function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2 The graph of function on the set f1;2;:::; 101g . . . . . . . 55
2.3 The graph of function on the set
1;2;:::; 105
. . . . . . . 56
3.1 Function 0(n). . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2 Function (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.1 Euler’s totient function . . . . . . . . . . . . . . . . . . . . . . 65
7.1 The function s. . . . . . . . . . . . . . . . . . . . . . . . . . . 180
xii
List of Tables
1.1 The vector isprime in the code 1.1 . . . . . . . . . . . . . . . 4
1.2 Comparative table . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Values nfor which(n) =k. . . . . . . . . . . . . . . . . . . 49
7.1 The check of the solutions of equation 7.30 . . . . . . . . . . 216
7.2 The check of the solutions of equation 7.33 . . . . . . . . . . 217
xiii
Introduction
A Diophantine equation is a linear equation ax+by=cwhere
a;b;c2Zand the solutions xandyare also integer numbers. This equa-
tion can be completely solved by the well known algorithm proposed by
Brahmagupta [Weisstein, 2014b].
In 1900, Hilbert wondered if there is an universal algorithm that solves
the Diophantine equation, but Matiyasevich [1970] proved that such an
algorithm does not exist for the first order solution.
The function relates to each natural number nthe smallest natural
numbermsuch thatm!is a multiple of n. In this book we aim to find ana-
lytical or empirical solutions to Diophantine and –Diophantine equation,
namely Diophantine equation that contain the Smarandache’s function,
Smarandache [1980b].
An analytical solution implies a general solution that completely
solves the problem. For example, the general solution for the equation a
x by=c, witha;b;c2Nisxk=bk+x0andyk=ak+y0, where (x0;y0)
is a particular solution, and kis an integer, kmaxfd x 0=be;d y 0=aeg.
By and empirical solution we understand a set of algorithms that de-
termine the solutions of the Diophantine equation within a finite domain
of integer numbers, dubbed the search domain to dimension d. For ex-
ample, the –Diophantine equation (mx+n) =xover the valid
search domain of dimension d= 3, the solutions could be the triplets
(m;n;x)2Dc=f1;2;:::; 1000gf1; 2;::: 1000gf1; 2;:::; 999g.
The first chapter introduces concepts about prime numbers, primality
tests, decomposition algorithms for natural numbers, counting algorithms
xiv
xv
for all natural numbers up to a real one, etc. This concepts are fundamental
for validating the empirical solutions of the –Diophantine equations.
The second chapter introduces the function along side its known
properties. This concepts allow the description of Kempner [1918] algo-
rithm that computes the function. The latter sections contain the set of
commands and instructions that generate the file :prn which contains the
(n)values forn= 1;2;:::; 106.
The third chapter describes the division functions 0,1, usually de-
noted by,2ands. The0(n)function counts the number of divisors of
n, while(n) =1(n)returns the sun of all those divisors. Consequently
2(n)computed the sum of squared divisors of nwhile, in general k(n)
add all divisors to the power of k. We call divisors of nall natural numbers
that divide nincluding 1andn, thus the proper divisors are considered all
natural divisors excluding nitself. In this case the function s(n) =(n) n
is , in fact, the sun of all proper divisors. Along side the the definition, this
third chapter also contains the properties and computing algorithms that
generate the files 0:prn,1:prn,2:prn,s:prn that contain all the values
for functions 0(n),(n),2(n)ands(n) forn= 1; 2;:::; 106. The last
section describes the k–perfect numbers.
Euler’s totient function also known as the 'function that counts the
natural numbers less than or equal to nthat are relatively prime is de-
scribed in chapter 4. As an example, for n= 12 the relatively prime fac-
tors are 1,5,7, and 11because (1;12) = 11,(5;12) = 1, (7;12) = 1, and
(11;12) = 1, thus '(12) = 4. The chapter also describes the most impor-
tant properties of this function. The latter section of the chapter contain the
algorithm that generates the file ':prn that contains the values of the func-
tion'fornraging from 1;2;:::; 106. Also, in this chapter the describes
a generalization of Euler theorem relative to the totient function 'and
the algorithm the computes the pair (s;ms)that verifies the Diophantine
equationa'(ms)as(modm), where a;m2N.
In chapter 5 we define a function Lwhich will allow us to (separately
or simultaneously) generalize many theorems from Number Theory ob-
1where (m; n) isgcd(m; n) that is the greatest common divisor of nandm
xv INTRODUCTION
tained by Wilson, Fermat, Euler, Gauss, Lagrange, Leibniz, Moser, and
Sierpinski.
Various analytical solutions to Diophantine equations such as: the sec-
ond degree equation, the linear equation with nunknown, linear systems,
thendegree equation with one unknown, Pell general equation, and the
equationx2 2y4= 1. For each of this cases, in chapter six we present
symbolic computation that ensure the detection of the solutions for the
particular Diophantine equations.
Chapter seven describes the solutions to the –Diophantine equations
using the search algorithms in the search domains.
The Conclusions and Index section conclude the book.
Chapter 1
Prime numbers
A prime number (or a prime) is a natural number greater than 1 that
has no positive divisors other than 1and itself. A natural number greater
than 1 that is not a prime number is called a composite number. For exam-
ple,7is prime because 1and7are its only positive integer factors, whereas
10is composite because it has the divisors 2and5in addition to 1and10.
The fundamental theorem of Arithmetics, [Hardy and Wright, 2008, p. 2-
3], establishes the central role of primes in the Number Theory: any integer
greater than 1can be expressed as a product of primes that is unique up to
ordering. The uniqueness in this theorem requires excluding 1as a prime
because one can include arbitrarily many instances of 1in any factoriza-
tion, e.g., 5,15,115, etc. are all valid factorizations of 5, [Estermann,
1952, Vinogradov, 1955].
The property of being prime (or not) is called primality. A simple but
slow method of verifying the primality of a given number nis known as
trial division. It consists of testing whether nis a multiple of any integer
between 2andbpnc. The floor function bxc, also called the greatest integer
function or integer value [Spanier and Oldham, 1987], gives the largest
integer less than or equal to x. The name and symbol for the floor function
were coined by Iverson, [Graham et al., 1994]. Algorithms much more
efficient than trial division have been devised to test the primality of large
1
2 CHAPTER 1. PRIME NUMBERS
numbers. Particularly fast methods are available for numbers of special
forms, such as Mersenne numbers. As of April 2014, the largest known
prime number 257885161 1has17425170 decimal digits [Caldwell, 2014a].
There are infinitely many primes, as demonstrated by Euclid around
300 BC. There is no known useful formula that sets apart all of the prime
numbers from composites. However, the distribution of primes, that is to
say, the statistical behavior of primes in the large, can be modelled. The
first result in that direction is the prime number theorem, proven at the end
of the 19th century, which says that the probability that a given, randomly
chosen number nis prime is inversely proportional to its number of digits,
or to log(n).
Many questions around prime numbers remain open, such as Gold-
bach’s conjecture, and the twin prime conjecture, Diophantine equations
that have integer functions. Such questions spurred the development of
various branches of the Number Theory, focusing on analytic or algebraic
aspects of numbers. Prime numbers give rise to various generalizations in
other mathematical domains, mainly algebra, such as prime elements and
prime ideals.
1.1 Generating prime numbers
The generation of prime numbers can be done by means of several
deterministic algorithms, known in the literature, as sieves: Sieve of Er-
atosthenes, Sieve of Euler, Sieve of Sundaram, Sieve of Atkin, etc. In this
volume we will detail only the most efficient prime number generating
algorithms.
The Sieve of Eratosthenes is an algorithm that allows the generation of
all prime numbers up to a given limit L2N. The algorithm was given by
Eratosthenes around 240 BC.
Program 1.1.Let us consider the origin of vectors and matrices 1, which
can be defined in Mathcad by assigning ORIGIN := 1 . The Sieve of Er-
atosthenes in the linear variant of Pritchard, presented in pseudo code in
the article [Pritchard, 1987], written in Mathcad is:
1.1. GENERATING PRIME NUMBERS 3
CEP (L) :=fork21::L
isprimek 1
k 2
whilek2L
j k2
whilejL
isprimepj 0
j j+k
k k+ 1
j 1
fork21::L
if isprimek=1
primej k
j j+ 1
returnprime
It is well known that the segmented version of the Sieve of Eratosthenes,
with basic optimizations, uses O(L)operations and
Op
Llog(log(L))
log(L)
bits of memory, [Pritchard, 1987, 1994].
The linear variant of the Sieve of Eratosthenes implemented by
Pritchard, given by the code 1.1, has the inconvenience that is repeats use-
lessly operations. For example, for L= 25 , in table (1.1) is given the binary
vectorisprime which contains at each position the values 1or0. On the
first line is the index of the vector.
1. Initially, all the positions of vector isprime have the value 1.
2. Forq= 2the algorithm puts 0on all the positions isprimekmultiple
of2, forkq2= 4.
3. Forq= 3the algorithm puts 0on all the positions isprimekmultiple
of3, forkq2= 9, which means positions 9,12,15,18,21and24
4 CHAPTER 1. PRIME NUMBERS
qnisprime 1 2 3 4 5 6 7 8 9 10 11 12
0 1 1 1 1 1 1 1 1 1 1 1
2 0 0 0 0 0
3 0 0
4
5
0 1 1 0 1 0 1 0 0 0 1 0
13 14 15 16 17 18 19 20 21 22 23 24 25
1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0
0 0 0
0
1 0 0 0 1 0 1 0 0 0 1 0 0
Table 1.1: The vector isprime in the code 1.1
but positions 12,18and24were already annulated in the previous
step.
4. Forq= 4the algorithm puts 0on all the positions isprimekmultiple
of4, forkq2= 16 , which means positions 16,20,24, but these
positions were annulated also in the second step, and on position 24
is taken 0for the third time.
5. Forq= 5one takesisprimeq2= 0.
Eventually, vector isprime is read. The index of vector isprime ,
which has the value 1, is a prime number. If we count the number of at-
tributing the value 0, we remark that this operation was made 21time. It
is obvious that these repeated operations make the algorithm less efficient.
1.1. GENERATING PRIME NUMBERS 5
Program 1.2.This program is a better version of program 1.1 because it
puts 0only on the odd positions of the vector isprime .
CEPi (L) :=fork23;5::L
isprimek 1
fork23;5::floor (p
L)
forj2k2;k2+ 2k::L
isprimej 0
prime 1 2
j 2
fork21;3::L
if isprimek=1
primej k
j j+ 1
returnprime
Program 1.3.This program is a better version of program 1.2 because it
uses a minimal memory space.
CEPm (L) := floor L
2
fork21::
isprimek 1
fork23;5::floor (p
L)
forj2k2;k2+ 2k::L
isprimej 1
2 0
prime 1 2
j 2
fork21:: 1
if isprimek=1
primej 2k+ 1
j j+ 1
returnprime
Even the execution time of the program 1.3 is a little longer than of the
program 1.2, the best linear variant of the Sieve of Eratosthenes is the pro-
6 CHAPTER 1. PRIME NUMBERS
gram 1.3, as it provides an important memory economy ( 11270607 mem-
ory locations instead of 21270607 , the amount of memory locations used
by programs 1.1 and 1.2).
Program 1.4.The program for the Sieve of Eratosthenes, Pritchard variant,
was improved in order to allow the number of repeated operations to di-
minish. The improvement consists in the fact that attributing 0is done for
only odd multiples of prime numbers. The program has a restriction, but
which won’t cause inconveniences, namely Lmust be a integer greater
than 14.
CEPb (L) :=fork23;5::L
isprimek 1
prime (2 3 5 7)T
i last(prime ) + 1
forj29;15::L
isprimej 0
k 3
s (primek 1)2
t (primek)2
whiletL
forj2t;t+ 2primek::L
isprimej 0
forj2s+ 2;s+ 4::t 2
if isprimej= 1
primei j
i i+ 1
s t
k k+ 1
t (primek)2
forj2s+ 2;s+ 4::L
if isprimej=1
primei j
i i+ 1
returnprime
1.1. GENERATING PRIME NUMBERS 7
We remark that it is not necessary to put 0on each positions
(primek)2+primek, as in the original version of the program 1.1, because
the sum of two odd numbers is an even number and the even positions are
not considered. In this moment of the program we are sure that the posi-
tions from (primek 1)2+ 2 to(primek)2 2of the vector isprime (from
2 in 2) which were left on 1(which means that their indexes are prime
numbers), can be added to the prime numbers vector. Hence, instead of
building the vector prime at the end of the markings, we do it in interme-
diary steps. The advantage consists on the fact that we have a list of prime
numbers which can be used to obtain the other primes, up to the given
limitL.
Program 1.5.The program that improves the program CEPb by halving the
used memory space.
CEPbm (L) := floor L
2
fork21::
isprimek 1
prime (2 3 5 7)T
i last(prime ) + 1
forj24;7::
isprimej 0
k 3
s (primek 1)2
t (primek)2
whiletL
forj2t;t+ 2primek::L
isprimej 1
2 0
forj2s+ 2;s+ 4::t 2
if isprimej 1
2= 1
primei j
i i+ 1
s t
k k+ 1
t (primek)2
8 CHAPTER 1. PRIME NUMBERS
forj2s+ 2;s+ 4::L
if isprimej 1
2=1
primei j
i i+ 1
returnprime
The performances of the 5 programs can be observed on the following
execution sequences (the call of the programs have been done on the same
computer and in similar conditions):
1. Call of the program CEP1.1, i.e. the Sieve of Eratosthenes in the lin-
ear version of Pritchard
L:= 2107t0:=time(0)p:=CEP (L)t1:=time(1)
(t1 t0)sec= 28:238s last (p) = 1270607 plast(p)= 19999999 ;
2. Call of the program CEPm1.3,
L:= 2107t0:=time(0)p:=CEPm (L)t1:=time(1)
(t1 t0)sec= 10:920s last (p) = 1270607 plast(p)= 19999999 :
3. Call of the program CEPi1.2,
L:= 2107t0:=time(0)p:=CEPi (L)t1:=time(1)
(t1 t0)sec= 7:231s last (p) = 1270607 plast(p)= 19999999 ;
4. Call of the program CEPb1.4,
L:= 2107t0:=time(0)p:=CEPb (L)t1:=time(1)
(t1 t0)sec= 5:064s last (p) = 1270607 plast(p)= 19999999
5. Call of the program CEPbm1.5,
L:= 2107t0:=time(0)p:=CEPb (L)t1:=time(1)
(t1 t0)sec= 7:133s last (p) = 1270607 plast(p)= 19999999
1.1. GENERATING PRIME NUMBERS 9
In the comparative table 1.2 are presented the attributions of 0, the exe-
cution times on a computer with a processor Intel of 2.20GHz with RAM of
4.00GB (3.46GB usable) and the number of memory units for the programs
1.1, 1.3, 1.2, 1.4 and 1.5.
program Attributions of 0Execution time Memory used
1.1 71 760 995 28.238 sec 21 270 607
1.3 35 881 043 10.920 sec 11 270 607
1.2 35 881 043 7.231 sec 21 270 607
1.4 18 294 176 5.064 sec 21 270 607
1.5 18 294 176 7.133 sec 11 270 607
Table 1.2: Comparative table
The Sieve of Sundaram is a simple deterministic algorithm for finding
the prime numbers up to a given natural number. This algorithm was
presented by Sundaram and Aiyar [1934]. As it is known, the Sieve of
Sundaram uses O(Llog(L))operations in order to find the prime numbers
up toL. The algorithm of the Sieve of Sundaram in pseudo code Mathcad
is:
CS(L) :=m floorL
2
fork21::m
isprimek 1
fork21::m
forj21::ceilm k
2k+ 1
isprimek+j+2kj 0
prime 1 2
j 1
fork21::m
if isprimek=1
j j+ 1
primej 2k+ 1
10 CHAPTER 1. PRIME NUMBERS
Figure 1.1: The ratio of the numbers of operations
returnprime
The Call of the program CS
L:= 2107t0:=time(0)p:=CS(L)t1:=time(1)
(t1 t0)sec= 32:706s last (p) = 1270607 plast(p)= 19999999
Until recently, i.e. till the appearance of the Sieve of Atkin, [Atkin
and Bernstein, 2004], the Sieve of Eratosthenes was considered the most
efficient algorithm that generates all the prime numbers up to a limit
L. The figure 1.1 emphasize the graphic representation of the ratio be-
tween the number of operations needed for the Sieve of Eratosthenes,
OE(L) :=O(Llog(log(L))), and the number of operations needed for
the Sieve of Atkin, OA(L) :=O(L=log(log(L))), forL= 102;103;:::; 1020.
In this figure one can see that the Sieve of Atkin is better (relative to the
number of operations needed by the program) then the Sieve of Eratos-
thenes, for L>1010.
Program 1.6.The Sieve of Atkin in pseudo code presented in Mathcad is:
Atkin (L) :=fork25::L
isprimek 0
forx21::p
L
fory21::p
L
n 4×2+y2
if nL^
mod(n;12)=1_mod(n;12)=5
1.1. GENERATING PRIME NUMBERS 11
isprimen :isprimen
n 3×2+y2
if nL^mod(n; 12)=7
isprimen :isprimen
n 3×2+y2
if x6=y^nL^mod(n; 12)=11
isprimen :isprimen
forn25::p
L
if isprimen
fork21::L
n2
isprimekn2 0
prime 1 2
prime 2 3
j 3
forn25::L
if isprimen
primej n
returnprime
As it is known, this algorithm uses only O(L=log(log(L))) simple op-
erations and O(L1=2+o(1))memory locations, [Atkin and Bernstein, 2004].
Our implementation, in Mathcad, of Atkin’s algorithm contains some
remarks that make the program have more performance than the original
algorithm.
1. Except 2all even numbers are not prime, it follows that, with the
initialization isprime 2k 0fork2f2;3;:::;L= 2g, there is no need
to change the values of these components. Consequently, we will
change only the odd components.
2. Ifjis odd then 4k2+j2is always odd. It follows that the sequence
j2n
1;3::jp
Lko
andk2(
1;2::$p
L j2
2%)
(1.1)
12 CHAPTER 1. PRIME NUMBERS
assures that the number 4k2+j2is always odd.
3. Ifjandkhave different parities, Then 3k2+j2is odd. Then the
sequence
j2n
1;2;::jp
Lko
andk0=mod(j;2) + 1; k2(
k0;k0+ 2::$r
L j2
3%)
(1.2)
assures that 3k2+j2is odd.
4. Ifk>j andkandjhave different parities, then 3k2 j2is odd. Then
the sequence
j2n
1;2;::jp
Lko
andk2(
j+ 1;j+ 3::$r
L+j2
3%)
(1.3)
assures that 3k2 j2is odd.
5. Similarly as in 1, we will eliminate only the perfect squares for odd
numbers5, because only these are odd.
Program 1.7.AO program (Atkin optimized) of generating prime numbers
up toL.
AO(L) :=isprimeL 0
floor p
L
forj21::ceil ()
fork21::ceilp
L j2
2
n 4k2+j2
m mod(n;12)
isprimen :isprimenif nL^(m=1_m=5)
fork21::ceilq
L j2
3
1.1. GENERATING PRIME NUMBERS 13
n 3k2+j2
isprimen :isprimenif nL^mod(n;12)=7
fork2j+ 1::ceilq
L+j2
3
n 3k2 j2
isprimen :isprimenif nL^mod(n;12)=11
forj25;7::
fork21;3::L
j2if isprimej
isprimekj2 0
prime 1 2
prime 2 3
forn25;7::L
if isprimen
primej n
j j+ 1
returnprime
In this program function ceilwas used (which means de) instead of func-
tionfloor (which meansbc) in formulas (1.1), (1.2) and (1.3), in order to
avoid errors of floating comma which could determine the loss of cases at
limitL, for example, when Lis a perfect square.
1. Call of the program 1.6 the Sieve of Atkin
L:= 2107t0:=time(0)p:=Atkin (L)t1:=time(1)
(t1 t0)s= 23:531s plast(p)= 19999999 last(p) = 1270607 ;
2. Call of the program 1.7 the optimized Sieve of Atkin
L:= 2107t0:=time(0)p:=AO(L)t1:=time(1)
(t1 t0)s= 19:45s plast(p)= 19999999 last(p) = 1270607 ;
There exists an implementation for the Sieve of Atkin, due to Bernstein
[2014] under the name Primgen .Primegen is a library of programs for fast
14 CHAPTER 1. PRIME NUMBERS
generating prime numbers, increasingly. Primegen generates all 50847534
prime numbers up to 109in only 8 seconds on a computer with a Pentium
II-350 processor. Primegen can generate prime numbers up to 1015.
1.2 Primality tests
A central problem in the Number Theory is to determine weather an
odd integer is prime or not. The test than can establish this is called pri-
mality test.
Primality tests can be deterministic or non-deterministic. The de-
terministic ones establish exactly if a number is prime, while the non-
deterministic ones can falsely determine that a composite number is
prime. These test are much more faster then the deterministic ones. The
numbers that pass a non-deterministic primality test are called probably
prime (this is denoted by prime? ) until their primality is deterministically
proved. A list of probably prime numbers are Mersenne’s numbers, [Cald-
well, 2014b]:
M43= 230402457 1, Dec. 2005 – Curtis Cooper and Steven Boone,
M44= 232582657 1, Sept. 2006 – Curtis Cooper and Steven Boone,
M45= 237156667 1, Sept. 2008 – Hans-Michael Elvenich,
M46= 242643801 1, Apr. 2009 – Odd Magnar Strindmo,
M47= 243112609 1, Aug. 2008 – Edson Smith,
M48= 257885161 1, Jan. 2013 – Curtis Cooper.
1.2.1 The test of primality
As seen in Theorem 2.3, we can use as primality test the computing of
the value of function. For n>4, if relation (n) =nis satisfied, it follows
thatnis prime. In other words, the prime numbers (to which number 4
is added) are fixed points for function. In this study we will use this
primality test.
1.2. PRIMALITY TESTS 15
Program 1.8.The program for primality test. The program returns the
value 0if the number is not prime and the value 1if the number is prime.
File:prn is read and assigned to vector .
ORIGIN := 1:=READPRN (":::n:prn ")
Tp(n) :=return "Errorn< 1ornotinteger "if n< 1_n6=trunc (n)
if n> 4
return 0if n6=n
return 1otherwise
otherwise
return 0if n=1_n=4
return 1otherwise
By means of the program 1.8 was realized the following test.
n:= 499999k:= 1::n vk:= 2k+ 1
last(v) = 499999 v1= 3vlast(v)= 999999
t0:=time(0)wk:=Tp(vk)t1:=time(1)
(t1 t0)sec= 0:304sX
w= 78497:
The number of prime numbers up to 106is78798 , and the sum of non-zero
components (equal to 1) is 78797 , as2was not counted as prime number
because it is an even number. We remark that the time needed by the
primality test of all odd numbers is 0:304sa much more better time than
the8snecessary for the primality test 1.11 on a computer with an Intel
processor of 2.20GHz with RAM of 4.00GB (3.46GB usable).
1.2.2 Deterministic tests
Proving that an odd number nis prime can be done by testing sequen-
tially the vector pthat contains prime numbers.
The browsing of the list of prime numbers can be improved by means
of the function that counts the prime numbers [Weisstein, 2014e]. Tradi-
tionally, by (x)is denoted the function that indicates the number of prime
16 CHAPTER 1. PRIME NUMBERS
numberspx, [Shanks, 1962, 1993, p. 15]. The notation for the function
that counts the prime numbers is a little bit inappropriate as it has nothing
to do with, The universal constant that represents the ratio between the
length of a circle and its diameter. This notation was introduced by the
number theorist Edmund Landau in 1909 and has now become standard,
[Landau, 1958] [Derbyshire, 2004, p. 38]. We will give a famous result
of Rosser and Schoenfeld [1962], related to function (x). Let functions
s; d: (1;+1)!R+given by formulas
s(x) =x
ln(x)
1 +1
2 ln(x)
(1.4)
and
d(x) =x
ln(x)
1 +3
2 ln(x)
: (1.5)
Theorem 1.9. Following inequalities
s(x)<(x)<d(x); (1.6)
hold, for all x > 1, the right side inequality, and for all x59the left side
inequality.
Proof. See [Rosser and Schoenfeld, 1962, T. 1].
Let functions f; m; M:N!Nbe defined by formulas:
f(n) =n
ln(n)
1 +1
2 ln(n)
;
m(n) =8
>>>><
>>>>:f(n) 2ifn<11
f(n) 1if11n39
f(n) ifn>39; (1.7)
M(n) =n
ln(n)
1 +3
2 ln(n)
; (1.8)
1.2. PRIMALITY TESTS 17
wherebcis the lower integer part function and deis the upper integer
part function. As a consequence of Theorem 1.9 we have
Theorem 1.10. Following inequalities
m(n)<(x)<M(n) (1.9)
hold, for all n22N+ 1, where by 2N+ 1 is denoted the set of natural odd
numbers.
Proof. As function d(n)M(n)for alln2N, it results, according to
Theorem 1.9, that the right side inequality is true for all n2N, hence,
also forn22N+ 1.
Figure 1.2: Functions M(n),(n)andm(n)
Asm(n)s(n)for alln2N, and the left side inequality (1.6) holds
for alln59, it follows that the left side inequality (1.9) holds for all
n59.
18 CHAPTER 1. PRIME NUMBERS
Forn2f3;5;7;:::; 59gwe have:
(3) m(3) = 1
(5) m(5) = 1
(7) m(7) = 2
(9) m(9) = 1
(11) m(11) = 1
(13) m(13) = 1
(15) m(15) = 1
(17) m(17) = 1
(19) m(19) = 2
(21) m(21) = 1
(23) m(23) = 2
(25) m(25) = 2
(27) m(27) = 1
(29) m(29) = 2(31) m(31) = 2
(33) m(33) = 2
(35) m(35) = 1
(37) m(37) = 2
(39) m(39) = 1
(41) m(41) = 1
(43) m(43) = 2
(45) m(45) = 1
(47) m(47) = 2
(49) m(49) = 1
(51) m(51) = 1
(53) m(53) = 1
(55) m(55) = 1
(57) m(57) = 1
(59) m(59) = 1(1.10)
we analyze table 1.10 (see also 1.2) we can say that the left side inequality
(1.9) holds for all n22N+ 1.
Theorem 1.10 allows us to find a lower and an upper margin for the
number of prime numbers up to the given odd number. Using the bisec-
tion method, one can efficiently determine if the given odd numbers is in
the list of prime numbers or not.
The function that counts the maximum number of necessary tests for
the bisection algorithm to decide if number Nis prime, is given by the
formula:
nt(N) =dlog2
M(N) m(N)
e (1.11)
The algorithm is efficient. For example, for numbers N,107< N < 108,
the algorithm will proceed between 16and19necessary tests for the bisec-
tion algorithm, at the worst (see figure 1.3).
For all programs we have considered ORIGIN := 1 . By means of the
algorithm 1.4 (The Sieve of Eratosthenes, Pritchard’s improved version)
1.2. PRIMALITY TESTS 19
Figure 1.3: The graph of function nt(10n)forn= 2;3;:::; 8
and of command
p:=CEPb (2107)
all prime numbers up to 2107are generated in vector p.
Program 1.11.The program is an efficient primality test for N. A binary
search is used (the bisection algorithm), i.e., if N, which finds itself be-
tween the prime numbers p`andpr, is in the list of prime numbers p.
Cb(N;`;r ) :=while`<r
M `+r
2
m ceil(M)
return 1if N =pm
` m if N >p m
r floor (M)if N <p m
return 0
The subprogram 1.11 calls the components pkof the vector that contains
the prime numbers. If Nis prime, the subprogram returns 1, if Nis not
prime, it returns 0. The necessary time to test the primality of all odd
numbers up to 106is8:283secon a 2.2 GHz processor.
20 CHAPTER 1. PRIME NUMBERS
Other deterministic tests:
1. Pepin’s test or the p 1test. If we study attentively a list that contains
the greatest known prim numbers, p, we will remark that most of
them has a particular form, namely, p 1orp+ 1and can be decom-
posed very fast. This result is not unexpected as there exist deter-
ministic primality tests for such numbers. In 1891, Lucas, [Williams,
1998], has converted the Fermat’s Little Theorem into a practical pri-
mality test, improved afterwards by Kraitchik and Lehmer [Brillhart
et al., 1975], [Dan, 2005].
2. n+1 tests or Lucas-Lehmer test for Mersenne numbers. Approxi-
mately half of the prime numbers in the list that contains the greatest
known prim numbers are of the form N 1, whereNcan be easily
factorized.
Program 1.12.The program for Lucas-Lehmer algorithm is:
LL(n) :=return "Errorn< 3orn> 53"if n2_n54
M 2n 1
f Fa(n)
return (M"isnotprime ")if(f1;1)2<n
s 4
fork21::n 2
S s2 2
s mod(S;M )
return "Error "if floor S
M
M+s6=S
return (M"isprime ")if s=0
return (M"isprime ")otherwise
Run examples:
LL(11) = (2047 " isnotprime ")LL(13) = (8191 " isprime ")
LL(19) = (524287 " isprime ")LL(23) = (8388607 " isnotprime "):
1.2. PRIMALITY TESTS 21
3. The Miller-Rabin test. If we apply the Miller’s test for numbers lesser
than 2:51010but different from 3215031751 , and they pass the test
for basis 2,3,5and7, they are prime. Similarly, if we apply a test
in seven steps, the previously obtained results allow to verify the
primality of all prime numbers up to 3:41014. If we choose 25 itera-
tions for Miller’s algorithm applied to a number, the probability that
this is not composite is lesser than 2 50. Hence, the Miller-Rabin test
becomes a deterministic test for numbers lesser than 3:41010;[Dan,
2005].
Program 1.13.The program for Miller-Rabin test is:
MR(n) :=return "Errorn< 2orneven "if n< 2_mod(n;2) = 1
s 0
t n 1
whilemod (t;2) = 0
s s+ 1
t t
2
pn
2
fork21::25
b 2 + 2floor (rnd()) + 1
y RRP (b;t;n )
if y6= 1^y6=n 1
j 1
whilejs 1^j6=n 1
y mod(y2;n)
return 0if y=1
j j+ 1
return 0if y6=n 1
return 1
The test of the program ha been made for n= 247 1>3:41010and
cun= 219 1.
MR(247 1) = 0MR(219 1) = 1
22 CHAPTER 1. PRIME NUMBERS
n= 247 1is indeed a composite number
Fa(247 1) =0
@2351 1
4513 1
13264529 11
A;
and219 1 = 524287 is a prime number. For factorization of a natural
numbers has been done with the programs Fa, 1.29, emphasized in
Section 1.3.1 .
The program MR calls the program RRP for repeatedly squaring
modulom, i.e. it calculates mod(bn;m)for great numbers.
RRP (b;n;m ) :=N 1
returnN if n =0
A b
a Cb2(n)
N bif a 0=1
fork21::last (a)
A mod(A2;m)
N mod(AN;m )if ak=1
returnN
The test of this program has been made on following example:
RRP (5;596;1234) = 1013 ;
provided in the paper [Dan, 2005, p. 60]. Concerning this program, it
calls a program for finding the digits of basis 2for a decimal number.
Cb2(n) :=j 0
c0 n
whiletrunccj
2
=0
rj mod(cj;2)
j j+ 1
1.2. PRIMALITY TESTS 23
cj trunccj 1
2
rj cj
returnr
The test of this program is made by following example:
Cb2(107) =0
BBBBBBBB@1
1
0
1
0
1
11
CCCCCCCCA:
4. AKS test. Agrawal, Kayal and Saxena, [Agrawal et al., 2004], have
found a deterministic algorithm, relative easy, that isn’t based on
any unproved statement. The idea of AKS test results form a simple
version of the Fermat’s Little Theorem . The AKS algorithm is:
INPUT a natural number >2;
OUTPUT 0ifnis not prime, 1ifnis prime;
1. Ifnis of the form ab, withb>1, then return: nis not prime and
stop the algorithm.
2. Letr 2.
3. As long as r<n ; execute:
3.1. If (n;r)6= 1, return:nis not prime and stop the algorithm.
3.2. Ifr2and it is prime, then execute: let qbe the great-
est factor of r 1, then, ifq > 4prlg(n)andn(r 1)=q6= 1
(modr ), then go to item 4.
3.3. Letr r+ 1.
4. Forafrom 1 to 2prlg(n), execute:
4.1. If (x a)n6=xn a(modxr 1;n), then return: nis not
prime and stop the algorithm.
5. Return:nis prime and stop the algorithm.
24 CHAPTER 1. PRIME NUMBERS
1.2.3 Smarandache’s criteria of primality
In this section we present four necessary and sufficient conditions for
a natural number to be prime, [Smarandache, 1981b].
Definition 1.14. We say that integers aarebcongruent modulo m
denotedab(modm )
if and only if mja b
i.e.mdividesa b
ora b=km, wherek2Z,k6= 1andk6=m
i.e.mis a proper factor of
a b
. Therefore, we have
ab(modm ),mod(a b;m) = 0; (1.12)
wheremod(x;y)is the function that returns the rest of the division of xby
y, withx;y2Z.
In 1640 Fermat shows without demonstrate the following theorem:
Theorem 1.15 (Fermat) .Ifa2Nandpis prime and p-a, then
ap 11 (modp ):
The first proof of the this theorem was given in 1736 by Euler.
Theorem 1.16 (Wilson) .Ifpis prime, then
(p 1)! + 10 (modp ):
The theorem Wilson 1.16 was published by Waring [1770], but it was
known long before even Leibniz.
Theorem 1.17. Letp2N,p3, thenpis prime if and only if
(p 3)!p 1
2(modp ): (1.13)
Proof.
Necessity :pis prime)(p 1)! 1 (modp )conform to Wilson’s
theorem 1.16. It results that (p 1)(p 2)(p 3)! 1 (modp ), or2(p 3)!
p 1 (modp ). Butpbeing a prime number 3it results that (2;p) = 1
1.2. PRIMALITY TESTS 25
and(p 1)=22Z. It has sense the division of the congruence by 2, and
therefore we obtain the conclusion.
Sufficiency : We multiply the congruence (p 3)!(p 1)=2 (modp )
with (p 1)(p 2)2 (modp ), [Popovici, 1973, pp. 10-16], and it results
that(p 1)! 1 (modp )from Wilson’s theorem 1.16, which makes that
pis prime.
Program 1.18.The primality criterion (1.13), given by Theorem 1.17 can be
implemented in Mathcad as follows:
CSP 1(p) :=return 1if p< 3_p6=trunc (p)
return 1if mod
(p 3)! p 1
2;p
=0
return 0otherwise
The call of this criterion using the symbolic computation is:
CSP 1(2)! 1;
CSP 1(3:5)! 1;
CSP 1(61)! 1;
CSP 1(87)! 0;
CSP 1(127)! 1;
CSP 1(1057)! 0;
where 1indicates that the number is prime, 0the contrary and 1error,
i.e.p<3orpis not integer.
Lemma 1.19. Letmbe a natural number >4. Thenmis a composite number if
and only if (m 1)!0 (modm ).
Proof.
The sufficiency is evident conform to Wilson’s theorem 1.16.
Necessity :mcan be written as m=p1
1p2
2psswherepiprime
numbers, two by two distinct and i2N, for anyi2Is=f1;2;:::;sg.
Ifs6= 1 thenpi
i< m , for anyi2Is. Therefore p1
1p2
2pssare
distinct factors in the product (m 1)!, thus (m 1)!0 (modm ).
26 CHAPTER 1. PRIME NUMBERS
Ifs= 1 thenm=pwith2(because non-prime). When = 2
we havep < m and2p < m becausem > 4. It results that pand2pare
different factors in (m 1)!and therefore (m 1)!0 (modm ). When
>2, we havep<m andp 1<m , andpandp 1are different factors
in product (m 1)!.
Therefore (m 1)!0 (modm )and the lemma is proved for all cases.
Theorem 1.20. Letpbe a natural number p>4. Thenpis prime if and only if
(p 4)!( 1)[p
3]+1p+ 1
6
(modp ); (1.14)
where [x]is the integer part of x, i.e. the largest integer less than or equal to x.
Proof.
Necessity :(p 4)!(p 3)(p 2)(p 1) 1 (modp )from Wilson’s
theorem 1.16, or 6(p 4)!1 (modp );pbeing prime and greater than 4, it
results that (6;p) = 1 . It results that p= 6k1, withk2N.
1. Ifp= 6k 1, then 6j(p+ 1) and (6;p) = 1 , and dividing the
congruence 6(p 4)!p+ 1 (modp ), which is equivalent with the
initial one, by 6we obtain:
(p 4)!p+ 1
6( 1)[p
3]+1p+ 1
6
(modp ):
2. Ifp= 6k+ 1, then 6j(1 p)and (6;p) = 1 , and dividing the
congruence 6(p 4)!1 p(modp ), which is equivalent to the
initial one, by 6it results:
(p 4)!1 p
6 k( 1)[p
3]+1p+ 1
6
(modp ):
Sufficiency : We must prove that pis prime. First of all we’ll show that
p6=M6. Let’s suppose by absurd that p= 6k,k2N. By substituting
1.2. PRIMALITY TESTS 27
in the congruence from hypothesis, it results (6k 4)! k(mod 6k).
From the inequality 6k 5kfork2N, it results that kj(6k 5)!. From
22j(6k 4), it results that 2kj(6k 5)!(6k 4). Therefore 2kj(6k 4)!and
2kj6k, it results (conform with the congruencies’ property), [Popovici,
1973, pp. 9-26], that 2kj( k), which is not true; and therefore p6=M6.
From (p 1)(p 2)(p 3) 6 (modp )by multiplying it with the
initial congruence it results that:
(p 1)!( 1)[p
3]6p+ 1
6
(modp ):
Let’s consider lemma 1.19, for p>4we have:
(p 1)!0 (modp )ifpis not prime ;
1 (modp )ifpis prime ;
1. Ifp= 6k+ 2)(p 1)!6k60 (modp ).
2. Ifp= 6k+ 3)(p 1)! 6k60 (modp ).
3. Ifp= 6k+ 4)(p 1)! 6k60 (modp ).
Thusp6=M6 +rwithr2 f0;2;3;4g. It results that pis of the form:
p= 6k1,k2Nand then we have: (p 1)! 1 (modp ), which means
thatpis prime.
Program 1.21.The primality criterion (1.14), given by Theorem 1.20 can be
implemented in Mathcad as follows:
CSP 2(p) :=return 1if p< 5_p6=trunc (p)
m truncp
3
+ 1
n truncp+ 1
6
return 1if mod [(p 4)! ( 1)mn;p]=0
return 0otherwise
28 CHAPTER 1. PRIME NUMBERS
The call of this criterion using the symbolic computation is:
CSP 2(4)! 1;
CSP 2(5:5)! 1;
CSP 2(61)! 1;
CSP 2(87)! 0;
CSP 2(127)! 1;
CSP 2(1057)! 0;
where 1indicates that the number is prime, 0the contrary and 1error,
i.e.p<5orpis not integer.
Theorem 1.22. Ifpis a natural number p5, thenpis prime if and only if
(p 5)!rh+r2 1
24(modp ); (1.15)
where
h=hp
24i
andr=p 24h:
Proof.
Necessity : ifpis prime, it results that:
(p 5)!(p 4)(p 3)(p 2)(p 1) 1 (modp )
or
24(p 5)! 1 (modp ):
Butpcould be written as p= 24h+r, withr2f1;5;7;11;13;17;19;23g,
because it is prime. It can be easily verified that
r2 1
242f0;1;2;5;7;12;15;22gZ:
24(p 5)! 1 +r(24h+r)24rh+r2 1 (modp )
Because (24;p) = 1 and24j(r2 1)we can divide the congruence by 24,
obtaining:
(p 5)!rh+r2 1
24(modp ):
1.2. PRIMALITY TESTS 29
Sufficiency :pcan be written p= 24h+r,h;r2N,0r <24. Multi-
plying the congruence (p 4)(p 3)(p 2)(p 1)24 (modp )with the
initial one, we obtain: (p 1)!r(24h+r) 1 1 (modp ).
Program 1.23.The implementation of the primality criterion (1.15) given
by Theorem 1.22 is:
CSP 3(p) :=return 1if p< 5_p6=trunc (p)
h truncp
24
r p 24h
return 1if mod
(p 5)!
rh+r2 1
24
;p
=0
return 0otherwise
The call of this criterion using the symbolic computation is:
CSP 3(4)! 1;
CSP 3(5:5)! 1;
CSP 3(61)! 1;
CSP 3(87)! 0;
CSP 3(127)! 1;
CSP 3(1057)! 0;
where 1indicates that the number is prime, 0the contrary and 1error,
i.e.p<5orpis not integer.
Theorem 1.24. Let’s consider p= (k 1)!h1, withk>2a natural number.
Thenpis prime if and only if
(p k)!( 1)k+[p
h]+1h(modp ): (1.16)
Proof.
Necessity : Ifpis prime then, according to Wilson’s theorem 1.16, results
that (p 1)! 1 (modp ),( 1)k 1(p k)!(k 1)! 1 (modp ),
(p k)!(k 1)!( 1)k(modp ). We have:
((k 1)!;p) = 1: (1.17)
30 CHAPTER 1. PRIME NUMBERS
(A)p= (k 1)!h 1.
(a)kis an even number )(p k)!(k 1)!1 +p(modp ), and
because of the relation (1.17) and (k 1)!j(1 +p), by dividing
with (k 1)!we have: (p k)!h(modp ).
(b)kis an odd number )(p k)!(k 1)! 1 p(modp ), and
because of the relation (1.17) and (k 1)!j( 1 p), by dividing
with (k 1)!we have: (p k)! h(modp ).
(B)p= (k 1)!h+ 1.
(a)kis an even number )(p k)!(k 1)!1 p(modp ), and
because (k 1)!j(1 p)and of the relation (1.17), by dividing
with (k 1)!we have: (p k)! h(modp ).
(b)kis an odd number )(p k)!(k 1)! 1 +p(modp ), and
because (k 1)!j( 1+p)and of the relation (1.17), by dividing
with (k 1)!we have (p k)!h(modp ).
Putting together all these cases, we obtain: if p is prime, p= (k 1)!h1,
withk>2andh2N, then the relation (1.16) is true.
Sufficiency : Multiplying the relation (1.16) by (k 1)!it results that:
(p k)!(k 1)!(k 1)!h( 1)[p
h]+1( 1)k(modp ):
Analyzing separately each of these cases:
(A)p= (k 1)!h 1and
(B)p= (k 1)!h+ 1, we obtain for both, the congruence:
(p k)!(k 1)!( 1)k(modp )
which is equivalent (as we showed it at the beginning of this proof) with
(p 1)! 1 (modp )and it results that pis prime.
Program 1.25.The implementation of the primality criterion given by (1.16)
using the symbolic computation is:
1.2. PRIMALITY TESTS 31
CSP 4(p) :=return 1if p< 2_p6=trunc (p)
return 1if p=2
h 0
j 3
while (j 1)!p+ 1
if mod [p+ 1;(j 1)!]=0
h p+ 1
(j 1)!
k j
j j+ 1
return 0if h=0
return 1if modh
(p k)! ( 1)k+trunc(p
h)+1h;pi
=0
return 0otherwise
The test of the program 1.25 has been done as follows. We know that
we have 24 odd prime numbers up to 99. VectorIof odd numbers from 3
to99was generated with the sequence:
ORIGIN := 2j:= 2::50Ij:= 2j 1:
For each component of vector Iprogram 1.25 was called and the result
was assigned to vector v. As the values of vector vare1for prime numbers
and0for non-prime numbers, it follows that the sum of the components of
vectorvwill give the number of prime numbers. If this sum is 24, it follows
that criterion 1.16 and program 1.25 are correct for all odd numbers up to
99.
vj:=CSP 4(Ij)X
v= 24:
The call of this criterion using the symbolic computation is:
CSP 4(1)! 1;
CSP 4(2)! 1;
CSP 4(3:5)! 1;
CSP 4(47)! 1;
CSP 4(147)! 0;
CSP 4(149)! 1;
CSP 4(150)! 0:
32 CHAPTER 1. PRIME NUMBERS
where 1indicates that the number is prime, 0the contrary and 1error,
i.e.p<2orpis not integer.
1.3 Decomposition product of prime factors
The factorization problem of integers is: given a positive integer nlet
find its prime factors, which means the pairs (pi;i),piare distinct prime
numbers and iare positive integers, such that n=p1
1p2
2pss.
In the Number Theory, the factorization of integers is the process of
finding the divisors of a given composite number. This seems to be a trivial
problem, but for huge numbers there doesn’t exist any efficient factoriza-
tion algorithm, the most efficient algorithm has an exponential complex-
ity, relative to the numbers of digits. Hence, a factorization experiment of
a number containing 200 decimal digits was successfully ended only af-
ter several months. In this experiment were used 80 computers Opteron
processor of 2.2 GHz, connected in a network of Gigabit type.
Many algorithms were conceived to determine the prime factors of a
given number. They can vary very little in sophistication and complexity.
It is very difficult to build a general algorithm for this ”complex” comput-
ing problem, such that any additional information about the number or its
factors can be often useful to save an important amount of time.
The algorithms for factorizing an integer ncan be divided into two
types:
1. General algorithms. Algorithm trial division is:
INPUTn2N,n3,nis neither prime nor perfect square and b2N.
OUTPUT Smallest prime factor nif it is<b, otherwise failure.
1. forq2f2;3;5;7;11;:::;pg,pb.
1.1. Return qifmod(n;q) = 0 .
1.2. Otherwise continue.
2. Return failure.
1.3. DECOMPOSITION PRODUCT OF PRIME FACTORS 33
The number of steps for trial division is O(3pn)most of the time,
[Myasnikov and Backes, 2008].
2. Special algorithms. Their execution time depends on the special
properties of number n, as, for example, the size of the greatest prime
factor. This category includes:
(a) Therhoalgorithm of Pollard, [Pollard, 1975, Brent, 1980, Weis-
stein, 2014d];
(b) Thep 1algorithm of Pollard [Cormen et al., 2001];
(c) The algorithm based on elliptic curves [Galbraith, 2012];
(d) The Pollard-Strassen algorithm [Pomerance, 1982, Hardy et al.,
1990, Weisstein, 2014f], which was proved to be the fastest fac-
torization algorithm. For a2Nwe denotea=mod(a;n). Letc,
1cpn
F(x) = (x+ 1)(x+ 2)(x+c)2Z[x]
and
f(x) =F(x)2ZN[x]
then
c2! =cY
k=0f(kc):
This algorithm has the following steps:
INPUTn2N,n3,nis neither prime, nor perfect square, b2N.
OUTPUT If the smallest prime factor of nis<b, otherwise failure.
1. Compute c lp
bm
.
2. Determine the coefficients of polynomial f2ZN[x]:
f(x) =cY
k=1(x+k):
34 CHAPTER 1. PRIME NUMBERS
3. Compute gk2f0;1;:::;n 1gsuch that
gk=mod
f(kc);n
for0k<c:
4.1. If gcd(gk;n) = 1 for8k2 f0;1;:::c 1gthen return
failure.
4.2. On the contrary, let
k= minf0k<c ; gcd(gk;n)>1g:
5. Return minfd;mod(n;d) = 0; kc+ 1dkc+cg.
Pollard’s and Strassen’s integer factoring algorithm works cor-
rectly and uses O(M(p
b)M(log(n))(log(b) +log(log(n)))word
operations, where Mis the time for multiplication, and space
forO(p
blog(n))words, [Myasnikov and Backes, 2008, von zur
Gathen and Gerhard, 2013].
Program 1.26.This program uses the Schema of Horner [1819],
the fastest algorithm to compute the value of a polynomial,
[Cira, 2005]. The input variables are the vector awhich defines
the polynomial amxm+am 1xm 1+:::+a1x+a0andx.
Horner (a;x) :=m last(a)
f am
fork2m 1::0
f fx+ak
returnf
Program 1.27.Computation program for the coefficients of the
polynomial (x+ 1)(x+ 2)(x+c).
Prod (c) :=v (1 1)T
returnvif c =1
fork22::c
v stack (0;v) +stack (kv;0)
returnv
1.3. DECOMPOSITION PRODUCT OF PRIME FACTORS 35
Program 1.28.This program applies the Pollard-Strassen algo-
rithm for finding the smallest prime factor, not greater than b,
of numbern.
PS(n;b) :=c ceil p
b
C Prod (c)
fork20::c
ak mod(Ck;n)
fork20::c 1
gk mod(Horner (a;mod (kc;n));n)
dk gcd(gk;n)
returndkif dk>1
return "Fail"
This program calls programs 1.27 and 1.26. The program was
tested by means of following examples:
n:= 143b:=floor (pn) = 11PS(n;b) = 11
n:= 667b:=floor (pn) = 25PS(n;b) = 23
n:= 4009b:=floor (pn) = 63PS(n;b) = 19
n:= 10097b:=floor (pn) = 100PS(n;b) = 23
1.3.1 Direct factorization
The most easy method to find factors is the so-called ”direct search”. In
this method, all possible factors are systematically tested using a division
of testings to see if they really divide the given number. This algorithm is
useful only for small numbers ( <106).
Program 1.29.The program of factorization of a natural number. This pro-
gram uss the vector of prime numbers pgenerated by the Sieve of Eratos-
thenes, the fastest program that generates prime numbers up to a given
36 CHAPTER 1. PRIME NUMBERS
limit. The Call of the Sieve of Eratosthenes, the program 1.4, is made us-
ing the sequence:
L:= 2107t0=time(0)p:=CEPb (L)t1=time(1)
(t1 t0)s= 5:064s last (p) = 1270607 plast(p)= 19999999
Fa(m) :=return ("m= "m">thatthelastp2")if m> (plast(p))2
j 1
k 0
f (1 1)
whilempj
ifmod (m;pj)=0
k k+ 1
m m
pj
otherwise
f stack [f;(pj;k)]if k> 0
j j+ 1
k 0
f stack [f;(pj;k)]if k> 0
returnsubmatrix (f;2;rows (f);1;2)
We give a remark that can simplify the primality test in some cases.
Observation 1.30.Ifpis the first prime factor of nandp2>q=n
p, thenqis
a prime number. Hence, the decomposition in prime factors of number n
ispq.
Proof. Let us suppose that qis a composite number, which means q=
ab. Aspis the first prime factor of n, it follows that a;b > p . Hence, a
contradiction is obtained, namely n=pq=pab>p3>n. Therefore,
qis a prime number. Hence, the decomposition in prime factors of nis
pq.
1.3. DECOMPOSITION PRODUCT OF PRIME FACTORS 37
Examples of factorization:
Fa(236 1) =0
BBBBBBBBBB@3 3
5 1
7 1
13 1
19 1
37 1
73 1
109 11
CCCCCCCCCCA; Fa (320 1) =0
BBBB@2 4
5 2
11 2
61 1
1181 11
CCCCA;
Fa(117 1) =0
BB@2 1
5 1
43 1
45319 11
CCA; Fa (711 1) =0
BB@2 1
3 1
1123 1
293459 11
CCA:
1.3.2 Other methods of factorization
1. The method of Fermat and the generalized method of Fermat are rec-
ommended for the case where nhas two factors of similar extension.
For a natural number n, two integers are searched, xandysuch that
n=x2 y2. Thenn= (x y)(x+y)and we obtain a first decompo-
sition ofn, where one factor is very small. This factorization may be
inefficient if the factors aandbdo not have close values, it is possi-
ble to be necessaryn+1
2 pnverifications for testing if the generated
numbers are squares. In this situation we can use a generalized Fer-
mat ethod which applies better in such cases, [Dan, 2005].
2. The method of Euler of factorization can be applied for odd numbers
nthat can be written as the sum of two squares in two different ways
n=a2+b2=c2+d2
wherea;care even and c;dodd.
38 CHAPTER 1. PRIME NUMBERS
3. The method of Pollard- rhoor the Monte Carlo method. We suppose
that a great number nis composite. The simplest test, much more
faster than the method of divisions, is due to Pollard [1975]. It is also
called therhomethod, or the Monte Carlo method. This test has a
special purpose, used to find the small prime factors for a composite
number.
For the Pollard- rho algorithm, a certain function f:Zn!Znis
chosen, such that, for example, its values to be determined easily.
Hence,fis usually a polynomial function; for example f(x) =x2+a,
wherea6=f0;2g.
Pollard-rhoalgorithm with the chosen function f(x) =x2+ 1, is:
INPUT: A composite number n >2, which is not the power of a prime
number.
OUTPUT: A proper divisor of n.
1. Leta 2andb 2.
2. Fork= 1;2;:::, run:
2.1 Compute a mod(f(a);n)andb mod(f(b);n).
2.2 Compute d= (a b;n).
2.3 If 1<d<n , then return dproper divisor of nand stop the
algorithm.
2.4 Ifd=n, then return the message ” Failure, another function
must be chosen ”.
4. Pollardp 1method. This method has a special purpose, being used
for the factorization of numbers nwhich have a prime factor pwith
the property that p 1is a product of prime factors smaller than a
relative small number. Pollard p 1algorithm is:
INPUT: A composite number n >2, which is not the power of a prime
number.
OUTPUT: A proper divisor of n.
1.4. COUNTING OF THE PRIME NUMBERS 39
1. Choose a margin B.
2. Choose, randomly, an a,2an 1and compute d= (a;n).
Ifd2, returndproper divisor of nand stop the algorithm.
3. For every prim qB, run:
3.1. Compute `= [ln(n)=ln(q)].
3.2. Compute a mod
aq`;n
.
4. Compute d= (n 1;a).
5. Ifd= 1ord=n, then return the message ” E’sec ”, else, return d
proper divisor of nand stop the algorithm.
1.4 Counting of the prime numbers
1.4.1 Program of counting of the prime numbers
If we have the list of prime numbers, we can, obviously, write a pro-
gram to count them up to a given number x2N. We read the file of
prime numbers available on the site [Caldwell, 2014b] and we assign it to
vectorpwith the sequence:
p:=READPRN (":::nPrime:prn ")
last(p) = 6106plast(p)= 104395301 :
Command last(p)states that vector pcontains the first 6106prime num-
bers, and the last prime number of vector pis104395301 .
Program 1.31.Program for counting the prime numbers up to a natural
numberx.
(x) :=forn21::last (p)
if pnx
returnn 1if pn>x
returnnotherwise
40 CHAPTER 1. PRIME NUMBERS
For example, let us count the prime numbers up to 10n, forn= 1;2;:::; 8.
This counting can be made by using following commands:
n:= 1::8(10n) =0
BBBBBBBBBB@4
25
168
1229
9592
78498
664579
57614551
CCCCCCCCCCA:
1.4.2 Formula of counting of the prime numbers
By means of Smarandache’s function we obtain a formula for counting
the prime numbers less or equal to n, [Seagull, 1995].
Theorem 1.32. Ifnis an integer4, then
(n) = 1 +nX
k=2(k)
k
(1.18)
Proof. Knowing the (n)has the property that if p > 4then(p) =pif
only ifpis prime, and (n)<n for anyn, and(4) = 4 (the only exception
from the first rule), then
(k)
k
=1;ifkis prime
0;ifkis not prime:
We easily find an exact formula for the number of primes less than or equal
ton.
If we read the file :prn and attribute to the values of the vector the
sequence
ORIGIN := 1:=READPRN (":::n:prn ")
1.4. COUNTING OF THE PRIME NUMBERS 41
then formula (1.18) becomes:
(n) :=8
>>>>>>>>>>>>>>><
>>>>>>>>>>>>>>>:return "Errorn< 1orn =2Z"if n< 1_n6=trunc (n)
return 1 +nX
k=2jk
kk
if n4
return 2if n= 3
return 1if n= 2
return 0if n= 1
(1.19)
Using this formula, the number of primes up to n= 10 ,n= 102, . . . ,
n= 106has been determined and the obtained results are:
(10) = 4(102) = 25(103) = 168(104) = 1229
(105) = 9592(106) = 78498:
Chapter 2
Smarandache’s function
The function that associates to each natural number nthe smallest nat-
ural number mwhich has the property that m!is a multiple of nwas con-
sidered for the first time by Lucas [1883]. Other authors who have con-
sidered this function in their works are: Neuberg [1887], Kempner [1918].
This function was rediscovered by Smarandache [1980a]. The function is
denoted by Smarandache with Sor, and on the site Wolfram MathWorld ,
[Sondow and Weisstein, 2014], it is denoted . In this volume we have
adopted the notation found in the paper [Smarandache, 1999b].
Therefore, function :N!N,(n) =m, wheremis the smallest
natural that has the property that ndividesm!, (orm!is a multiple of
n) is known in the literature as Smarandache’s function . The values of the
function, for n= 1;2;:::; 18, are: 1,2,3,4,5,3,7,4,6,5,11,4,13,7,5,6,
17,6obtained by means of an algorithm that results from the definition of
function, as follows:
Program 2.1.
(n) =form = 1::n
returnmif mod (m!;n)=0
The program 2.1 can not be used for n19as the numbers 19!,20!,
. . . has much more than 17decimal digits and in the classic computation
42
43
Figure 2.1: function
approach (without an arithmetics of random precisions [Uznanski, 2014])
will be generated errors due to the classic representation in the memory of
computers.
Kempner [1918], gave an algorithm to compute (n)using the classic
factorization p1
1p2
2psswith prime numbers of n, and the generalized
base (i)[pi], fori=1;s. Partial solutions for algorithms that compute (n)
were given previously by Lucas and Neuberg, [Sondow and Weisstein,
2014] .
We give Kempner’s algorithm, that computes Smarandache’s function
. At the beginning, let us define the recursive sequence
aj+1=paj+ 1 withj= 1;2;::: anda1= 1;
wherepis a prime number. This sequence represents the generalized base
ofp. Asa2=p+ 1,a3=p2+p+ 1, . . . we can prove by induction that
aj= 1 +p+:::+pj 1=pj 1
p 1for8j2:
44 CHAPTER 2. SMARANDACHE’S FUNCTION
The value of , such thata<a+1, is given by the formula
=blogp
1 +(p 1)
c; (2.1)
wherebcis the function lower integer part . With the help Euclid’s algorithm
we can determine the unique sequences iandri, as follows
=a+r; (2.2)
r= 1a 1+r 1; (2.3)
…
r ( 2)= ( 1)a ( 1)+r ( 1); (2.4)
r ( 1)= a : (2.5)
which means, until the rest r = 0. At each step iis the integer part of
the ratiori=aiandriis the rest of the division. For example, for the first
step we have =b=acandr= a. Then, we have
(p) = (p 1)+X
i=i: (2.6)
In general, for
n=p1
1p2
2pss; (2.7)
the value of function is given by the formula:
(n) = maxf(p1
1);(p2
2);:::; (pss)g; (2.8)
formula due to Kempner [1918].
Remark 2.2.Ifn2Nhas the decomposition in product of prime numbers
(2.7), where piare prime numbers such that p1<p2<:::<p s, ands1,
then the Kempner’s algorithm of computing function is
(n) = max
p1
1[p1]
(p1); p2
2[p2]
(p2);
:::; ps
s[ps]
(ps)
;(2.9)
2.1. THE PROPERTIES OF FUNCTION 45
where
[p]
(p)means that is ”written ” in the generalized base p(denoted
[p]) and is ” read” in basep(denoted(p), where=[p]), [Smarandache,
1999a, p.39].
On the site The On-Line Encyclopedia of Integer Sequences , [Sloane, 2014,
A002034], is given a list of 1000 values of function , due to T. D. Noe. We
remark that on the site The On-Line Encyclopedia of Integer Sequences it is
defined(1) = 1 , while Ashbacher [1995] and Russo [2000] consider that
(1) = 0 .
2.1 The properties of function
The greater values for function are obtained for 4and for the prime
numbers and are (p) =p, [Sloane, 2014, A046022].
The smallest values for nare, [Sloane, 2014, A094371]:
(n)
n= 1;1
2;1
3;1
4;1
6;1
8;1
12;3
40;1
15;1
16;1
24;1
30; :::
for the values [Sloane, 2014, A002034]:
n= 1;6;12;20;24;40;60;80;90;112;120;180; :::
This function is important because it characterize the prime numbers –
by the following fundamental property.
Theorem 2.3. Letpbe an integer >4. Thenpis prime if and only if (p) =p.
Proof. See [Smarandache, 1999a, p. 31].
Hence, the fixed points of this function are prime numbers (to which 4
is added). Due to this property, function is used as a primality test.
46 CHAPTER 2. SMARANDACHE’S FUNCTION
The formula (2.9) used to compute Smarandache’s function allows
us to give several values of the function for particular numbers n
(1) = 1;
(n!) =n;
(p) =p;
(p1p2ps) =p1p2ps;
(p) =p;(2.10)
wherepandpiare distinct prime numbers with p1< p 2< ::: < p sand
p, [Kempner, 1918].
Other special numbers for which we can give the values of function
are:
(Pp) =Mp; (2.11)
whereP2= 6,P3= 28 ,P5= 496 ,P7= 8128 , . . . , [Sloane, 2014, A000396],
are the perfect numbers corresponding to the prime numbers 2,3,5,7, . . . ,
andM2= 22 1 = 3 ,M3= 23 1 = 7 ,M5= 25 1 = 31 ,M7= 27 1 = 127 ,
. . . , [Sloane, 2014, A000668], are Mersenne numbers corresponding to the
prime numbers prime 2,3,5,7, . . . , see the papers [Ashbacher, 1997, Ruiz,
1999a].
Functionhas following properties:
(n1n2)(n1) +(n2); (2.12)
maxf(n1);(n2)g(n1n2)(n1)(n2); (2.13)
wheren1;n22N.
Ifpis a prime number and 2an integer, then
pp
=p+1 p+p: (2.14)
This result is due to Ruiz [1999b].
The casepwith > p is more complicated to which applies the
Kempner’s algorithm.
According to formula (2.8), it results that for all n2Nwe have
(n)gpf(n); (2.15)
2.1. THE PROPERTIES OF FUNCTION 47
wheregpf(n)is the function the greatest prime factor ofn. Therefore, (n)
can be computed by determining gpf(n)and testing if njgpf(n)!. Ifnj
gpf(n)!then(n) =gpf(n), ifn-gpf(n)!then(n)> gpf(n)and we call
Kempner’s algorithm.
LetANa set of strictly nondecreasing positive integers. We denote
byA(n)the number of numbers of the set Aup ton. In what follows we
give the definition of the density of a set of natural numbers, [Guy, 1994,
p. 199].
Definition 2.4. We name density of a set AN, the number
lim
n!1A(n)
n;
if it exists.
For example, the density of the set of the even natural numbers is1=2be-
cause
lim
n!1bn
2c
n=1
2:
The set of numbers n2Nwith the property that n-gpf(n)!haszero
density , such as Erd ¨os [1991] supposed and Kastanas [1994] proved.
The first numbers with the property that n-gpf(n)!are:4,8,12,16,18,
24,25,27,32,36,45,48,49,50, . . . [Sloane, 2014, A057109].
If we denote by N(x)the number of numbers n2Nwhich have the
properties 2nxandn-gpf(n)!, then we obtain the estimation
N(x)xe 1
4p
ln(x); (2.16)
due to Akbik [1999], where the notation f(x)g(x)means that there
existsc2R+such thatjf(x)j<cjg(x)j,8x. As
N(x)
xe 1
4p
ln(x);and lim
x!1e 1
4p
ln(x)= 0;
we may say that the set has zero density .
48 CHAPTER 2. SMARANDACHE’S FUNCTION
This result was later improved by Ford [1999] and by the authors
De Koninck and Doyon [2003] . Ford proposed following asymptotic for-
mula:
N(x)p
1 + ln(2)
4p
234p
ln(x)3ln(ln(x))3x1 1
u0(u0); (2.17)
where(u)is the Dickman’s function, [Dickman, 1930, Weisstein, 2014a],
andu0is defined implicitly by equation
ln(x) =u0
x1
u2
0 1
: (2.18)
The estimation made in formula (2.17) was rectified by Ivi ´c [2003], in
two consecutive postings,
N(x) =x
2 +O s
ln(ln(x))
ln(x)!!Zx
2ln(x)
ln(t)ln(t)
t2dt; (2.19)
or, by means of elementary functions
N(x) =xexp
p
2 ln(x) ln(ln(x))
1 +Oln(ln(ln(x)))
ln(ln(x))
:(2.20)
Tutescu [1996] assumed that function does not have the same value
for two consecutive values of the argument, which means
8n2N; (n)6=(n+ 1):
Weisstein published, on the 3rd of March 2004, [Sondow and Weisstein,
2014], the fact that he has verified this result, by means of a program, up
to109.
Several numbers n2Nmay have the same value for function, i.e.
functionis not injective. In table 2.1 we emphasize numbers nfor which
(n) =k.
2.1. THE PROPERTIES OF FUNCTION 49
knfor which we have (n) =k
11
22
33, 6
44, 8, 12, 24
55, 10, 15, 20, 30, 40, 60, 120
66, 16, 18, 36, 45, 48, 72, 80, 90, 144, 240, 360, 720
Table 2.1: Values nfor which(n) =k
Leta(k)be the smallest inverse of (n), i.e. the smallest nfor which
(n) =k. Thena(k)is given by
a(k) =gpf(n)!;
where!=LX
i=1n 1
gpf(k)i
;andL=j
loggpf(k)(n 1)k
:(2.21)
This result was published by Sondow [2005]. For k= 1;2;:::, function
a(k)is equal to 1,2,3,4,5,9,7,32,27,25,11,243, . . . as seen in [Sloane,
2014, A046021].
Some values of (n)function are obtained for huge values of n. An
increasing sequence of great values of a(k)is1,2,3,4,5,9,32,243,4096 ,
59049 ,177147 ,134217728 ,31381059609 , . . . , (see [Sloane, 2014, A092233]),
the sequence that corresponds to n= 1,2,3,4,5,6,8,12,24,27,32,48,54,
. . . (see [Sloane, 2014, A092232]).
In the process of finding number nfor which(n) =k, we remark that
nis a divisor of (n)!but not of(n 1)!. Therefore, in order to find all
the numbers nfor each(n)has a value, we consider all nwith(n) =k,
wherenis in the set of all divisors of k!minus the divisors of (k 1)!. In
particular,b(k)ofnfor which(n) =k, fork>1is
b(k) =0(k!) 0
(k 1)!
; (2.22)
where0(m)is the divisors counting function of m. Hence, the number of
50 CHAPTER 2. SMARANDACHE’S FUNCTION
integersnwith(n) = 1 ,2, . . . are given by the sequence 1,1,2,4,8,14,30,
36,64,110, . . . (see [Sloane, 2014, A038024]).
Particularly, equation (2.22) shows that the inverse of Smarandache’s
function,a(n), exists always, as for each nthere exist an msuch that(n) =
m
i.e. the smallest a(n)
, because
0(n!) 0
(n 1)!
>0;
forn>1.
Sondow [2004] showed that (n)appears unexpectedly in an irrational
limit foreand it suppose that the inequality n2< (n)!holds for ” almost
everyn”, where ” almost every n” means the set of integers minus an excep-
tion set of zero density . The exception set is 2,3,6,8,12,15,20,24,30,36,
40,45,48,60,72,80, . . . , (see [Sloane, 2014, A122378]).
As equation gpf(n) =(n), considered by Erd ¨os [1991], Kastanas [1994]
for ” almost every n”, is equivalent with the inequality n2<gpf(n)!for ” al-
most everyn” of Sondow’s conjecture, it results that the conjecture of Erd ¨os
and Kastanas is equivalent with Sondow’s conjectures. The exception set,
in this case, of zero density is:2,3,4,6,8,9,12,15,16,18,20,24,25,27,30,
32,36, . . . , (see [Sloane, 2014, A122380]).
D. Wilson, underlines, in the case where
I(n;p) =n (n;p)
p 1; (2.23)
is a power of pprime inn!, where (n;p)is the function sum in base pofn,
then following relation
a(n) = min
pjnpI(n 1;p)+1; (2.24)
hold, where the minimum is reached for every prime number pthat di-
videsn. This minimum seems to be always attainable when p=gpf(n).
2.2 Programs for Kempner’s algorithm
In this section we emphasize Kempner’s algorithm by means of the
Mathcad programs necessary to the algorithm.
2.2. PROGRAMS FOR KEMPNER’S ALGORITHM 51
Program 2.5.The function that counts the digits in base pofn
ncb(n;p) :=returnceil (log(n;p))if n> 1
return 1otherwise
where the utility function Mathcad ceil()is the upper integer part func-
tion.
Program 2.6.The program that generates the generalized base p
denoted
by Smarandache [p]
for a number with mdigits
a(p;m) :=fori21::m
ai pi 1
p 1
returna
Program 2.7.The program that generates the base p
denoted by Smaran-
dache (p)
to write number
b(;p) :=return (1)if p= 1
fori21::ncb(;p)
bi pi 1
returnb
Program 2.8.The program of finding the digits of the generalized base [p]
for number n
Nbg(n;p) :=m ncb(n;p)
a a(p;m)
return (1)if m =0
fori2m::1
ci truncn
ai
n mod (n;ai)
returnc
Program 2.9.The program for Smarandache’s function
52 CHAPTER 2. SMARANDACHE’S FUNCTION
(n) :=return "Errornisnotinteger "if n6=trunc (n)
return "Errorn< 1"if n< 1
return (1)if n=1
f Fa(n)
p fh1i
fh2i
fork = 1::rows (p)
k pkNbg(k;pk)b(k;pk)
return max()
This program calls the program Fa(n)of factorization by prime numbers.
The program uses Smarandache’s remark 2.2 relative to Kempner’s algo-
rithm.
If we introduce number nas a product of prime numbers piraised at
poweri(iinteger0) it will result a variant of the program 2.9 which
can compute the values of function for huge numbers.
Program 2.10.The program for computing the values of function for huge
numbers.
s(f) :=Prop "Matrixf isnotatleastonerowwithtwocolumns "
returnPropif:(IsArray (f)^rows (f)1^cols(f)=2)
p fh1i
fh2i
fork = 1::rows (p)
k pkNbg(k;pk)b(k;pk)
return max()
Program 2.11.Program that generates the matrix that contains al values n
for which(n) =k.
EK(N) :=forn22::N
Kn (n)
forq22::max (K)
j 1
fork22::N
2.2. PROGRAMS FOR KEMPNER’S ALGORITHM 53
if Kk=q
EKq;j k
j j+ 1
returnEK
2.2.1 Applications
Several applications for the given programs are given in what follows:
1.Compute the values of function for numbers n1,n2given as products of
prime numbers raised at a positive integer power .
(a) Letn1= 2127131123= 895430243255334261261034 , then
n1:=0
@2 12
7 13
11 231
As(n1) = 242:
(b) Letn2= 3335557511111=
12589532854288041315477068297463914028063002 ;
then
n2:=0
BB@3 33
5 55
7 51
11 111
CCAs(n2) = 315;
2.Find the number whose factorial ends in 1000 zeros .
To answer this question we remark that for n= 101000we have
(n)! =M101000and this(n)is the smallest natural number whose
factorial ends in 1000 zeros. We have (n) =(2100051000), then
n:=2 1000
5 1000
s(n) = 4005
and, hence, the number whose factorial ends in 1000 zeros is 4005.
The numbers 4006 ,4007 ,4008 ,4009 have also the required property,
but 4010 has the property that its factorial has 1001 zeros.
54 CHAPTER 2. SMARANDACHE’S FUNCTION
3.Determine all values nfor which(n) = 7 .
With the help of program 2.11 we can generate the matrix that con-
tains all values nfor which(n) =k. Line 7of the matrix is the
answer to the problem:
7 =(n);forn= 7;14;21;28;35;42;56;63;70;84;105;
112;126;140;168;210;252;280;315;336;420;504;560;630;
840;1008;1260;1680;2520;5040:
2.2.2 Calculation the of values function
Generating the file :prn once and reading the generated file in Math-
cad documents that determine solutions of the Diophantine equations lead
to an important saving of the execution time for the program that searches
the solutions.
Program 2.12.The program by means of which the file :prn is generated
is:
ValFS (N) :=1 1
forn22::N
n (n)
return
This program calls the program 2.9 which calculates the values of func-
tion. The generating sequence of the file :prn is:
t0:=time(0)WRITEPRN (":prn ") :=ValFS (106)t1:=time(1)
(t1 t0)sec= "1 : 7 : 32 :625"hhmmss
The execution time of generating the values of function up to 106exceeds
one hour on a computer with an Intel processor of 2.20GHz with RAM of
4.00GB (3.46GB usable).
2.2. PROGRAMS FOR KEMPNER’S ALGORITHM 55
Figure 2.2: The graph of function on the set f1;2;:::; 101g
We give the list of the first 400 and the last 256 values of function:
1, 2, 3, 4, 5, 3, 7, 4, 6, 5, 11, 4, 13, 7, 5, 6, 17, 6, 19, 5, 7, 11, 23, 4, 10, 13, 9, 7, 29,
5, 31, 8, 11, 17, 7, 6, 37, 19, 13, 5, 41, 7, 43, 11, 6, 23, 47, 6, 14, 10, 17, 13, 53, 9,
11, 7, 19, 29, 59, 5, 61, 31, 7, 8, 13, 11, 67, 17, 23, 7, 71, 6, 73, 37, 10, 19, 11, 13,
79, 6, 9, 41, 83, 7, 17, 43, 29, 11, 89, 6, 13, 23, 31, 47, 19, 8, 97, 14, 11, 10, 101,
17, 103, 13, 7, 53, 107, 9, 109, 11, 37, 7, 113, 19, 23, 29, 13, 59, 17, 5, 22, 61, 41,
31, 15, 7, 127, 8, 43, 13, 131, 11, 19, 67, 9, 17, 137, 23, 139, 7, 47, 71, 13, 6, 29,
73, 14, 37, 149, 10, 151, 19, 17, 11, 31, 13, 157, 79, 53, 8, 23, 9, 163, 41, 11, 83,
167, 7, 26, 17, 19, 43, 173, 29, 10, 11, 59, 89, 179, 6, 181, 13, 61, 23, 37, 31, 17,
47, 9, 19, 191, 8, 193, 97, 13, 14, 197, 11, 199, 10, 67, 101, 29, 17, 41, 103, 23,
13, 19, 7, 211, 53, 71, 107, 43, 9, 31, 109, 73, 11, 17, 37, 223, 8, 10, 113, 227, 19,
229, 23, 11, 29, 233, 13, 47, 59, 79, 17, 239, 6, 241, 22, 12, 61, 14, 41, 19, 31, 83,
15, 251, 7, 23, 127, 17, 10, 257, 43, 37, 13, 29, 131, 263, 11, 53, 19, 89, 67, 269,
9, 271, 17, 13, 137, 11, 23, 277, 139, 31, 7, 281, 47, 283, 71, 19, 13, 41, 8, 34, 29,
97, 73, 293, 14, 59, 37, 11, 149, 23, 10, 43, 151, 101, 19, 61, 17, 307, 11, 103, 31,
311, 13, 313, 157, 7, 79, 317, 53, 29, 8, 107, 23, 19, 9, 13, 163, 109, 41, 47, 11,
56 CHAPTER 2. SMARANDACHE’S FUNCTION
331, 83, 37, 167, 67, 7, 337, 26, 113, 17, 31, 19, 21, 43, 23, 173, 347, 29, 349, 10,
13, 11, 353, 59, 71, 89, 17, 179, 359, 6, 38, 181, 22, 13, 73, 61, 367, 23, 41, 37,
53, 31, 373, 17, 15, 47, 29, 9, 379, 19, 127, 191, 383, 8, 11, 193, 43, 97, 389, 13,
23, 14, 131, 197, 79, 11, 397, 199, 19, 10,
…
607, 389, 1669, 83311, 569, 1193, 83, 7351, 239, 55541, 1451, 193, 14489,
Figure 2.3: The graph of function on the set
1;2;:::; 105
26309, 1531, 127, 2531, 1567, 2267, 2293, 999749, 43, 14081, 9613, 19603,
71411, 3389, 9257, 90887, 499879, 333253, 12497, 7517, 166627, 999763,
10867, 1709, 499883, 5779, 541, 999769, 5881, 2207, 249943, 999773, 829,
197, 199, 9007, 38453, 937, 877, 32251, 71413, 12343, 2659, 4877, 166631,
2557, 249947, 47609, 149, 76907, 131, 23251, 499897, 66653, 5101, 2309, 593,
521, 4999, 10099, 1319, 613, 29, 199961, 499903, 333269, 107, 999809, 46,
2053, 733, 333271, 229, 557, 41659, 10987, 317, 111091, 49991, 571, 2347,
8263, 113, 13331, 137, 7193, 27773, 5987, 7691, 1013, 124979, 1499, 15149,
199967, 5813, 1949, 4201, 3533, 2083, 14923, 3067, 827, 1381, 53, 55547, 2141,
2.2. PROGRAMS FOR KEMPNER’S ALGORITHM 57
124981, 333283, 19997, 443, 11903, 999853, 499927, 1307, 23, 9173, 166643,
142837, 49993, 333287, 17239, 999863, 1543, 643, 71419, 739, 249967, 76913,
33329, 7873, 919, 269, 16127, 421, 859, 1447, 967, 337, 3571, 13697, 4273,
999883, 249971, 349, 499943, 142841, 563, 5347, 99989, 1277, 249973, 14083,
179, 15383, 124987, 333299, 9433, 3257, 101, 1721, 21737, 4219, 31247, 6451,
9803, 999907, 67, 461, 99991, 90901, 683, 52627, 499957, 107, 547, 999917,
18517, 1009, 431, 25639, 151, 449, 809, 47, 1901, 111103, 124991, 677, 33331,
999931, 223, 193, 38459, 881, 31, 8849, 499969, 2237, 173, 1733, 166657,
20407, 1033, 823, 499973, 76919, 3623, 87, 2857, 331, 62497, 999953, 761,
18181, 249989, 2801, 499979, 999959, 641, 999961, 13513, 811, 503, 4651, 139,
32257, 31249, 333323, 277, 6211, 197, 97, 29411, 199, 523, 90907, 821, 999979,
49999, 111109, 6329, 999983, 251, 28571, 38461, 1297, 22727, 52631, 271, 997,
2551, 333331, 21739, 199999, 499, 1321, 254, 37, 25 .
Chapter 3
Divisor functions
3.1 The divisor function
The divisor function of order kis given by the formula:
k(n) =X
djndk: (3.1)
Fork= 0, we have function 0(n)(see figure 3.1) which counts the
number of divisors of n. For example, 12has1,2,3,4,6,12as divisors
and, hence, their number is 6.
Figure 3.1: Function 0(n)
58
3.1. THE DIVISOR FUNCTION 59
Fork= 1 we have function 1(n), (see figure 3.2) the function sum of
the divisors of n. For example, 1(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 .
Function1(n), which gives the sum of the divisors of n, is usually
written without index, i.e. (n).
The function sum of the proper divisors of s, [Madachy, 1979], and is
given by the formula:
s(n) =(n) n: (3.2)
For example, s(12) = 1 + 2 + 3 + 4 + 6 = 16 .
Fork= 2 function2(n)is the sum of the squares of the divisors. Fo
examples,2(12) = 12+ 22+ 32+ 42+ 62+ 122= 210 .
Letnbe a natural number whose decomposition into prime factors is
n=p1
1p2
2pss; (3.3)
wherep1<p2<:::psare prime numbers, and j2Nforj= 1;2;:::;s .
Theorem 3.1. For two positive natural numbers nandm, relative prime,
(n;m) = 1 , then
(nm) =(n)(m): (3.4)
Proof. For each divisor djofnmwe havedj=nj1mj2, wherenj1jnand
mj2jm. The numbers 1,n1,n2, . . . ,nare the divisors of nand1,m1,m2,
. . . ,mare the divisors of m. Then we have
(n) = 1 +n1+n2+:::+n
and
(m) = 1 +m1+m2+:::+m:
According to the previous relations we can write nj1(1 +m1+m2+:::+
m) =nj1(m). If we sum relative to nj1it follows that (1+n1+n2+:::+
n)(m) =(n)(m), i.e. relation (3.4) holds.
We owe to Berndt, [Berndt, 1985, p. 94], [Weisstein, 2014c], next result.
60 CHAPTER 3. DIVISOR FUNCTIONS
Figure 3.2: Function (n)
3.1. THE DIVISOR FUNCTION 61
Theorem 3.2. For every natural number n, whose decomposition into prime fac-
tors is (3.3) , we have that
(n) =sY
j=1pj+1
j 1
pj 1: (3.5)
Proof. According to relations (3.3) and (3.4) it follows that
(n) =(p1
1)(p2
2)(pss):
The divisors of pj
jare1,pj,p2
j, . . . ,pj
j, therefore, the sum of the divisors
ofpj
jis
(pj
j) = 1 +pj+p2
j+:::+pj
j=pj+1
j 1
pj 1:
Hence, according to Proposition 3.1 we can state that
(n) =(p1
1p2
2psr) =sY
j=1pj+1
j 1
pj 1:
By generalizing formula (3.5) it results a relation for function k. Func-
tionk:N!N, [Weisstein, 2014c], is given by the relations:
0(n) =sY
j=1(j+ 1) (3.6)
and
k(n) =sY
j=1p(j+1)k
j 1
pk
j 1: (3.7)
62 CHAPTER 3. DIVISOR FUNCTIONS
3.1.1 Computing the values of kfunctions
Program 3.3.The program for computing the values of function k, for
k= 0;1;:::.
(k;n) :=f Fa(n)
returnrows (f)Y
j=1(fj;2+ 1)if k=0
returnrows (f)Y
j=1(fj;1)(fj;2+1)k 1
(fj;1)k 1if k> 0
The program 3.3 calls the program 1.29 of factorization in product of prime
factors.
Program 3.4.The program by means of which the files k:prn are gener-
ated is:
G(k;N) :=f'1 1
forn22::N
fn (k;n)
returnf
Obviously this program calls the program 3.3 for computing the values of
functionk. The sequence for generating the file 0:prn is:
t0:=time(0)WRITEPRN ("0:prn") :=G(0;106)t1:=time(1)
(t1 t0)sec= "0 : 0 : 2:833"hhmmss
The sequences for generating the files 1:prn and2:prn are similar.
3.2.K–HYPERPERFECT NUMBERS 63
3.2k–hyperperfect numbers
A numbern2Nis calledk–hyperperfect if following identity
n= 1 +kX
jdj
holds, or
n= 1 +k((n) n 1); n = 1 +k(s(n) 1);
where(n) =1(n)is the function that represents sum of the divisors dj
ofnands(n)the sum of the proper divisors of n, where 1<dj<n. After
rearranging, we obtain relation
k(n) = (k+ 1)n+k 1
which, if it is verified, means that nisk–hyperperfect number. If k= 1 we
say thatnis aperfect number.
The conjecture of McCranie [2000] states: the number n=p2qis ak–
hyperperfect number if k22N+ 1,p=3k+1
2,q= 3k+ 4,pandqprime
numbers .
Ifpandqare distinct odd prime numbers such that k(p+q) =pq 1
for ak2N, thenn=pqisk–hyperperfect .
Ifk2Nandp=k+ 1is prime, then, if there exists a j2Nsuch that
q=pj p+ 1prime, then n=pj 1qisk–hyperperfect .
The firstk-hyperperfect numbers are: 6, 21, 28, 301, 325, 496, 697, 1333,
. . . [Sloane, 2014, A034897], which correspond to the values of k: 1, 2, 1, 6,
3, 1, 12, 18, . . . . McCranie [2000] gave the list of all hyperperfect numbers
up to 1011.
Chapter 4
Euler’s totient function '
Euler’s totient function, denoted ', counts the number of factors rel-
ative prime to n, where 1is considered relative prime to every natural
number. For example, factors relative prime to 36are1,5,7,11,13,17,19,
23,25,29,31,35and, therefore, it results that '(36) = 12 . By convention,
we have'(0) = 1 .
Program 4.1.The program for computing the values of Euler’s totient func-
tion which applies the definition of the function is
'(n) :=return 1if n=0
j 0
fork21::n
j j+ 1ifgcd(k;n)=1
returnj
This program can not be used for computing the values of Euler’s totient
function for great numbers.
Functionn '(n)is called cototient function.
64
4.1. THE PROPERTIES OF FUNCTION ' 65
Figure 4.1: Euler’s totient function
4.1 The properties of function '
Forpprime number we have '(p) =p 1, and
'(p) =p 1(p 1) =p
1 1
p
:
Letmbe a prime multiple of p. We define function 'p(m)which counts
the positive integers mwhich are not divisible by p. Asp,2p, . . . ,m
pp
have common factor p, it follows that
'p(m) =m m
p=m
1 1
p
: (4.1)
Letqbe another prime number that divides m, or letmbe a multiple of
q. Thenq,2q, . . . ,m
qqhaveqcommon factor, but there exist also duplicate
common factors pq,2pq, . . . ,m
pqpq. Therefore, the number of terms that
66 CHAPTER 4. EULER’S TOTIENT FUNCTION '
have to be subtracted from 'p(m)to obtain'pq(m)is
m
q m
pq=m
q
1 1
p
: (4.2)
Then, from (4.1) and (4.2) it results that
'pq(m) =m
1 1
p
m
q
1 1
p
=m
1 1
p
1 1
q
: (4.3)
Similarly, by mathematical induction it can be proved that if nis divisible
byp1,p2, . . . ,ps, prime numbers (or nis a multiple of p1,p2, . . . ,ps, prime
numbers), then we have
'(n) =nsY
k=1
1 1
pk
: (4.4)
We have an interesting identity, due to Olofsson [2004], regarding '(n`)
and'(n), given by relation
'(n`) =n` 1'(n): (4.5)
Euler’s totient function satisfies the inequality '(n)>pnfor alln2N
excepting 2and6, [Kendall and Osborn, 1965], [Mitrinovi ´c and S ´andor,
1995, p. 9]. Consequently, '(n) = 2 only forn= 3,n= 4andn= 6. Also,
in the monograph [Sierpi ´nski, 1988], was proved that '(n)n pn.
The solutions of the '–Diophantine equation '(n) ='(n+ 1) are:1,3,
15,104,164,194,255,495,584,975, . . . [Sloane, 2014, A003275].
In the search domain Dc=
1;2;:::; 1010
there exists only one solu-
tionn= 5186 = 2534for which the double identity '(n) ='(n+ 1) =
'(n+ 2) holds, [Guy, 2004, p. 139].
The smallest three close numbers (the difference between them is 6),
for which the double equality '(n1) ='(n2) ='(n3)holds, are: 404471 ,
404473 and404477 . These numbers verify the equalities:
'(404471) = '(404473) = '(404477) = 403200 :
4.1. THE PROPERTIES OF FUNCTION ' 67
The smallest four close numbers (the difference between them is 12),
for which the triple equality '(n1) ='(n2) ='(n3) ='(n4)hold, are:
25930 ,25935 ,24940 and25942 . They verify the equalities:
'(25930) ='(25935) ='(25940) ='(25942) = 10368 :
These results were published in [Guy, 2004, p. 139].
McCranie [2000] found the arithmetic progression ak=a0+kr, where
the first term is a0= 583200 andr= 30 is the ratio, for which we have
'(ak) = 155520 for allk= 0;1;:::; 5:
Other arithmetic progressions with six consecutive terms, with a0=
1166400 andr= 583200 , which have the same property, are also known
[Sloane, 2014, A050518].
An interesting conjecture due to Guy [2004] has following predication.
If Goldach’s conjecture holds, then, for every m2N, there exist the prime num-
berspandqsuch that'(p) +'(q) = 2m. Erd ¨os wondered if this statement
also holds for pandqnot necessarily primes, but this ”relaxed” conjecture
remains unproved.
Guy [2004] considered the '––Diophantine equation '((n)) =n. F.
Helenius found 365 solutions, of which the first are: 2,8,12,128,240,720,
6912 ,32768 ,142560 ,712800 , . . . , [Sloane, 2014, A001229].
4.1.1 Computing the values of 'function
Program 4.2.Considering formula (4.5), an efficient program for comput-
ing the values of function 'can be written.
'(n) :=return 1if n=0_n=1
f Fa(n)
n
fork21::rows (f)
fk;1 1
fk;1
return
68 CHAPTER 4. EULER’S TOTIENT FUNCTION '
This program calls the program 1.29 for factorization of a number.
Program 4.3.The program by means of which the file ':prn is generated
is:
G'(N) :=f'1 1
forn22::N
f'n '(n)
returnf'
This program calls the program 4.2 for computing the values of Euler’s
totient function. The sequence for generating the file ':prn is:
t0:=time(0)WRITEPRN ("':prn ") :=G'(106)t1:=time(1)
(t1 t0)sec= "5 : 30 : 33 :558"hhmmss
The execution time for generating the values of function 'up to 106is of
5hours and 30minutes on a computer with an Intel processor of 2.20GHz
with RAM of 4.00GB (3.46GB usable).
4.2 A generalization of Euler’s theorem
In the sections which follow we will prove a result which replaces the
theorem of Euler: ”If (a;m) = 1 , thena'(m)1 (modm )”, for the case
whenaandmare not relatively primes.
One supposes that m > 0. This assumption will not affect the gener-
alization, because Euler’s indicator satisfies the equality: '(m) ='( m),
[Popovici, 1973], and that the congruencies verify the following property:
ab(modm ),ab(mod m), [Popovici, 1973, pp. 12–13].
In the case of congruence modulo 0, there is the relation of equality.
One denotes
a;b
=gcf(a;b)greatest common factor of the two integers a
andb, and one chooses
a;b
>0. Notegcfis the same as gcdfor numbers,
so
a;b
=gcf(a;b) = gcd(a;b).
4.2. A GENERALIZATION OF EULER’S THEOREM 69
Lemma 4.4. Let beaan integer and ma natural number >0. The existd0;m02
Nsuch thata=a0d0,m=m0d0and
a0;m0
= 1.
Proof. It is sufficient to choose d0=
a;m
. In accordance with the defi-
nition of the gcf(greatest common factor), the quotients of a0andm0of
aandmby theirgcfare relatively primes, [Creang ˘a et al., 1965, pp. 25–
26].
Lemma 4.5. With the notations of lemma 4.4, if d06= 1 and if:d0=d1
0d1,
m0=m1d1,
d1
0;m1
= 1 andd16= 1, thend0> d 1andm0> m 1, and if
d0=d1, then after a limited number of steps ione hasd0>di+1=
di;mi
.
Proof.
(0)a=a0d0;
a0;m0
= 1
m=m0d0;d06= 1;
(1)d0=d1
0d1;
d1
0;m1
= 1
m0=m1d1;d16= 1:
From (0)and from (1)it results that a=a0d0=a0d1
0d1therefored0=d1
0d1
thusd>d 1ifd1
06= 1.
Fromm0=m1d1we deduct that m0> m 1. Ifd0=d1thenm0=
m1d0=kdz
0, wherez2Nandd0-k. Therefore m1=kdk 1
0;d2=
d1;m1
=
d0;kdz 1
0
. Afteri=zsteps, it results di+1=
d0;k
<d0.
Lemma 4.6. For each integer aand for each natural number m > 0one can
build the following sequence of relations:
(0)a=a0d0;
a0;m0
= 1
m=m0d0;d06= 1;
(1)d0=d1
0d1;
d1
0;m1
= 1
m0=m1d1;d16= 1;
:::::::::
(s 1)ds 2=d1
s 2ds 1;
d1
s 2;ms 1
= 1
ms 2=ms 1ds 1;ds 16= 1;
70 CHAPTER 4. EULER’S TOTIENT FUNCTION '
(s)ds 1=d1
s 1ds;
d1
s 1;ms
= 1
ms 1=msds;ds6= 1:
Proof. One can build this sequence by applying lemma 4.4. The sequence
is limited, according to lemma 4.5, because after r1steps, one has d0>dr1,
andm0>mr1, and afterr2steps, one has dr1>dr1+r2andmr1>mr1+r2,
etc., and the miare natural numbers. One arrives at ds= 1 because if
ds6= 1 one will construct again a limited number of relations (s+ 1) , . . . ,
(s+r)withds+r<ds.
Theorem 4.7. Let us havea;m2Z, andm6= 0. Then
a'(ms)+sas(modm );
wheresandms, are the same ones as in the lemmas above.
Proof. Similar with the method followed previously, one can suppose m>
0without reducing the generality. From the sequence of relations from
lemma 4.6, it results that:
(0) (1) (2) (3) ( s)
a=a0d0=a0d1
0d1=a0d1
0d1
1d2:::=a0d1
0d1
1d1
s 1ds
and
(0) (1) (2) (3) ( s)
m=m0d0=m1d1d0=m2d2d1d0:::=msdsds 1d1
1d0
and
msdsds 1d1d0=d0d1ds 1dsms:
From (0)it results that d0=
a;m
, and from (i)thatdi=
di 1;mi 1
, for
alli2f1;2;:::;sg.
d0=d1
0d1
1d1
2d1
s 1ds;
d1=d1
1d1
2d1
3d1
s 1ds;
…
ds 1=d1
s 1ds;
ds=ds:
4.2. A GENERALIZATION OF EULER’S THEOREM 71
Therefore
d0d1d2ds 1ds= (d1
0)1(d1
1)2(d1
2)3(d1
s 1)s(d1
s)s+1
= (d1
0)1(d1
1)2(d1
2)3(d1
s 1)s;
becauseds= 1.
Thusm= (d1
0)1(d1
1)2(d1
2)3(d1
s 1)sms; thereforemsjm.
(s)
ds;ms
=
1;ms
and
d1
s 1;ms
= 1
(s 1)
1 =
d1
s 2;ms 1
=
d1
s 2;msds
therefore
d1
s 2;ms
= 1,
(s 2)
1 =
d1
s 3;ms 2
=
d1
s 3;ms 1ds 1
=
d1
s 3;msdsds 1
therefore
ds 3;ms
= 1,
…
1(i+ 1)
=
d1
i;mi+1
=
d1
i;mi+2di+2
=
d1
i;mi+3di+3di+2
=:::
=
d1
i;msdsds 1di+2
;
thus
d1
i;ms
= 1, and this is for all i2f1;2;:::;s 2g,
…
(0)
1 =
a0;m0
=
a0;d1ds 1dsms ;
72 CHAPTER 4. EULER’S TOTIENT FUNCTION '
thus
a0;ms
= 1.
From the Euler’s theorem results that: (d1
i)'(ms)1 (modms)for all
i2f0;1;:::;sg,a'(ms)
01 (modms), but
a'(ms)
0 =a'(ms)
0 (d1
0)'(ms)(d1
1)'(ms)(d1
s 1)'(ms);
thereforea'(ms)11|{z}
(s+1)times(modms), thena'(ms)1 (modms). We
equivalence
a0(d1
0)s 1(d1
1)s 2(d1
2)s 3(d1
s 2)1a'(ms)
as
0(d1
0)s 1(d1
1)s 2(d1
s 2)11 (modms):
If you multiply the (d1
0)1(d1
1)2(d1
2)3(d1
s 2)s 1(d1
s 1)swe obtain:
as
0(d1
0)s(d1
1)s(d1
s 2)s(d1
s 1)sa'(ms)
as
0(d1
0)s(d1
1)s(d1
s 2)s(d1
s 1)s
mod (d1
0)1(d1
s 1)sms
;
butas
0(d1
0)s(d1
1)s(d1
s 1)sa'(ms)andas
0(d1
0)s(d1
1)s(d1
s 1)s=asthere-
forea'(ms)+sas(modm ), for alla;m2Z,m6= 0.
Observation 4.8.If
a;m
= 1 thend= 1. Thuss= 0, and according the
theorem 4.7 one has a'(m0)+0a0(modm )thereforea'(m0)1 (modm ).
Butm=m0d0=m01 =m0. Thusa'(m)1 (modm ), and one obtains
Euler’s theorem.
Observation 4.9.Let us have aandmtwo integers, m6= 0 and
a;m
=
d06= 1, andm=m0d0. If
d0;m0
= 1, thena'(m0)+1a(modm ).
Which, in fact, it results from the theorem 4.7 with s= 1 andm1=m0.
This relation has a similar to Fermat’s theorem: a'(p)+1a(modp ).
4.2.1 An algorithm to solve congruences
One will construct an algorithm to calculate sandmsof the theorem
4.7.
4.2. A GENERALIZATION OF EULER’S THEOREM 73
Program 4.10.The program is:
S(a;m) :=s 0
ms m
d gcd(a;ms)
whiled6= 1
s s+ 1
ms ms
d
d gcd(d;ms)
returns
ms
The program calls the function Mathcad gcdcomputation of the greatest
common divisor.
4.2.2 Applications
In the resolution of the exercises one uses the theorem 4.7 and the al-
gorithm to calculate sandms.
Example 1 :6'(ms)6s(mod 105765) . One thus applies the algorithm
to calculate sandmsand then the theorem 4.7:
a:= 6m:= 105765
s
ms
:=S(a;m) =1
35255
:='(ms) +s= 25601
mod(a;m) = 6mod(as;m) = 6;
where we used the programs 4.10 and 4.2.
Example 2 :847'(ms)as(mod 283618125) . One thus applies the algo-
rithm to calculate sandmsand then the theorem 4.7:
a:= 847m:= 283618125
74 CHAPTER 4. EULER’S TOTIENT FUNCTION '
s
ms
:=S(a;m) =5
16875
:='(ms) +s= 9005
mod(a;m)!759601mod(as;m)!759601;
where we used the programs 4.10 and 4.2.
Example 2 :847'(ms)as(mod 283618125) . One thus applies the algo-
rithm to calculate sandmsand then the theorem 4.7:
a:= 847m:= 283618125s
ms
:=S(a;m) =5
16875
:='(ms) +s= 9005
mod(a;m)!759601mod(as;m)!759601;
where we used the programs 4.10 and 4.2.
Example 3 :437'(ms)as(mod 2058557375) . One thus applies the algo-
rithm to calculate sandmsand then the theorem 4.7:
a:= 437m:= 2058557375s
ms
:=S(a;m) =3
300125
:='(ms) +s= 205803
mod(a;m)!193233mod(as;m)!193233;
where we used the programs 4.10 and 4.2.
Example 4 :4433'(ms)as(mod 789310951) . One thus applies the algo-
rithm to calculate sandmsand then the theorem 4.7:
a:= 4433m:= 789310951s
ms
:=S(a;m) =5
29
:='(ms) +s= 33
mod(a;m)!23115132mod(as;m)!23115132;
where we have used the programs 4.10 and 4.2.
Chapter 5
Generalization of congruence
theorems
5.1 Notions introductory
Let us consider a positive integer, which we will call modulus . With
its help we introduce in the set Zof integers a binary relation, called of
congruence and denoted, such that:
Definition 5.1. The integers aand bare congruent relative to modulus m
is and only if mdivides the difference a b.
Hence, we have
ab(modm ),a b=km;wherek2Z: (5.1)
Consequence 5.2. ab(modm ),aandbgive, by division trough m,
the same residue.
It is known that the congruence relation given by (5.1) is an equiva-
lence relation (is reflexive, symmetric and transitive). It also has following
remarkable properties:
a1b1(modm )anda2b2(modm )),
75
76CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
(i)a1+a2b1+b2(modm ),
(ii)a1 a2b1 b2(modm ),
(iii)a1a2b1b2(modm ).
More generally, if aibi(modm ), fori= 1;2;:::;n , andf(x1;x2;:::;xn)
is a polynomial with integer coefficients, then
(iv)f(a1;a2;:::;an)f(b1;b2;:::;bn) (modm ).
One can also prove following properties of the congruence relations:
(v)ab(modm )andc2N)acbc(modm ),
(vi)ab(modm )andn2N,ndividem)ab(modn ),
(vii)ab(modmi),i=1;s,)ab(modm ),
wherem= [m1;m2;:::;ms] =lcm(m1;m2;:::;ms)is the smallest com-
mon multiple of numbers mi.
(viii)ab(modm ))(a;m) = (b;m),
where by (x;y) =gcd(x;y)we denote the greatest common divisor of
numbersxandy.
As the relation congruence mod m is an equivalence relation, it divides
the set Zof integers into equivalence classes (classes of congruence mod m ).
Two such classes either are disjoint or coincide.
As every integer provides by division through mone of the residues 0,
1,2, . . . ,m 1, it follows that
C0; C1; :::; Cm 1
are themclasses of residues mod m , whereCiis the set of all integers
congruent with i(modm ).
Sometimes it is useful to consider, instead of the classes, representa-
tives that satisfy certain conditions. Hereby, following terminology is es-
tablished.
5.1. NOTIONS INTRODUCTORY 77
Definition 5.3. The integers a1,a2, . . . ,amcompose a complete system of
mod m residues if any two of them are not congruent mod m .
It results that a complete system of mod m residues contains a represen-
tative of each class.
If'is Euler’s totient function ( '(n), denoted also 'n, is the number of
natural numbers smaller than nand prime to n), then we also have:
Definition 5.4. The integers a1,a2, . . . ,a'(m)build a reduced system of mod
m residues if each is prime with the modulus and if any two of them are
not congruent mod m .
Following result is known:
Theorem 5.5.
1. Ifa1,a2, . . . ,amis a complete system of mod m residues and a is an integer,
prime to m, then the sequence aa1; aa2; :::;aamis also a complete
system of mod m residues.
2. Ifa1,a2, . . . ,a'(m)is a reduced system of mod m residues and a is an
integer, prime to m, then the sequence aa1; aa2; :::;aa'(m)is also a
reduced system of mod m residues.
If we denote by Zmthe set of the classes of residues mod m:
Zm=fC0;C1;:::;Cm 1g
and we define the relations
+ :ZmZm!Zm;:ZmZm!Zm;
by
Ci+Cj=Ck;whereki+j(modm );
CiCj=Ch;wherehij(modm );
then following result holds:
78CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
Theorem 5.6.
1.(Zm;+)is a commutative group,
2.(Zm;+;)is a commutative ring,
3.(Gm;)is a commutative group,
whereGm=n
Cr1;Cr2;:::;Cr'(m)o
the set of the classes of residues prime to
the modulus.
Consequence 5.7. The setZpof the classes of residues relative to a prime
moduluspbuilds a commutative field relative to the previously defined
operations of addition and multiplication.
5.2 Theorems of congruence of the Number Theory
In this section we will recall some congruence theorems of the Num-
ber Theory (Theorems of Fermat, Euler, Wilson, Gauss, Lagrange, Leib-
niz, Moser and Sierpinski) which we will generalize in the next section.
Equally, we will emphasize a unifying point of view.
In 1640 Fermat states, without proof, the next result:
Theorem 5.8 (Fermat) .If integerais not divisible by the prime number p, then
ap 11 (modp ): (5.2)
The first proof of this theorem was given in 1736 by Euler.
As it is known, the reciprocal of Fermat’s Theorem is not true. In an-
other words, the fact that am 11 (modm )andmis not divisible by a,
does not necessarily imply that mis a prime number.
It is not even true that, if (5.2) holds for all numbers aprime relative to
m, thenmis prime, as one can remark in the following example.
Example 5.9. Letm= 561 = 31117. Ifais an integer that is not divisible
by3, by11or by 17, we surely have:
a21 (mod 3); a101 (mod 11); a161 (mod 17);
5.2. THEOREMS OF CONGRUENCE OF THE NUMBER THEORY 79
according to the direct Theorem of Fermat. But, as 560is divisible by 2and
10, as well as by 16, we deduce that:
a5601 (modmi); i= 1;2;3;
wherem1= 3,m2= 11 andm3= 17 .
According to property (vii) of the previous section, it follows that
a5601 (modm );form= 561:
Actually, it is known that 561is the smallest composite number that satis-
fies (5.2). Next numbers follow: 1105 ,1729 ,2465 ,2821 , . . . .
Consequently, the congruence (5.2) can be true for a certain integer a
and a composite number m.
Definition 5.10. If relation (5.2) is satisfied for a composite number mand
an integera, it is said that mispseudoprime relative to a . Ifmis pseudoprime
relative to every integer a, prime to m, it is said that mis a Carmichael
number .
The American mathematician Robert Carmichael was the first who, in
1910 has emphasized such numbers, called fake prime numbers .
Until recently, it was not known if there exists or not an infinity of
Carmichael numbers. In the very first issue of the journal ”What0s Hap-
pening in the Mathematical Sciences”, where, yearly, the most important
recent results in mathematics are emphasized, it is that three mathemati-
cians: Alford, Granville and Pomerance, have proved that there exists an
infinity of Carmichael numbers.
The proof of the trio of American mathematicians is based on an
heuristic remark from 1956 of the internationally known Hungarian math-
ematician P . Erd ¨os. The main idea is to chose a number Lfor which there
exist a lot of prime numbers pthat do not divide L, but having the prop-
erty thatp 1dividesL. Afterwards it is shown that these prime numbers
can be multiplied among themselves in several ways such that each prod-
uct is congruent with 1 (modL ). It results that every such product is a
Carmichael number.
80CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
For example, for L= 120 , the prime numbers that satisfy the previous
condition are: p1= 7,p2= 11 ,p3= 13 ,p4= 31 ,p5= 41 ,p6= 61 . It follows
that41041 = 7111341,172081 = 7133161and852841 = 11314161are
congruent with 1 (mod 120) , and, hence, they are Carmichael numbers.
We mention that the heuristic remark of P . Erd ¨os is based on the follow-
ing theorem that characterizes the Carmichael numbers, proved in 1899.
Theorem 5.11 (A. Korselt) .The number nis a Carmichael number if and only
if following conditions hold:
(C1)nis squares free,
(C2)p 1dividesn 1as long aspis a prime divisor of n.
The three American mathematicians have proved the following result:
Theorem 5.12 (Alford, Granville, Pomerance) .There exist at least x2=7
Carmichael numbers, not greater than x, forxsufficiently big.
By means of the heuristic argument due to P . Erd ¨os it can be proved
that the exponent of Theorem 5.12 can be replaced by any other sub uni-
tary exponent.
Theorem 5.13 (Euler) .If(a;m) = 1 , thena'(m)1 (modm ).
The notation (a;m) = 1 means that the greatest common divisor of a
andmis1, which means that the numbers are relatively prime.
Theorem 5.13 generalizes Theorem 5.8 and was proved by Euler in
1760.
Theorem 5.14 (Wilson) .Ifpis a prime number, then (p 1)!+10 (modp ).
It is known that the reciprocal of Theorem 5.14 is true, which means
that following result holds
Theorem 5.15. Ifn>1is an integer and (n 1)! + 10 (modn )thennis
prime.
5.3. A UNIFYING POINT OF CONVERGENCE THEOREMS 81
Theorem 5.14, of Wilson, was published in 1770 by mathematician
Waring ( Meditationes Algebraicae ), but it was known long before, by Leib-
niz.
Lagrange generalizes Theorem 5.14, of Wilson, as follows:
Theorem 5.16 (Lagrange) .Ifpis a prime number, then ap 1 1(a+1)(a+
2):::(a+p 1) (modp ).
Leibniz states following theorem:
Theorem 5.17 (Leibniz) .Ifpis a prime number, then (p 2)!1 (modp ).
The reciprocal of Theorem 5.17, of Leibniz, is also true, i.e. a natural
numbern>1is prime if and only if (n 2)!1 (modp ).
Another result concerning congruences with prime numbers is the next
theorem:
Theorem 5.18 (L. Moser) .Ifpis a prime number, then (p 1)!ap+a
0 (modp ).
Sierpinski proves that following result holds:
Theorem 5.19 (Sierpinski) .Ifpis a prime number, then ap+ (p 1)!
0 (modp ).
We remark that this statement unify the Theorems 5.8 of Fermat and
5.14 of Wilson.
In the next section we will define a function L:ZZ!Z, by means
of which we will be able to prove several results that unify all previous
theorems.
5.3 A unifying point of convergence theorems
LetAbe the set
m2Z=m=p;2p
withpan odd prime, 2N,
orm=2, with= 0;1;2, orm= 0.
Letm="p1
1p2
2prr, with"=1, alli2Nandp1,p2, . . . ,prare
distinct positive primes.
82CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
We construct the function L:ZZ,
L(x;m) = (x+C1)(x+C2)(x+C'(m)); (5.3)
whereC1,C2, . . .C'(m)are all modulo mrests relatively prime to m, and
'is Euler’s function.
If all distinct primes which divide xandmsimultaneously are pi1,pi2,
. . .pir, then:
L(x;m)1
modpi1
i1pi2
i2pir
ir
whenm2A (5.4)
respectively m =2A, and
L(x;m)0
modm=
pi1
i1pi2
i2pir
ir
: (5.5)
Ford=pi1
i1pi2
i2pir
ir, andm0=m=d we find
L(x;m)1 +k0
1dk0
2m0(modm ); (5.6)
wherek0
1andk0
2constitute a particular integer solution of the Diophantine
equationk2m0 k1d=1(the signs are chosen in accordance with the
affiliation of mtoA).
This result generalizes Gauss’ theorem, (C1C2C'(m)1 (modm )
whenm2Arespectively m =2A), see [Dirichlet, 1894], which generalized
in its turn the Wilson’s theorem (if pis prime then (p 1)! 1 (modm )).
Lemma 5.20. IfC1,C2, . . . ,C'(p)are all modulo prests, relatively prime to
p, withpan integer and 2N, then fork2Zand2Nwe have also that
kp+C1,kp+C2, . . . ,kp+C'(p)constitute all modulo prests relatively
prime top.
Proof. It is sufficient to prove that for 1i'(p)we havekp+Ci
relatively prime to p, but this is obvious.
Lemma 5.21. IfC1,C2, . . . ,C'(m)are all modulo mrests relatively prime to m,
pi
idividesmandpi+1
i does not divide m, thenC1,C2, . . . ,C'(m)constitute
'(m=pi
i)systems of all modulo pi
irests relatively prime to pi
i.
5.3. A UNIFYING POINT OF CONVERGENCE THEOREMS 83
Proof. Proof is obvious.
Lemma 5.22. IfC1,C2, . . . ,C'(m)are all modulo qrests relatively prime to b
and(b;q) = 1 thenb+C1,b+C2, . . . ,b+C'(q)contain a representative of the
classb0moduloq.
Proof. Of course, because (b;q b) = 1 there will be a Ci0=q b, whence
b+Ci0=Mq(multiple of q).
From this we have:
Theorem 5.23. If
x;m= (pi1
1pi2
2pir
ir)
= 1then
L(x;m) = (x+C1)(x+C2)(x+C'(m))
0
modm=
pi1
1pi2
2pir
ir
:
Proof. Proof is obvious.
Lemma 5.24. BecauseC1C2C'(m)1 (modm )it results that
C1C2C'(m)1 (modpi
i);
for alli, whenm2A, respectively m =2A.
Proof. Proof is obvious.
Lemma 5.25. Ifpidividesxandmsimultaneously, then
(x+C1)(x+C2)(x+C'(m))1 (modpi
i);
whenm2Arespectively m =2A.
Proof. Of course, from the lemmas 5.21 and 5.20, respectively 5.24, we have
(x+C1)(x+C2)(x+C'(m))C1C2C'(m)1 (modpi
i):
84CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
From the lemma 5.25 we obtain:
Theorem 5.26. Ifpi1,pi2, . . . ,pirare all primes which divide xandmsimulta-
neously then
(x+C1)(x+C2)(x+C'(m))1
modpi1
1pi2
2pir
i
;
whenm2Arespectively m =2A.
From the theorems 5.23 and 5.26 it results L(x;m) =1 +k1d=
k2m0, wherek1;k22Z. Because (d;m0) = 1 the Diophantine equation
k2m0 k1d=1admits integer solutions (the unknowns being k1and
k2). Hencek1=m0t+k0
1andk2=dt+k0
2, witht2Z, andk0
1;k0
2
constitute a particular integer solution of our equation. Thus
L(x;m)1 +m0dt+k0
1d1 +k0
1(modm )
or
L(x;m)k0
2m0(modm ):
5.4 Applications
1. The theorem Lagrange was extended of Wilson as follows: ”if pis
prime, then xp 1 1(x+ 1)(x+ 2)(x+p 1) (modp )”; we
shall extend this result in the following way: For any m6= 0;4we
have forx2+s26= 0that
x'(ms)+s xs(x+ 1)(x+ 2)(x+jmj 1) (modm );
wheremsandsare obtained from the algorithm:
Algorthm 5.27.
(0)x=x0d0; (x0;m0) = 1
m=m0d0;d06= 1;
5.4. APPLICATIONS 85
(1)d0=d1
0d1; (d1
0;m1) = 1
m0=m1d1;d16= 1;
:::::::::
(s 1)ds 2=d1
s 2ds 1; (d1
s 2;ms 1) = 1
ms 2=ms 1ds 1;ds 16= 1;
(s)ds 1=d1
s 1ds; (d1
s 1;ms) = 1
ms 1=msds;ds6= 1;
[Smarandache, 1981a, 1984].
Formpositive prime we have ms=m,s= 0and'(m) =m 1, that
is Lagrange’s theorem.
2. L. Moser enunciated the following theorem: ” ifpis prime, then (p
1)!ap+a=Mp”, and Sierpinski [1966]: ” ifpis prime then ap+ (p
1)!a=Mpwhich merges Wilson’s and Fermat’s theorems in a single
one.
The function Land the algorithm 5.27 will help us to generalize them
too, so: ifaandmare integers, m6= 0, andC1,C2, . . . ,C'(m)are all
modulo rests relatively prime to mthen
C1C2C'(m)a'(ms)+s L(0;m)as=Mm;
respectively
L(0;m)a'(ms)+s+C1C2C'(m)as=Mm;
or more,
(x+C1)(x+C2)(x+C'(m))a'(ms)+s L(x;m)as=Mm
respectively
L(x;m)a'(ms)+s+ (x+C1)(x+C2)(x+C'(m)as=Mm;
which reunites Fermat, Euler, Wilson, Lagrange and Moser (respec-
tively Sierpinski).
86CHAPTER 5. GENERALIZATION OF CONGRUENCE THEOREMS
3. The author also obtained a partial extension of Moser’s and Sier-
pinski’s results, [Smarandache, 1983], so: if mis positive integer,
m6= 0;4, andais an integer, then (am a)(m 1)! =Mm, reuniting
Fermat’s and Wilson’s theorem in another way.
4. Leibniz enunciated that: ” ifpis prime then (p 2)!1 (modp )”;
we consider ” Ci< Ci+1(modm )” ifCi< Ci+1where 0Ci<
jmj,0Ci+1<jmjandCiCi(modm ),Ci+1Ci+1(modm );
one simply gives that if C1,C2, . . . ,C'(m)are all modulo mrests
relatively prime to m(Ci< Ci+1(modm )for alli,m6= 0) then
C1C2C'(m) 1 1 (modm )ifm2Arespectively m =2A,
becauseC'(m) 1 (modm ).
Chapter 6
Analytical solving of
Diophantine equations
6.1 General Diophantine equations
A Diophantine equation is an equation in which only integer solutions
are allowed.
Hilbert’s 10th problem asked if an algorithm existed for determining
whether an arbitrary Diophantine equation has a solution. Such an al-
gorithm does exist for the solution of first-order Diophantine equations.
However, the impossibility of obtaining a general solution was proven by
Matiyasevich [1970], Davis [1973], Davis and Hersh [1973], Davis [1982],
Matiyasevich [1993] by showing that the relation n=F2m(whereF2is the
2m-th Fibonacci number) is Diophantine. More specifically, Matiyasevich
showed that there is a polynomial Pinn,m, and a number of other vari-
ablesx,y,z, . . . having the property that n=F2mif there exist integers x,
y,z, . . . such that P(n;m;x;y;z;::: ) = 0 .
Matiyasevich’s result filled a crucial gap in previous work by Martin
Davis, Hilary Putnam, and Julia Robinson. Subsequent work by Matiya-
sevich and Robinson proved that even for equations in thirteen variables,
no algorithm can exist to determine whether there is a solution. Matiya-
87
88 CHAPTER 6. ANALYTICAL SOLVING
sevich then improved this result to equations in only nine variables Jones
and Matiyasevich [1981].
Ogilvy and Anderson [1988] give a number of Diophantine equations
with known and unknown solutions.
A linear Diophantine equation (in two variables) is an equation of the
general form
mx+ny=`;
where solutions are sought with m,n, and`integers. Such equations can
be solved completely, and the first known solution was constructed by
Brahmagupta, [Weisstein, 2014b]. Consider the equation
mx+ny= 1:
Now use a variation of the Euclidean algorithm, letting m=r1andn=r2
r1=q1r2+r3;
r2=q2r3+r4;
……
rn 3=qn 3rn 2+rn 1;
rn 2=qn 2rn 1+ 1:
Starting from the bottom gives
1 =rn 2 qn 2rn 1
rn 1=rn 3 qn 3rn 2;
rn 2=rn 4 qn 4rn 3;
……
n=r2=r4 q4r3;
m=r1=r3 q3r2
6.2. GENERAL LINEAR DIOPHANTINE EQUATION 89
so
1 =rn 2 qn 2rn 1
=rn 2 qn 2(rn 3 qn 3rn 2)
= qn 2rn 3+ (1 +qn 2qn 3)rn 2
= qn 2rn 3+ (1 +qn 2qn 3)(rn 4 qn 4rn 3)
= (1 +qn 2qn 3)rn 4 (qn 2+qn 4+qn 2qn 3qn 4)rn 3
=::: :
Continue this procedure all the way back to the top.
6.2 General linear Diophantine equation
The utility of this section is that it establishes if the number of natural
solutions of a general linear equation is limited or not. We will show also a
method of solving, using integer numbers, the equation ax by=c(which
represents a generalization of lemmas 1and2of [Andrica and Andreescu,
1981]), an example of solving a linear equation with 3unknowns in N, and
some considerations on solving, using natural numbers, equations with n
unknowns.
Let’s consider the equation:
ax=b; (6.1)
wherea2Zn,b2Zor in explicit form
nX
i=1aixi=b; (6.2)
with allai;b2Z,ai6= 0and the greatest common factor
d=gcf(a1;a2;:::;an): (6.3)
90 CHAPTER 6. ANALYTICAL SOLVING
Observation 6.1.The notion of gcd(greatest common divisor) is the same
with the notion of gcf (greatest common factor) for numbers, gcf being
used for algebraic expressions.
1. the notion of gcf refers to numbers and algebraic expressions, for
example:gcf(2abc;8a2b;10abc) = 2ab.
2.gcdrefers only to numbers, for example: gcd(2;8;10) = 2 .
Analogously, the notion of lcm (least common multiple) is the same with
the notion of lcf(least common factory) for numbers, lcfbeing used for
algebraic expressions.
1. the notion of lcfrefers to numbers and algebraic expressions, for
example:lcf(2abc;8a2b;10abc) = 40a2b.
2.lcm refers only to numbers, for example: lcm(2;8;10) = 40 .
Lemma 6.2. The equation (6.2) admits at least a solution in the set of integer, if
d,(6.3) , dividesb.
Proof. This result is classic.
In (6.2), one does not diminish the generality by considering
gcf(a1;a2;:::;an) = 1;
because in the case when d6= 1, one divides the equation by this number;
if the division is not an integer, then the equation does not admit natural
solutions.
It is obvious that each homogeneous linear equation admits solutions
inN: at least the banal solution!
6.2.1 The number of solutions of equation
a1x1+a2x2++anxn=b
We will introduce the following definition:
6.2. GENERAL LINEAR DIOPHANTINE EQUATION 91
Definition 6.3. The equation (6.2) has variations of sign if there are at least
two coefficients ai;aj, with 1i;jn, such thatsign(ai;aj) = 1.
Lemma 6.4. An equation (6.2) which has sign variations admits an infinity of
natural solutions.
Observation 6.5.Lemma 6.4 generalization of lemma 1 of [Andrica and An-
dreescu, 1981].
Proof. From the hypothesis of the lemma it results that the equation has h
no null positive terms, 1hn, andk=n hnon null negative terms.
We have 1kn; it is supposed that the first hterms are positive and
the following kterms are negative (if not, we rearrange the terms).
We can then write:
hX
i=1aixi nX
j=h+1a0
jxj=bwherea0
j= aj>0:
Let’s consider 0<M =lcm(a1;a2;:::;an), the least common multiple,
andci=jM=aij,i2In=f1;2;:::;ng.
Let’s also consider 0<P =lcm(h;k), the least common multiple, and
h1=P=h, andk1=P=k. Taking
xt=h1ctz+x0
t;1th
xj=k1cjz+x0
j; h+ 1jn
wherez2N,
z max
1th<jn( x0
t
h1ct
;"
x0
j
k1cj#)
+ 1;
where [
]meaning integer part of
, i.e. the greatest integer less than or
equal to
, andx0
i,i2In, a particular integer solution (which exists accord-
ing to lemma 6.2), we obtain an infinity of solutions in the set of natural
numbers for the equation (6.2).
Lemma 6.6.
92 CHAPTER 6. ANALYTICAL SOLVING
1. An equation (6.2) which does not have variations of sign has at maximum
a limited number of natural solutions.
2. In this case, for b6= 0, constant, the equation has the maximum number of
solutions if and only if all ai= 1fori2In.
Proof.
1. One considers all ai>0(otherwise, multiply the equation by 1).
Ifb<0, it is obvious that the equation does not have any solu-
tion in N.
Ifb= 0, the equation admits only the trivial solution.
Ifb > 0, then each unknown xi, takes positive integer values
between 0anddi=b=ai(finite), and not necessarily all these
values. Thus the maximum number of solutions is lower or
equal toQn
i=1(1 +di), which is finite.
2. Forb6= 0, constant,Qn
i=1(1 +di)is maximum if and only if diare
maximum, i.e. ifai= 1for alli2In.
Theorem 6.7. The equation (6.2) admits an infinity of natural solutions if and
only if it has variations of sign.
Proof. This naturally follows from the previous results.
6.2.2 Diophantine equation of first order with two unknown
Theorem 6.8. Let’s consider the equation ax by=c, with integer coefficients,
wherea>0andb>0and(a;b) =gcd(a;b) = 1 . Then the general solution in
natural numbers of this equation is:
x=bk+x0
y=ak+y0(6.4)
6.2. GENERAL LINEAR DIOPHANTINE EQUATION 93
where (x0;y0)is a particular integer solution of the equation, and
kmax x0
b
; y0
a
is an integer parameter.
Observation 6.9.The theorem 6.8 generalization of lemma 2 of [Andrica
and Andreescu, 1981].
Proof. It results from [Creang ˘a et al., 1965] that the general integer solution
of the equation is (6.4). Since xandyare natural integers, it is necessary
for us to impose conditions for ksuch thatx0andy0, from which it
results the theorem 6.8.
The solve in the set of natural numbers a linear equation with nun-
knowns we will use the previous results in the following way:
(a) If equation does not have variations of sign, because it has a limited
number of natural solutions, the solving is made by tests.
(b) If it has variations of sign and if bis divisible by d, then it admits an
infinity of natural solutions. One finds its general integer solution,
see [Ion and Nit ,˘a, 1978];
xi=n 1X
j=1ijkj+j; i2In;
where all the ij;j2Zand thekjare integer parameters.
By applying the restriction xi0fori2In, one finds the conditions
which must be satisfied by the parameters kj:
kj2Z;for allj2In 1: (6.5)
The casen= 2 andn= 3 can be done by this method, but when nis
bigger, the conditions (6.5) becomes more and more difficult to find.
94 CHAPTER 6. ANALYTICAL SOLVING
Example 6.10. Solve in Nthe equation 3x 7y+ 2z= 18.
Solution: In Zone obtains the general integer solution:
8
<
:x=k1
y=k1+ 2k2
z= 2k1+ 7k2 9;
withk1andk2inZ.
From the conditions (6.5) result the inequalities x0,y0,z0. It
results that k10and also:
k2 k1
2if k1
2=2Z,
or
k2 k1
2if k1
22Z;
and
k29 2k1
7+ 1if9 2k1
7=2Z,
or
k29 2k1
7if9 2k1
72Z;
that is
k22 2k1
7+ 2if2 2k1
7=2Z,
or
k22 2k1
7+ 1if2 2k1
72Z.
With these conditions on k1andk2we have the general solution in natural
numbers of the equation.
6.2. GENERAL LINEAR DIOPHANTINE EQUATION 95
Procedure for solving Diophantine equations of first order
with two unknowns
For automatically solving the Diophantine equations of order 1 with 2
unknowns ax by=cwe need the following program.
Program 6.11.Program for finding a solution.
S12(a;b;c ) :=return "Error (a;b)6= 1"ifgcd(a;b)6= 1
m 106
forx21::m
fory2floor (ax c 1
b)::ceil (ax c+1
b)
return
x yTif ax by c=0
return "Notfoundasolution "
Example 6.12. We consider the Diophantine equation on the set of natural
numbers 1245x 365y= 4567 . This case is solvable, as gcd(a;b) = 1 .
a:= 124b:= 365c:= 4567gcd(a;b) = 1
x0
y0
:=S12(a;b;c ) =28
3
k0:= maxceil x0
b
ceil y0
a
= 1
x(k) :=bk+x0
y(k) :=ak+y0
96 CHAPTER 6. ANALYTICAL SOLVING
fork:=k0::10we obtain the solutions
x(k)!0
BBBBBBBBBBBBBB@393
758
1123
1488
1853
2218
2583
2948
3313
36781
CCCCCCCCCCCCCCAy(k)!0
BBBBBBBBBBBBBB@121
245
369
493
617
741
865
989
1113
12371
CCCCCCCCCCCCCCA:
Solving of Diophantine equation a1x1+a2x2+:::+anxn=b
In this section we will present the problem of solving for integers equa-
tions of the form:
a1x1+a2x2+:::+anxn=b (6.6)
whereak;b2Zfork2In.
We suppose that not all the numbers ak, fork2In, are null. Obviously,
to exist an integer solution of the equation (6.6) it is necessary that
d= (a1;a2;:::;an) = gcd(a1;a2;:::;an)jb:
We will prove that this condition is also sufficient.
Leta0
k=ak=d,k2Inandb0=b=d. We consider following equation
equivalent with (6.6)
a0
1x1+a0
2x2+:::+a0
nxn=b0(6.7)
then (a0
1;a0
2;:::;a0
n) = 1 . Leta0
k,a0
jbe non-null numbers with k < j and
ja0
kj>a0
j. According to the Theorem of division with remainder, [Burton,
2010], there exist the numbers qandrsuch that
a0
k=a0
jq+r
6.2. GENERAL LINEAR DIOPHANTINE EQUATION 97
and, by substituting a0
kin (6.7) equation
a0
1x1+:::+rxk+:::+a0
j(xj+qxk) +:::+a0
nxn=b0(6.8)
is obtained.
Equation (6.8) can be written as:
a00
1x00
1+:::+a00
nx00
n=b0(6.9)
where
a00
i=a0
i; i6=k
r; i =k; x00
i=xi; i6=k
xj+qxk; i=k:
It can be easily observed that there exists a one-to-one correspondence
between the solutions of equations (6.7) and (6.9). Furthermore, knowing
the solutions of equation (6.9) and taking into account the previous trans-
formations, the solutions of equation (6.7) can also be given.
We mention that, for every i;k2In,i6=kfollowing relations hold:
a00
i=a0
ianda00
k<a0
k:
Additionally, we have
(a00
1;:::;a00
n) = (a0
1;:::;a0
k a0
jq;:::;a0
n) = (a0
1;:::;a0
n) = 1:
After summing all the previous relations, we conclude that equation
(6.7) can be reduced to the form
ea1fx1+:::+fanfxn=b0(6.10)
after a finite number of steps, where eaiwithi2Inare non-null numbers,
whose absolute values are pairwise distinct.
Hence, we deduce that the numbers eai,i2Inhave only the values 0
or1and are not all null. Without any loss of generality of the problem,
we suppose that ea1= 1. Then equation (6.10) has following solutions
8
>><
>>:fx1=b0 ea2t2 ::: fantn
fx2=t2
:::
fxn=tn
98 CHAPTER 6. ANALYTICAL SOLVING
wheret2;t3;:::;tnare arbitrary integers. Using the transformations done
along the previous reasonings, the solutions of equation (6.7) are also ob-
tained.
We insist on mentioning that in solving equation (6.10) the fact that
ea1= 1 was used, and, therefore, if at a certain step of the indicated algo-
rithm an equation with at least one coefficient equal to 1is obtained, the
solution of this equation can be written similarly with the solution of the
equation (6.10).
6.3 Solving the Diophantine linear systems
More generally, every system of linear Diophantine equations may be
solved by computing the Smith normal form of its matrix, in a way that is
similar to the use of the reduced row echelon form to solve a system of linear
equations over a field.
ABS algorithm for solving linear Diophantine equations, Gao and
Dong [2008] introduce an algorithm for solving a system of mlinear in-
teger inequalities in nvariables,mn, with full rank coefficient matrix.
6.3.1 Procedure of solving with row–reduced echelon form
Echelon form (or row echelon form) is:
1. All nonzero rows are above any rows of all zeros.
2. Each leading entry (i.e. leftmost nonzero entry) of a row is in a col-
umn to the right of leading entry of the row above it.
3. All entries in a column below a leading entry are zero.
Example 6.13. Echelon forms:
0
BB@
0
0 0 0 0 0
0 0 0 0 01
CCA;0
BB@
0
0 0
0 0 01
CCA;
6.3. SOLVING THE DIOPHANTINE LINEAR SYSTEMS 99
0
BBBB@0
0 0 0
0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
CCCCA:
where we noted with any nonzero integer and with any integer.
Reduced echelon form: Add the following conditions to conditions 1,2
and3above.
4. The leading entry in each nonzero row is 1.
5. Each leading 1is the only nonzero entry in its column.
A matrix is in reduced row echelon form, also called row canonical form , if
it satisfies the following conditions, [Meyer, 2000].
Example 6.14. Reduced echelon form:
0
BBBB@0 10 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1
CCCCA:
The theorem uniqueness of the reduced echelon form, [Nakos and
Joyner, 1998, Meyer, 2000]:
Theorem 6.15. Each matrix is row-equivalent to one and only one reduced ech-
elon matrix.
Definition 6.16. Pivot position is a position of a leading entry in an eche-
lon form of the matrix.
Definition 6.17. Pivot is a nonzero number that either is used in a pivot
position to create 00s or is changed into a leading 1, which in turn is used
to create 00s.
100 CHAPTER 6. ANALYTICAL SOLVING
Definition 6.18. Pivot column is a column that contains a pivot position.
The theorem existence and uniqueness, [Nakos and Joyner, 1998,
Meyer, 2000].
Theorem 6.19.
1. A linear system is consistent if and only if the rightmost column of aug-
mented matrix is not a pivot column (i.e. if and only if an echelon form of
the augmented matrix has no row of the form [0 0:::0b], whereb6= 0).
2. If a linear system is consistent, then the solution contains either
(a) a unique solution (when there are no free variables) or
(b) infinitely many solutions (when there is at least one free variable).
Algorthm 6.20.The algorithm using reduced row echelon form to solve
linear system:
1. Write the augmented matrix of the system.
2. Use the row reduction algorithm to obtain equivalent augmented
matrix in echelon form. Decide whether the system is consistent. If
not stop; otherwise go to the next step.
3. Continue row reduction to obtain the reduced echelon form.
4. Write the system of equations corresponding to the matrix obtained
in step 3.
5. State the solution by expressing each basic variable in terms of free
variables and declare the free variables.
Example 6.21. Solving by means of symbolic computation of a Diophan-
tine linear system using the method row reduced echelon form . We consider
the origin of the vectors and matrices equal to 1.
ORIGIN := 1
6.3. SOLVING THE DIOPHANTINE LINEAR SYSTEMS 101
We consider the system Ax=b, where
A:=0
@0 3 6 6 4
3 7 8 5 8
3 9 12 9 61
Ab:=0
@ 5
9
151
A:
We concatenate matrix Ato the free term band we determine the num-
ber of lines and columns of matrix E
E:=augment (A;b)n:=rows (E)!3cols(E)!6:
By means of the Mathcad function rref we determine the row reduced
echelon form of matrixE.
R:=rref(E)!0
@1 0 2 3 0 24
0 1 2 2 0 7
0 0 0 0 1 41
A:
According to this matrix, it follows that the main unknowns are x1,x2
andx5, whilex3andx4are the secondary unknowns.
S(x1;x2;x3;x4;x5) :=
submatrix (R;1;n;1;m 1)0
BBBB@x1
x2
x3
x4
x51
CCCCA Rhmi!
0
@x1 2×3+ 3×4+ 24
x2 2×3+ 2×4+ 7
x5 41
A
We determine x1,x2andx5relative tox3andx4.
x1x2x5
:=
S(x1;x2;x3;x4;x5)solve
x1x2x5
!
2×3 3×4 24 2×3 2×4 7 4
:
102 CHAPTER 6. ANALYTICAL SOLVING
We verify if the obtained solution satisfies the equation
A0
BBBB@x1
x2
x3
x4
x51
CCCCA b= 0;
A0
BBBB@2×3 3×4 24
2×3 2×4 7
x3
x4
41
CCCCA b!0
@0
0
01
A:
It is obvious that for different integer values of x3andx4there result
integer solutions for the linear system.
Example 6.22. Linear Diophantine system that has a unique solution. We
consider the linear system with
A:=0
@3 4
2 5
2 31
A0
@ 3
5
11
A:
We consider matrix Eand we count the number of lines and columns
of matrixE.
E:=augment (A;b)n:=rows (E)!3cols(E)!3:
The matrix row reduced echelon form is
R:=rref(E)!0
@1 0 5
0 1 3
0 0 01
A:
6.3. SOLVING THE DIOPHANTINE LINEAR SYSTEMS 103
We compute
S(x1;x2) :=
submatrix (R;1;n;1;m 1)x1
x2
Rhmi!0
@x1+ 5
x2 3
01
A:
From this result follows that the main unknowns are x1andx2which
do not depend on any other variable and we have x1= 5andx2= 3.
Indeed, it is verified that
A 5
3
b=0
@0
0
01
A:
Example 6.23. Linear Diophantine system that has no solutions. We con-
sider matrix Aand vector b
A:=0
BB@1 1 1
1 2 4
1 3 9
1 4 161
CCA0
BB@ 1
3
3
51
CCA:
Let be matrix E
E:=augment (A;b)n:=rows (E)!4m:=cols(E)!4:
We compute the matrix row-reduced echelon form by means of function
rref
R:=rref(E)!0
BB@1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 11
CCA:
104 CHAPTER 6. ANALYTICAL SOLVING
Following calculation is done
S(x1;x2;x3) :=
submatrix (R;1;n;1;m 1)0
@x1
x2
x31
A Rhmi!0
BB@x1
x2
x3
11
CCA:
We try to solve by means of symbolic computation, using function
solve , the equation S(x1;x2;x3)=0:
S(x1;x2;x3)=0solve (x1;x2;x3)!
Nosolutionwasfound:
The Mathcad’s answer is: No solution was found .
Example 6.24. Linear Diophantine system with matrix Aand free term b
A:=0
BBBB@1 2 3 4 5 6
1 4 9 16 25 36
1 8 27 64 125 216
1 16 81 256 625 1296
1 32 243 1024 3125 77761
CCCCAb:=0
BBBB@104
140
2750
7952
873741
CCCCA:
MatrixEis obtained by concatenating vector bto matrixA.
E:=augment (A;b)n:=rows (E)!5m:=cols(E)!7:
We compute the matrix row-reduced echelon form by means of function
rref
R:=rref(E)!0
BBBB@1 0 0 0 0 1980 17833
0 1 0 0 0 3465 31185
0 0 1 0 0 3080 27719
0 0 0 1 0 1386 12469
0 0 0 0 1 252 22721
CCCCA:
6.3. SOLVING THE DIOPHANTINE LINEAR SYSTEMS 105
We compute
S(y1;y2;y3;y4;y5;y6) :=
submatrix (R;1;n;1;m 1)0
BBBBBB@y1
y2
y3
y4
y5
y61
CCCCCCA Rhmi!
0
BBBB@y1+ 1980y6 17833
y2 3465y6+ 31185
y3+ 3080y6 27719
y4 1386y6+ 12469
y5+ 252y6 22721
CCCCA:
We solve by means the symbolic computation, using function solve ,
equationS(y1;y2;y3;y4;y5;y6)=0:
0
BBBB@y1
y2
y3
y4
y51
CCCCA:=S(y1;y2;y3;y4;y5;y6)=0solve0
BBBB@y1
y2
y3
y4
y51
CCCCA!
0
BBBB@17833 1980y6
31185 + 3465y6
27719 3080y6
12469 + 1386y6
2272 252y61
CCCCA:
6.3.2 Solving with Smith normal form
Using matrix notation every system of linear Diophantine equations
may be written
AX=C
106 CHAPTER 6. ANALYTICAL SOLVING
whereAis amnmatrix of integers, Xis an1column matrix of
unknowns and Cis am1column matrix of integers.
The computation of the Smith normal form of Aprovides two unimod-
ular matrices (that is matrices that are invertible over the integers, which
have1as determinant) UandVof respective dimensions mm and nn,
such that the matrix
B= [bi;j] =UAV
is such that bi;iis not zero for inot greater than some integer k, and all the
other entries are zero. The system to be solved may thus be rewritten as
B(V 1X) =UC:
Callingyithe entries of V 1Xanddithose ofD=UC, this leads to the
system
bi;iyi=difor1ik
0yi=di fork<in
This system is equivalent to the given one in the following sense: Acol-
umn matrix of integers xis a solution of the given system if and only if
x=Vyfor some column matrix of integers ysuch thatBy=D.
It follows that the system has a solution if and only if bi;idividesdifor
ikanddi= 0fori>k . If this condition is fulfilled, the solutions of the
given system are
V0
BBBBBBBBB@d1
b1;1…
dk
bk;k
hk+1
…
hn1
CCCCCCCCCA
wherehk+1;:::;hnare arbitrary integers, [Schmidt, 1991, Lazebnik, 1996,
Smart, 1998].
6.4. SOLVING THE DIOPHANTINE EQUATION OF ORDER N 107
6.4 Solving the Diophantine equation
of ordernwith an unknown
The Diophantine equation of order nwith a single unknown is
P(x) =anxn+an 1xn 1+:::+a1x+a0= 0; (6.11)
whereak2Z,an6= 0. The problem that arises is to find the solutions
that are rational numbers ( Q) or integers ( Z) or natural numbers ( N). As
it is well known, the Fundamental Theorem of Algebra, [Krantz, 1999],
assures the existence of ncomplex solutions for the algebraic equation of
ordern. Therefore, the Diophantine equation (6.11) can not have more
thannrational, integer or natural solutions.
Leaving from ”Vieta’s formula”, [Vi `ete, 1646, Girard, 1884]:
s1s2sn= ( 1)na0
an;
whereskare the roots of polynomial P, which means P(sk) = 0 , fork2In,
it results a classic method. This method supposes finding all the divisors of
anand ofa0. Afterwards, the set of numbers that divide an=a0is generated
(finite set,0(an)0(a0)) and it is tested which of those divisors are roots
of polynomial P.
We give an automatic procedure for finding the rational, integer or nat-
ural solutions which uses following 3programs.
Program 6.25.Program to find the divisors of a natural number.
Div(m) :=j 0
dj 1
fork22::floor (m
2)
if mod (m;k)=0
j j+ 1
dj k
d stack (d;m)
returnd
108 CHAPTER 6. ANALYTICAL SOLVING
Program 6.26.Program to find the factors (repetition excluded) of the num-
bera0=an. This program calls the program 6.25.
Factori (a) :=d0 Div(ja0j)
dn Div(alast(a))
f d0
i last(f) + 1
fork20::last (d0)
forj21::last (dn)
fi d0k
dnj
i i+ 1
f sort(f)
j 0
wj f0
fork21::last (f)
if wj6=fk
j j+ 1
wj fk
returnw
Program 6.27.Program to find the rational solutions for the input param-
etert= 0, the integer solutions for the input parameter t= 1 and the
natural solutions for the input parameter t= 2. This program calls the
programs 6.26 and 1.26.
Sqzn (a;t) :=retur "Errort6= 0^1^2"if t6= 0^t6= 1^t6= 2
f Factori (a)
fs sort(f)
f stack ( reverse (fs);fs)
w f if t =0
if t=1
j 0
fork20::last (f)
if fk=trunc (fk)
wj fk
6.4. SOLVING THE DIOPHANTINE EQUATION OF ORDER N 109
j j+ 1
if t=2
j 0
fork20::last (f)
if fk=trunc (fk)^fk0
wj fk
j j+ 1
i 0
fork20::last (w)
if Horner (a;wk)=0
si wk
i i+ 1
returnsT
Example 6.28. We consider the polynomial defined by the vector
a:=
96 776 1568 134 1620 359 466 49 30T;
afterwards we consider the calls
S(a;2)!
3
;
S(a;1)!
4 2 3
;
S(a;0)!
4 21
51
22
33
:
The first call states that the polynomial defined by vector ahas a unique
natural solution; the second call tells us that the polynomial has 3 inte-
ger solutions; while the third call shows hat the polynomial has 6 integer
solutions.
The second method supposes finding all the roots of the polynomial
by means of formula for polynomials of order n4and emphasizing the
rational, integer or natural roots.
110 CHAPTER 6. ANALYTICAL SOLVING
As the polynomials of degree n>4can not be solved with square roots
(Impossibility Theorem, Abel [1826, 1881, 1988] and Galois 1832, [Artin,
1944], (this was also shown by Ruffini in 1813 [Wells, 1986]), the roots of
the polynomial will be approximated by a numerical method, usually La-
guerre’s method, [Cira, 2005](probably the best numerical method for ap-
proximating the solutions of a algebraic equation. This method is imple-
mented in most of the mathematics softwares, such as Maple, Mathemat-
ica, Matlab, Mathcad.
The approximative roots which are ”close” to rational, integer or natu-
ral numbers are verified by direct computation (Schema of Horner [1819],
the fastest algorithm for computing the values of an algebraic polynomial)
if those numbers are the solutions of the equation P(x) = 0 . We give an
example of how this method is applied.
Example 6.29. Let be the algebraic equation P(x) = 0 , where polynomial
Pis defined by the vector
a:= (2074506308666643852 ; 4170138555243755952 ;
3708600060698625999 ; 2371615921694294428 ;
1144052588009550927 ; 392768652155202268 ;
93951730922422481 ; 15744238825971732 ;
1864646677195241 ; 156394532149220 ;
9205044609900 ; 370727876000 ;
9701590000 ; 148200000;1000000)T
The call of Mathcad function polyroots will give approximations for the
6.4. SOLVING THE DIOPHANTINE EQUATION OF ORDER N 111
solutions of the algebraic equation P(x) = 0
s:=polyroots (a)
=0
BBBBBBBBBBBBBBBBBBBBBBB@ 0:00000000595668852 2:0000000743130992 i
0:00000000540100408 + 2 :00000007346564 i
1:0999993750452355
5:097397296153272
5:911537626129313
6:877530938768753
8:128108099781006
9:08388413343586
10:99946985840438
13:00329871837791
16:99735261469869
19:00160713253058
22:99980560963407
29:000008608398621
CCCCCCCCCCCCCCCCCCCCCCCA:
Aside the fist two solution which are complex numbers,the other so-
lutions are ”close” to natural numbers. By direct computation it can be
established which of these ”close” integer are solutions natural numbers.
P(1)!72560416394188800 ;
P(5)! 856324819703808 ;
P(6)! 202256700445800 ;
P(7)!153045758638080 ;
P(8)!161732639306700 ;
P(9)! 274961651328000
P(11)!0;
P(13)!0;
P(17)!0;
P(19)!0;
P(23)!0;
P(29)!0:
112 CHAPTER 6. ANALYTICAL SOLVING
The conclusion is that equation P(x) = 0 has following solutions natural
numbers: 11,13,17,19,23and29.
In the case of algebraic equations of order 1,2,3and4the solutions are
obtained by means of symbolic calculus, by applying well known formu-
las.
Equation 29×2 490x+ 1469 = 0 has the solutions
29×2 490x+ 1469solve0
B@13
113
291
CA
which implies that there exists a rational solution and a natural solution.
Equation 127×3 28829×2 12767x+ 2898109 = 0 has the solutions
127×3 28829×2 12767x+ 2898109solve!0
BBBBBBBB@227
p
1621409
127
p
1621409
1271
CCCCCCCCA
hence, we have a unique solution natural number.
Equation 3×4 7×3+ 17×2 35x+ 10 = has the solutions
3×4 7×3+ 17×2 35x+ 10solve!0
BBBBBBBBBB@2
1
3
p
5i
p
5i1
CCCCCCCCCCA
therefore we have a solution natural number and a solution rational num-
ber.
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 113
6.5 The Diophantine equation of second order
and with two unknowns
We consider the equation
ax2 by2+c= 0; (6.12)
witha;b2Nandc2Z. It is a generalization of Pell’s equation
x2 Dy2= 1, [Dickson, 2005]. Here, we show that: if the equation has an
integer solution and abis not a perfect square, then (6.12) has an infini-
tude of integer solutions; in this case we find a closed expression (xn;yn),
the general positive integer solution, by an original method. More, we
generalize it for any Diophantine equation of second degree and with two
unknowns.
6.5.1 Existence and number of solutions of Diophantine
quadratic equations with two unknowns in ZandN
We study the existence and number of solutions in the set of integers,
Zand the set of natural numbers, Nof Diophantine equations of second
degree with two unknowns of the general form (6.12).
Theorem 6.30. The equation x2 y2=cadmits integer solutions if and only if
cbelongs to 4Zor is odd.
Proof. The equation (x y)(x+y) =cadmits solutions in Zif there exist
c1andc2inZsuch thatx y=c1,x+y=c2andc1c2=c. Therefore
x=c1+c2
2andy=c2 c1
2:
Butxandyare integers if and only if c1+c222Z, i.e.:
1. orc1andc2are odd, then cis odd (and reciprocally),
2. orc1andc2are even, then c24Z.
114 CHAPTER 6. ANALYTICAL SOLVING
Reciprocally, if c24Z, then we can decompose up cinto two even
factorsc1andc2, such thatc1c2=c.
Remark 6.31.The theorem 6.30 is true also for solving in N, because we can
supposec0(in the contrary case, we can multiply the equation by 1),
and we can suppose c2c10, from which x0andy0.
Theorem 6.32. The equation x2 dy2=c2(wheredis not a perfect square)
admits infinity of solutions in N.
Proof. Let’s consider x=ck1,k12Nandy=ck2,k22N,c2N. It re-
sults thatk2
1 dk2
2= 1, which we can recognize as being the Pell-Fermat’s
equation, which admits an infinity of solutions in N,(un;vn). Therefore
xn=cun,yn=cvnconstitute an infinity of natural solutions for our equa-
tion.
Theorem 6.33. The equation (6.12) ,c6= 0, whereab=k2,k2Z, admits a
finite number of natural solutions.
Proof. We can consider a;b;c as positive numbers, otherwise, we can mul-
tiply the equation by 1and we can rename the variables.
Let us multiply the equation by a, then we will have:
z2 t2=dwithz=ax2N; t=ky2Nandd=ac> 0: (6.13)
We will solve it as in theorem 6.30, which gives zandt. But in (6.13)
there is a finite number of natural solutions, because there is a finite num-
ber of integer divisors for a number in N. Because the pairs (z;t)are in a
limited number, it results that the pairs (z=a;t=k )also are in limited num-
ber, and the same for the pairs (x;y).
Theorem 6.34. If the equation (6.2) , whereab6=k2,k2Z, admits a particular
nontrivial solution in N, then it admits an infinity of solutions in N.
Proof. Let’s consider:
xn=x0un+by0vn;
yn=y0un+ax0vn;(6.14)
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 115
forn2N, where (x0;y0)is the particular natural solution for the equation
(6.12), and (un;vn)is the general natural solution for the equation u2
abv2= 1, called the solution Pell, which admits an infinity of solutions.
Thenax2
n by2
n= (ax2
0 by2
0)(u2
n abv2
n) =c. Therefore (6.14) verifies the
equation (6.12).
6.5.2 Method of solving the Diophantine equation of second or-
der
Suppose (6.12) has many integer solutions. Let (x0;y0),(x1;y1)be the
smallest positive integer solutions for (6.12), with 0x0< x 1. We con-
struct the recurrent sequences:
xn+1=xn+yn
yn+1=
xn+yn(6.15)
putting the condition (6.15) verify (6.12). It results:
a =b
(6.16)
a2 b
2=a (6.17)
a2 b2= b (6.18)
having the unknowns ;;
; .
We pull out a2anda2from (6.17), respectively (6.18), and replace
them in (6.16) at the square; it obtains
a2 b
2=a: (6.19)
We subtract (6.19) from (6.17) and find
=: (6.20)
Replacing (6.20) in (6.16) it obtains
=b
a
: (6.21)
116 CHAPTER 6. ANALYTICAL SOLVING
Afterwards, replacing (6.20) in (6.17), and (6.21) in (6.18) it finds the
same equation:
a2 b
2=a: (6.22)
Because we work with positive solutions only, we take
xn+1=0xn+b
a
0yn (6.23)
yn+1=
0xn+0yn (6.24)
where (0;
0)is the smallest, positive integer solution of (6.22) such that
0
06= 0. Let
A=
0b
a
0
00!
2M 2(Z): (6.25)
Of course, if (x0;y0)is an integer solution for (6.12), then
Ax0
y0
; A 1x0
y0
are another ones, where
A 1=1
2b a2 a
b
b a
is the inverse matrix of A, i.e.A 1A=AA 1=I(unit matrix). Hence, if
(6.12) has an integer solution it has an infinite ones. Clearly A 12M 2(Z).
The general positive integer solution of the equation (6.12) is (x0
n;y0
n) =
(jxnj;jynj).xn
yn
=Anx0
y0
for alln2Z; (6.26)
where by conversion A0=Iand
A k=A 1A 1
|{z}
k times:
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 117
In problems it is better to write general solution as
x0
n
y0
n
=Anx0
y0
n2N (6.27)
and x00
n
y00
n
=Anx1
y1
n2N: (6.28)
We proof, by reduction ad absurdum , (6.28) is a general positive integer
solution for (6.12).
Let(u;v)be a positive integer particular solution for (6.12). If
9k02N: (u;v) =Ak0x0
y0
or
9k12N: (u;v) =Ak1x0
y0
;
then (u;v)2(6.28). Contrary to this, we calculate
(ui+1;vi+1) =A 1ui
vi
fori= 0;1;2;:::, whereu0=u,v0=v. Clearlyui+1<uifor alli. After a
certain rank x0<ui0<x 1it finds either 0ui0<x 0but that is absurd.
It is clear we can put
xn
yn
=Anx0
"y0
n2N;where"=1: (6.29)
We shall now transform the general solution (6.29) in closed expres-
sion.
Letbe real number, then det(A I) = 0 involves the solutions 1;2
and the proper vectors v1;2i.e.
Avi=ivi;fori2I2:
118 CHAPTER 6. ANALYTICAL SOLVING
Note
P=
v1v2
2M 2(R):
Then
P 1AP=10
02
;
whence
An=Pn
10
0n
2
P 1
and replacing it in (6.29) and doing the calculus we find a closed expres-
sion for (6.29).
6.5.3 Procedure for solving of Diophantine equation
of second order with two unknowns
We will present an automatic procedure for solving Diophantine equa-
tions (6.12). We have two programs that establish the basis matrix (6.25)
and the particular minimal solution. The input variables are the integer
constantsa,bandc. Finding the basis matrix and the minimal solution is
done up to a given limit (in our case up to m= 106, obviously this limit
can be augmented).
Program 6.35.Program for finding the basis matrix.
M(a;b) :=m 106
for22::m
q r
b
a( 1)(+ 1)
breakif q =trunc (q)^a
bq=trunca
bq
return
q
a
bq !
if <m
return "ErrorMatrixAwasnotfound "otherwise
Program 6.36.Program for finding the minimal solutions.
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 119
SM(a;b;c ) :=m 106
fory21::m
d by2 c
a
if d0
x p
d
breakif x =trunc (x)
returnx x
y y
if y<m
return "ErrorSwasnotfound "otherwise
Example 6.37. For the Diophantine equation 2×2 3y2= 5, we give the
sequence of symbolic Mathcad commands which completely solve analyt-
ically the Diophantine equation. Origin indices are considered 1by using
the command ORIGIN := 1.
We initialize the constants a,bandc
a:= 2b:= 3c:= 5
The determine the basis matrix Aand the eigenvalues of the matrix by
means of the Mathcad function eigenvals
A:=M(a;b) =5 6
4 5
:=eigenvals (A)!5 + 2p
6
5 2p
6
We determine the eigenvectors of matrix Awith the aid of the Mathcad
functioneigenvec and we build matrix V
V:=augment (eigenvec (A; 1);eigenvec (A; 2))!0
@p
6
2 p
6
2
1 11
A
We have matrix P(n)given by formula (where P(n) =An):
P(n) :=V(1)n0
0 (2)n
V 1
120 CHAPTER 6. ANALYTICAL SOLVING
We determine the minimal solutions
SM(a;b;c )!2 2
1 1
S0:=SM(a;b;c )h1i!2
1
S1:=SM(a;b;c )h2i!2
1
The general solutions of the Diophantine equation are S0(n)andS1(n)
S0(n) := (AnS0)TS1(n) := (AnS1)T
The explicit formulas for the general solutions are T0(n)andT1(n)
T0(n) :=P(n)S0factor!
0
B@(p
6 + 4)(5 + 2p
6)n (p
6 4)(5 2p
6)n
4
(2p
6 3)(5 2p
6)n (2p
6 + 3)(5 + 2p
6)n
61
CA
T1(n) :=P(n)S1factor!
0
B@(p
6 + 4)(5 2p
6)n (p
6 4)(5 + 2p
6)n
4
(2p
6 + 3)(5 2p
6)n (2p
6 3)(5 + 2p
6)n
61
CA
Letn= 0;1;2;:::; 10
n:= 0::10
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 121
We display the solutions for n
S0(n)!0
BBBBBBBBBBBBBBBBB@2 1
16 13
158 129
1564 1277
15482 12641
153256 125133
1517078 1238689
15017524 12261757
148658162 121378881
1471564096 1201527053
14566982798 118938916491
CCCCCCCCCCCCCCCCCA
S1(n)!0
BBBBBBBBBBBBBBBBB@2 1
4 3
38 31
376 307
3722 3039
36844 30083
364718 297791
3610336 2947827
35738642 29180479
353776084 288856963
3502022198 28593891511
CCCCCCCCCCCCCCCCCA
The displayed solutions can be tested if we verify the Diophantine
equation by the aid of the sequences:
a(S0(n)1)2 b(S0(n)2)2+c!
0 0 0 0 0 0 0 0 0 0 0T
a(S1(n)1)2 b(S1(n)2)2+c!
0 0 0 0 0 0 0 0 0 0 0T
122 CHAPTER 6. ANALYTICAL SOLVING
The solutions given by the expressions T0(n)andT1(n)can also be dis-
played, as follows:
T0(n)1T0(n)2
!0
BBBBBBBBBBBBBBBBB@2 1
16 13
158 129
1564 1277
15482 12641
153256 125133
1517078 1238689
15017524 12261757
148658162 121378881
1471564096 1201527053
14566982798 118938916491
CCCCCCCCCCCCCCCCCA;
T1(n)1T1(n)2
!0
BBBBBBBBBBBBBBBBB@2 1
4 3
38 31
376 307
3722 3039
36844 30083
364718 297791
3610336 2947827
35738642 29180479
353776084 288856963
3502022198 28593891511
CCCCCCCCCCCCCCCCCA:
Obviously these solutions are identical with those given by S0(n)and
S1(n).
Basically, any Diophantine equation of the type (6.12) can be com-
pletely solved with this set of commands.
Example 6.38. Let us consider the equation 13×2 17y2+ 2636 = 0 . The
basis matrix is
A:=M(13;17) =1665 1904
1456 1665
:
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 123
The minimal solutions are:
S0!19
11
S1!19
11
:
the solutions are given by the formulas:
S0(n) := (AnS0)TS1(n) := (AnS1)T:
The values given by S0forn= 0;1;2and10are:
19;11;52579;45979;175088051;153110059
and
2647342081327033989423041791914721331 ;
2315033492863349726442025803342919339 ;
and the values provided by S1forn= 0;1;2and10are:
19; 11;10691;9349;35601011;31132181
and
538289472181531211118549596688006131 ;
470720488200496189286367630993971861 :
The explicit solutions are:
T0(n) :=P(n)S0factor!
0
B@(11p
221 + 247)n
1 (11p
221 247)n
2
26
(19p
221 + 187)n
1 (19p
221 187)n
2
341
CA
where
1= 1665 + 112p
221; 2= 1665 112p
221
124 CHAPTER 6. ANALYTICAL SOLVING
and
T1(n) :=P(n)S1factor!
0
B@(11p
221 + 247)n
2 (11p
221 247)n
1
26
(19p
221 + 187)n
2 (19p
221 187)n
1
341
CA;
forn2N.
6.5.4 Generalizations
Iff(x;y) = 0 is a Diophantine equation of second degree and with two
unknowns, by linear transformations it becomes (6.12).
Ifab0the equation has at most a finite number of integer solutions
which can be found attempts. It is easier to present an example.
The Diophantine equation
18×2+ 12xy 26y2 12x 32y+ 40 = 0 (6.30)
becomes
2u2 7v2+ 45 = 0; (6.31)
where (unfortunately, finding these substitutions is a difficult problem)
u= 3x+y 1;
v= 2y+ 1:(6.32)
The basis matrix for the Diophantine equation (6.31) is
A:=M(2;7) =15 28
8 15
and the minimal solutions are S0= (3 3)TandS1= (3 3)T. In this
conditions we obtain the solutions S0(n) =AnS0andS1(n) =AnS1.
FormulaS1(n)produces as solutions negative integers. Back from the
6.5. THE DIOPHANTINE EQUATION OF SECOND ORDER 125
solutions obtain with formula S0(n)to variables xandyby means of the
substitutions8
>><
>>:x=2u v 3
6
y=v 1
2
we obtain the solution of the Diophantine equation (6.30). The first 11
positive integer solutions are:
0
BBBBBBBBBBBBBBBBB@1 1
32 34
945 1033
28304 30970
848161 928081
25416512 27811474
761647185 833416153
22823999024 24974673130
683958323521 748406777761
20495925706592 22427228659714
614193812874225 6720684530136731
CCCCCCCCCCCCCCCCCA:
We solve (6.31). Thus:
un+1= 15un+ 28vn;
vn+1= 8un+ 15vn;(6.33)
n2N, with (u0; v0) = (3;3").
First solution
By induction we proof that: for all n2Nwe havevnis odd, and un
as well asvnare multiple of 3. Clearlyv0= 3"u0. Forn+ 1 we have
vn+1= 8un+ 15vn=even +odd=odd, and of course un+1,vn+1are
multiples of 3becauseun,vnare multiple 3, too.
126 CHAPTER 6. ANALYTICAL SOLVING
Hence, there exist xn,yn, in positive integers for all n2N:
8
>><
>>:xn=2un vn+ 3
6;
yn=vn 1
2;(6.34)
(from (6.32)). Now we find the (6.29) for (6.31) as closed expression, and by
means of (6.34 it results the general integer solution of the equation (6.30).
Second solution
Another expression of the (6.29) for (6.30) we obtain if we transform
(6.32) as:un= 3xn+yn 1andvn= 2yn+ 1, for alln2N. Whence, using
(6.33) and doing the calculus, it finds
8
><
>:xn+1= 11xn+52
3yn+11
3;
yn+1= 12xn+ 19yn+ 3;(6.35)
forn2N, with (x0;y0) = (1;1)or(2; 2)(two infinitude of integer
solutions). Let
A=0
BBBBB@1152
311
3
12 9 3
0 0 11
CCCCCA:
Then 0
@xn
yn
11
A=An0
@1
1
11
A
or 0
@xn
yn
11
A=An0
@2
2
11
A; (6.36)
6.6. THE DIOPHANTINE EQUATION X2 2Y4+ 1 = 0 127
alwaysn2N.
From (6.35) we have always yn+1yn:::y01 (mod 3), hence
alwaysxn2Z. Of course (6.36) and (6.34) are equivalent as general integer
solution (6.30).
This method can be generalized for Diophantine equations
nX
i=1aix2
i=b; (6.37)
will allai;b2Z.
It alwaysaiaj0 1ij < n , the equation (6.37) has most finite
number of integer solution.
Now, we suppose 9i0;j02Infor whichai0aj0<0(the equation
presents at least a variation of sign). Analogously, for n2N. We define
the recurrent sequence:
x(n+1)
h=nX
i=1aihx(n)
i 1h2In (6.38)
considering (x0
1;x0
2;:::;x0
n)the smallest positive integer solution of (6.37).
It replaces (6.38) in (6.37), it identifies the coefficients and it look for the
n2unknowns aih, wherei;h2In. This calculus is very intricate, but it
can done by means of a computer. The method goes on similarly, but the
calculus becomes more and more intricate – for example to calculate An.
It must computer may be.
Other results referring to Diophantine equations can be found in the
papers [Landau, 1955, Long, 1965, Ogibvy and Anderson, 1966, Mordell,
1969, Hardy and Wright, 1984, Bencze, 1985, Borevich and Shafarevich,
1985, P ´erez et al., 2013].
6.6 The Diophantine equation x2 2y4+ 1 = 0
In this section we present a method of solving this Diophantine equa-
tion, method which is different from Ljunggren’s, Mordell’s and Guy’s.
128 CHAPTER 6. ANALYTICAL SOLVING
In the book [Guy, 1981, pp. 84-85] to shows that equation x2= 2y4 1
has, in the set of positive integers, only solutions 1;1and 239;13; Ljung-
gren [1966] has proved it in a complicated way. But Mordell [1964] gave
an easier proof.
We’ll notet=y2. The general integer solution for x2 2t2+ 1is
xn+1= 3xn+ 4tn;
tn+1= 2xn+ 3tn
for alln2N, where (x0;y0) = (1;"), with"=1or
xn
tn
=3 4
2 3n
1
"
;
for alln2N, where a matrix to the power zero is equal to the unit matrix
I.
Let’s consider
A=3 4
2 3
;
and2R. Thendet(A I) = 0 implies1;2= 3p
2, whence if vis a
vector of dimension two, then Av=1;2v.
Let’s consider
P=2 2p
2 p
2
and
D=3 +p
2 0
0 3 p
2
:
We haveP 1AP=D, or
An=PDnP 1=0
B@an+bn
2p
2(an bn)
2 p
2(an bn)
4an+bn
21
CA:
6.6. THE DIOPHANTINE EQUATION X2 2Y4+ 1 = 0 129
wherean= (3 + 2p
2)nandbn= (3 2p
2)n. Hence, we find
xn
tn
=0
B@1 +"p
2
2an+1 "p
2
2bn
2"+p
2
4an+2"
