Elementary Theory 00 Grif
Elementary Theory 00 Grif
Elementary Theory 00 Grif
INTERNATIONAL SERIES IN
PURE AND APPLIED MATHEMATICS
weinstock •
Calculus of Variations
weiss •
Algebraic Number Theory
zemanian •
Distribution Theory and Transform Analysis
ELEMENTARY
THEORY OF NUMBERS
HARRIET GRIFFIN
Associate Professor of Mathematics
Brooklyn College
1954
ELEMENTARY THEORY OF NUMBERS
Copyright, 1954, by the McGraw-Hill Book Company, Inc. Printed in the
United States of America. All rights reserved. This book, or parts thereof,
may not be reproduced in any form without permission of the publishers.
6789-MP-9876
24785
PREFACE
PREFACE v
chapter 8. INDICES
8-1. Indices for a prime modulus 125
8-2. Euler's criterion for the solvability of x n = c(mod m) 129
BIBLIOGRAPHY 197
INDEX 199
CHAPTER 1
1-1. The Development of the Integers. The rational integers are the
result ofmany centuries of development of the concept of number.
Doubtless man learned first to distinguish oneness and otherness without
abstracting the idea of number itself. The basic notion in the concept of
number is that of one-to-one correspondence. If there are two sets of
elements, A and B, and if to each element of A there is assigned exactly
one element of B, while each element of B is thereby related to a single
element of A, the relationship is called a one-to-one reciprocal correspond-
ence. By means of such a relation a man could determine that he had
exactly as many rings as he had fingers even though he had not learned to
count. Any two sets that can be put into one-to-one correspondence are
said to have the same number. Thus the concept of number implies the
abstraction of that property which is common to sets that are so related.
However imperfect these concepts may have been, man did eventually
learn to count and to represent by marks the ideas now represented by
the symbols 1, 2, 3, . These numbers have the single property of
. . .
denoting quantity. They answer the question, How many units? They
are the natural numbers, and they were the only numbers known to the
Greeks until Diophantus (c. 275) extended the concept of number to
include fractions. To be sure the Ahmes papyrus, which was written
before 1700 B.C., indicates that in their calculations the Egyptians
employed symbols that are equivalent to fractions with numerator one,
but such symbols, even to the Greeks of Euclid's time, referred to the
notion of magnitude rather than number. The art of calculating was
thus distinguished from the science of number. It is to be noted that
zero is not among the natural numbers. The Greeks had no symbol for
zero. It was probably not until the fifth century that the Hindus intro-
duced a symbol for zero and the principle of position in writing numbers.
These were, indeed, great accomplishments in the field of arithmetic.
By the twelfth century the advancement of the Hindus in algebra almost
matched their achievements in arithmetic, for they were the first to
recognize the existence of negative quantities even though they did not
admit them as solutions of their problems. It was not until the sixteenth
century that European mathematicians reached this stage of development
1
I ELEMENTARY THEORY OF NUMBERS
in another way? Have you ever noticed the remarkable fact that, of the
consecutive integers 8 and 9, one is a perfect cube and the other a perfect
square? Surely you have not overlooked the familiar right triangle
whose sides have the lengths 3, 4, and 5. Again, the sum of the positive
divisors of 6 is double having this
itself. Can you find another integer
property? Although for its size 6 has many divisors, you notice that
5 has but ± 1 and ± 5. Observe how close the first few integers of the
latter type are. Would you be interested in examining the law indicated
by the following equations?
3 = 1 + 1 + 1 4 = 1+3
5=1+1+3 6=1+5=3+3
7=1+1+5=1+3+3 8=1+7=3+5
9 = 1 + 1+7 = 1+3 + 5 10 = 3 + 7 = 5 + 5
Perhaps these few examples will stimulate the reader to look for some
other significant facts. Having made a discovery, he certainly will want
* F. Cajori, "A History of Mathematics."
THE FUNDAMENTAL LAWS 6
in that order, the sum of a and b exists and is a unique integer c. Thus
a + b = c.
3. The commutative law for addition: a b = b a. + +
4. The associative law for addition (a + b) : c = a + (6 + c) + .
The second postulate tells us that the operation of addition exists for
the rational integers. Moreover, since +1 is in the set, we can generate
a subset of integers by merely adding +
1 to itself and to each result so
and b, in that order, the product of a and b exists and is a uniquely deter-
mined integer c. Thus a b = c, or ab = c.
•
according to the relation "less than" and then separated into any two
parts without disturbing the array, there is a first integer in one part and
a last integer in the other.
13. Any sequence of integers rii, where i = 1, 2, 3, such that . . .
,
b + X = (c + a) + Oi
= c + (a + Oi)
= c +a
= b
This integer Oi is unique, for if there were a second integer O2 such that
b + 2 any b, then 2 + Oi = 2 and Oi + 2 = Oi. But Oi +
= b for
2 = 2 + Oi, and therefore Oi = 2 There is, then, but a single integer, .
Suppose that subtraction is not unique and that when a and c are given,
both b\ and 6 2 are such that
a + 6i = c = a + 62
Since
a + — a) ( = ( — a) + a =
and since
(-a) + (a + 6i) = (-a) + (a + 6 2)
it follows that
[(-a) + a] + 6i = [(-a) + a] + 62
and that
+ 6i = + b2
Hence,
&i = 6
tive two. Moreover, each of these negative integers is less than zero, for
( — a) + a = 0, where a is positive. For the same reason, — ( — a) = a.
This means that a is the inverse with respect to addition of —a; that is, a
is the negative of negative a. This statement implies that the positive
integers are the negatives of the negative integers. To summarize, we
have proved that:
Theorem 1-1. There is a unique integer such that, for any integer 6,
b + = b.
EXERCISES
;
Theorem 1-8. If b divides a, and b divides c, then b divides a + c.
Theorem 1-9. If 6 divides a, and b does not divide c, then b does not
divide a + c.
Since 6 |
a, then a = bd and a + c = 6c? + c. If 6 did divide a + c,
is, if it exists, a common divisor of the set that is divisible by every com-
mon divisor of the set.* We notice then that if -\-d is a greatest common
divisor of a set of integers, so is — d. It is conventional, however, to
refer to the one of the two integers -\-d and — d that is positive as the
greatest common divisor. It is evident, too, that the greatest common
divisor of a set of integers is unchanged if any a -
t of the set is replaced by
— cti. The symbol d = (a h a2 , . . . , a r) is used to denote that d is the
greatest common divisor of the set a\, 0,2, , . . , ar ; for example, 3 =
(6, 12, -15), and 12 = (36,48).
A common multiple of two or more integers is an integer that is divisible
by each of the given integers.
A least common multiple of two or more integers is, if it exists, a common
multiple that is a divisor of every common multiple of the given integers.
It is evident that ifa ^ is a least common multiple of a set of integers,
then —a is also. Again, it is usual in this case to refer to the positive
integer that fits the definition as the least common multiple. The least
common multiple is unchanged if any of the given integers az -
is replaced
by — di. The least common multiple of 6, —15, and 9 is 90.
* This definition and that of a least common multiple are so worded that they will
apply equally well in a domain of algebraic integers where we cannot say of two dis-
tinct integers that one must be less than the other. For instance, the set of algebraic
integers of the form a + bi with a and b rational integers is not ordered by the relation
"less than."
THE FUNDAMENTAL LAWS 9
littlewith this branch of the subject and but one theorem in the theory of
numbers bears his name. This theorem is, however, a basic one.
We shall assume the principle of Archimedes extended to include the
rational integers. This principle states that any integer a either is a
multiple of an integer b ^ or lies between two consecutive multiples of
b; that is, corresponding to each pair of integers a and 6^0, there exists
an integer m such that, for b > 0,
and hence an integer d divides a and b if and only if d divides both r and
b. For example, to find out whether or not 152 is prime to 21, just divide
152 by 21, getting the remainder 5. Since (5, 21) = 1, then (152, 21) = 1.
Theorem 1-16. All integers take the form 2n or 2n + 1.
According to the theorem of Euclid, any integer a can be expressed in
the form
a = 2n + r < r < 2
so that r is either or 1.
EXERCISES
The product of any two consecutive integers can be written in the form n(n + 1).
But then, according to the theorem of Euclid, n has the form 2k or 2k 1, whence +
the product has the form 2k(2k + 1) or (2k + l)(2k + 2) = 2 (2k + 1)(& + 1). In
either case the product has the factor 2. /
2. Show that the sum of an integer and its square is even.
for n > 0.
1J _o.
1 + 3 +
k(k + 1) _ k(k + l)(fc +2)
• • •
+
,
^
6
( }
where the right-hand member of the equation is the sum of the first k terms of the
series obtained from the formula for the sum of n terms.
We must now show by a general method that the sum of the first k + 1 terms of
the series can be correctly obtained from the sum formula. To accomplish this end,
we shall build up the series of k + 1 terms by adding the (k + l)st term to the indi-
cated sum of the first A; terms. The (k + l)st term is obtained from the term formula
THE FUNDAMENTAL LAWS 11
one member of Eq. (1), we must add it to the other member also to maintain an
equality. Thus we have
1+3+-..+ k(k 2+
,,,, ,
l)
+
(k + l)(k+2)
2
= k(k + l)(k+2)
6 + ,
(k + l)(k+2)
2 m
(2)
But the right-hand member of Eq. (2) can be factored and simplified, giving
(t
6 2
Assuming that the law is correct in the fcth case, (k + 1) (k + 2) + 3) /6 is the correct (A;
sum of the first k + 1 terms. Consequently, unless the sum formula gives this result
for the sum of k + 1 terms, the sum formula is in error. Substituting + 1 for n in fe
the formula n(n + l)(n + 2)/6, we find that it also gives + l)(fc + 2) + 3)/6. (fc (A;
We must conclude that this formula gave the correct result for n = 1,
is correct, for it
and, upon the assumption of its truth for n = k, we found it gave the correct result
for n = ft + 1. Hence, being true for n = 1, it is true for n = 2, 3, . . . .
15. Prove that the cube of any integer is equal to the difference of the squares of
two integers.
To solve a problem of this type, we often set up a few examples with the purpose of
12 ELEMENTARY THEORY OF NUMBERS
The sequence of integers 1, 3, 6, 10, reminds us of the sum of the series 1+2 . . .
+ •
+ n = n(n + l)/2. Hence, we should like to show that n 3 is the difference
• •
V n(n + 1) 1
2
_ (n - l)rc T n 2 (n 2 + 2^i + 1 - n2 + 2w - i;
f
19. Show that the square of an integer that is not a multiple of 2 or 3 is of the form
24A; + 1.
20. Prove that the sum of the odd integers from 1 through In — 1 is a perfect
square, n 2 .
21. Prove that every odd cube, n 3 is the sum of n consecutive odd integers. Find ,
If a < —cb, let m = —c — 1, but if a = —cb, then a < (— c + 1)6 and m = —c.
Let the student complete the proof.
23. If a ^ and |6| > \a\, then 6 does not divide a.
24. What values can you assign to r in order that 4n + r include all odd primes?
26. Using the idea of Exercise 24, write another set of expressions whose values
include all odd primes.
26. If n is a positive integer, the triangular numbers are given by the formula
n(n + l)/2. Find by trial some integers that are both square and triangular.
THE FUNDAMENTAL LAWS 13
27. Is the set of even integers closed under the operation of addition? Do the odd
integers have this property? Is the set of even integers closed under multiplication?
What important property that pertains to multiplication does the set of even integers
lack?
28. Peano stated the following postulates, together with the principle of finite
induction, to define the natural numbers
a. There is a number 1.
d. If n + = m + then n = m.
,
Define addition and multiplication, and derive the commutative, associative, and
distributive laws for the natural numbers on the basis of these postulates.
CHAPTER 2
The Form ax
2-1. by. +
A polynomial in the variables Xi, x 2 xT , . . . ,
in these variables; that is, each term of the polynomial is of the same
degree. The degree of a form is the degree in all its variables of any term
of the form. The polynomial Sx 2 y + 5xy 2 — y z is a form of the third
degree. All the forms with which we shall be concerned will have
integers as coefficients. We shall make use of the form ax + by to show
that the greatest common divisor of two rational integers (not both zero)
exists and is a rational integer.
Theorem 2-1. The least positive integer in the set of integers defined
by ax + by, where a and b are not both zero, is the greatest common
divisor of the set.
Consider the set of integers defined by the linear form ax by when +
a and b are constants and x and y are variables whose values are all the
integers. Since there is but a finite number of integers between zero and
any positive integer, and since the set ax by contains a positive integer, +
this set has a least positive integer. Let it be represented by
L = ax + by
This integer L divides every integer of the set because, according to the
This technical use of the word "form" is not to be confused with the ordinary
*
sense in which we have made use of the term. When we say, for instance, that an
integer has the form Qk + 1, the word is synonymous with "mold" or "structure"
and in this case designates that the given integer is always a multiple of six, plus one.
Whenever "form " is used to mean a homogeneous polynomial, the implication will be
clear from the text.
14
THE LINEAR DIOPHANTINE EQUATION 15
n = mh + r < r <L
Hence,
ax\ + byi = m(ax + by ) + r
and
a(zi — mxo) + 6(?/i - m?/ ) = r
The least positive integer of the set thus divides every integer of the set
and is necessarily a common divisor of the set. But L is in the set, and
therefore any common divisor of the set divides L. Hence, L is the
greatest common divisor of the set ax + by, for it satisfies the stated
definitionby being a positive integer which is a common divisor of the
setand which is divisible by every common divisor of the set.
Theorem 2-2. The greatest common divisor of a and b, where not
both are zero, exists and is the least positive integer in the set defined by
ax -f- by.
The and b are determined by the form ax + by, when x = 1,
integers a
y = 0, and when x = 0, y = 1, respectively. Hence, Theorem 2-1 shows
that L is a common divisor of a and b. But L = ax + by and thus srny ,
It follows, then, that the greatest common divisor of a and b is the least
positive integer in the set ax + by and that d = (a, b) can be expressed
as a linear function of a and b with integral coefficients. Thus 4 =
(12, 20) can be written 4 = 12(2) + 20(-l) = 12(-18) + 20(11).
The fact that the greatest common divisor of any two rational integers
a and b, where not both are zero, can be written in the form ax + by with
x and y rational integers is an important characteristic of the set of
16 ELEMENTARY THEORY OF NUMBERS
EXERCISES
was the one Greek mathematician of note who devoted himself to algebra.
He solved quadratic equations in a single variable, but he found only one
answer and discarded all but positive rational numbers as solutions. He
even considered types of quadratics in two unknowns and two simul-
taneous equations of this kind. He is credited with enlarging the concept
of number to include the fractions. Because he sometimes restricted his
solutions to integers, his name is now attached to the kind of equation
defined below. Diophantus developed no general method for the solution
of these equations, however. It was not until the Hindus attacked the
problem that such general methods were devised.
A Diophantine equation is a rational integral algebraic equation in
which the coefficients of the variables and the absolute term are integers
and of which the solutions, or values of the variable or variables that
THE LINEAR DIOPHANTINE EQUATION 17
y = z/i. Then
b(mxi + ayi) = b
and
mbxi + abyi = b
But m |
mb, and m\ ab. Therefore, m \
b.
Observe that Theorem 2-7 holds even when m — 0, for then if (m, a) =
1, it is necessary that a = +1. But m \
ab implies that ab = 0. Con-
sequently, 6 = 0, and m\b.
Notice also that if m ^ + 1 is prime to an integer n, then m does not
divide n. On the other hand, if m does not divide n, the integers m and n
need not be relatively prime; for example, 6 \ 15, but (6, 15) = 3.
Corollary 1. If m is prime to both a and b, then m is prime to ab.
Corollary 2. If m is prime to a h a 2 , a^, then m is prime to their , . . .
product.
EXERCISES
ai^i + a 2£ 2 + * * "
+ «nX„ = d
where the Xi, for i — 1,2, . . . , n, are integers.
Let us start with the integers oi, a 2 and a 3 and let d\
, ,
= (a h a 2 ). Then
?/i and 2/ 2 exist so that
aiyi + CL2V2 = di
diZi + a 32 2 = d2
we have
(«i2/i + a 2 y 2 )zi + a 3z 2 = d2
and finally
diXx + a 2£ 2 + a 3£ 3 = d2
Using induction, we can similarly raise the number of the integers in the
set to n.
Furthermore, as in Theorem 2-6, we can now show that when d =
(oi, a2 a n ) and d m, there exist integers x'i7 where i = 1,2,
, . . . , \
. . .
,
then the greatest common divisor of d\, a 2 , . a,k, a*+i is the greatest . . ,
If a |
n, so that n — n a, let y = and x = n , and the equation is
satisfied.
If a Jf n, then a 5* ±1 and we may suppose that 1 < \a\ < \b\. Then
and
w = #20 + 7*2 < r2 < |a|
Therefore,
ax + (oia + ri)i/ = q 2a + r2
and .
we have
ny = q*ri + r4 - (gs^i + r )« 3
and, as above,
r 3z + riw = r4
If we continue in this manner, we find that \a\ > r\ > r > > 3
and
14t/ + (14 + 9)2 = 10
so that
9z + Uw = 10
Again,
9z + (9 + S)w = 9 + 1
and
bw + 9v = 1
Therefore,
bw + (5 + 4)t> = 1
and
4^ + 5s = 1
Finally,
4z; + (4 + 1)« = 1
so that
a^ j s = i
l/ 1
x = 124 + 37k
y = 4 - 23/c
THE LINEAR DIOPHANTINE EQUATION 21
If we wish only the positive integers that satisfy the given equation,
we take
124 + 37/c >
and
4 - 23/c >
so that
4 -v L v _ 124
Hence, k can have only the values —3, —2, —1, and 0.
EXERCISES
Solve the equations and determine the number of solutions for which both x and
y are positive.
1. 16x + 7y = 601. 2. Ux - 45y = 11.
If (ai, a 2 a 3)
,
= d, there is no solution unless d \
m. Supposing that d m, \
to find the solutions we should first divide each member of the equation
by d. Therefore, let us assume that (a h a 2 a 3 ) = , 1. Then if d\ =
(a h a 2 ), it is necessary and sufficient that d\ divide a z z — m in order that
there be a solution of the given equation. But (a 3 , di) = 1, and therefore
atf + dit = m
has the solutions z = 2 — diw, t = t + a z w, where z = z , t = to is one
* H. J. S. Smith, "Collected Mathematics Papers," Vol. 1, Oxford University Press,
New York, 1894.
22 ELEMENTARY THEORY OF NUMBERS
x = biu +bv 2
(2)
y = c\U +cv 2
= c 2x - b 2y
u
bic 2 — b 2 c\
= biy — Cix
bic 2 — b 2 Ci
Therefore, any choice of integral values for 61, b 2 , Ci, c 2 that makes
bic 2 — b 2 Ci = 1
will force u and v to be integers since x and y have only integral values.
Applying this transformation (2) to the original equation (1), and sub-
stituting z = z — diw, the resulting equation is
aib 2 + a>iC 2 =
Since (a,i, a 2) = di, let a\ = doidi, a2 = aoarfi, and then
dQidib 2 = —a 02 dic 2
or
«01?>2 = —CLo 2 C 2
and
u = to + a>zw
which is the same as the value found for t. Then by eliminating u from
Eqs. (2) for x and y, we find that the solutions of the original equation are
of the form
x = bit — a 02 v + dzbiw
y = crfo + a 01 v + a ciw3
z = 20 — diw
where v and w are the parameters. That all these values of x, y, and z
determined by integral values of the parameters satisfy the equation is
easily verified.
It is evident that the solution of a Diophantine equation in four
variables can now be made
depend upon the solution of one with three
to
variables in the we have used equations in two variables
same manner as
in the above development to solve an equation in three variables.
Example. Solve: Qx + 24?/ - 41z = 91.
Solution. (6, 24) = 6, and —Alz + Qt = 91 has the solutions z =
bix +by+bz = 2 3 ra 2
If (ai, a2 ,
CJ3) = di does not divide mi
d 2 fails to divide
or if (61, 62, &s) =
m 2, there is, of course, no solution for the set. But even when these con-
ditions are fulfilled, there need not be a common solution. Take, for
instance, the set
2x + Sy +z= 7
2x - y + 3z = 8
4y - 2s = -
Any y and z that, together with an x, satisfy the given set must satisfy this
equation, but because (4, 2) = 2, the equation has no solution whatever.
When each individual equation has a solution, we can always determine
24 ELEMENTARY THEORY OF NUMBERS
the common solutions, if they exist, by solving one equation and sub-
stituting these values in the second. Thus, when the solutions of the
equation
aix + a 2y + a 3z = mi (5)
are
x — ri + SiV + t\W
y = r2 + s 2v + t2 w (6)
z = r3 + s 3^
Aw + Bv = C
The given equations have a common solution ifand only if this last equa-
tion is solvable. Suppose the solutions exist and are of the form
w = Wo -\- Bit
v = v + Ait
When these values are substituted in the solutions (6) of the first equation
(5), the common solutions of (4) take the form
x = X + Kit
y = Y +K 2t
z = Z + K^
where there is but one parameter t.
EXERCISES
7. A room has 100 seats. How many men, women, and children should be admitted
to realize exactly $10 if the men will pay 50 cents each; the women, 20 cents each; and
the children, 1 cent each?
8. If 100 pieces of money in denominations of 50 cents, $5, and $10 are to amount to
$100, how many of each denomination must there be?
CHAPTER 3
PROPERTIES OF INTEGERS
3-1. The Composite. Perhaps one of the facts with which you are
most familiar is that a composite has a prime factor, but have you ever
proved it?
Theorem 3-1. Every composite has a prime factor.
Because any negative integer can be expressed as the product of its
positive associate and the unit — 1, we shall assume that the composite m
is positive. Since m is neither a unit nor a prime, it has a factor that is
not a unit or an associate of m. Therefore, let m = /i/ 2 where both ,
posite, it, in turn, has a factor other than an associate or a unit. Then
/i = fzfA, where < /3 < /i. If /3 is not a prime, the line of reasoning
continues in the above manner, but only for a finite number of steps, for
since
m > /i > / > 3 • •
>
we must arrive at a positive factor f<m-\ that is divisible only by its asso-
ciates and theunits. The integer 2n -i is, therefore, a prime, and by sub-
stitution it is obviously shown to be a factor of m.
3-2. The Sieve of Eratosthenes (c. 230 B.C.). It is evident that one
way to test whether or not a positive integer m is a prime would be to
write all the integers from 1 through m; then to leave 2, and strike out
every second integer thereafter; next to leave 3, and strike out every third
integer thereafter; generally, to leave the next unstruck integer p, and
strike out every pth integer thereafter. Each integer except 1 that is not
crossed off by For how long must this
this process is obviously a prime.
process be continued before we know that m is a prime? Eratosthenes
answered this question by means of the following theorem and thus
presented a useful test for a prime:
Theorem 3-2. A positive integer m is prime if it has no positive prime
factor less than or equal to /, where I is the greatest integer such that I 2
is less than or equal to m.
Suppose that m is not a prime but is a composite. Then m has a prime
factor. This prime factor p must be greater than / according to the
25
26 ELEMENTARY THEORY OF NUMBERS
N = (2 •
3 • 5 p) + 1
tive prime factor. This factor is not one of the primes in the set 2, 3,
5, . . .
, p, or according to the distributive law it would divide 1, which is
shown that when we assume the number of primes is finite, we can always
find a positive prime that was not previously counted, the number of
primes is infinite.
N = (4 •
3 • 7 p) - 1
factor of the form An — I, for the complementary factor must also be odd,
and the product
(4s + 1)(4« + 1) = 4/c + 1
(4s + l)(At - 1) = Ak - 1
EXERCISES
1. Show that all primes except ±2, ±3 are represented by the forms 6n — 1 and
6n + 1.
a < and b < p. We shall prove that the prime p does not divide ab
p,
by assuming the contrary and showing that we arrive at an impossibility.
According to the principle of Archimedes there exists a positive integer k
such that for a > 1
< p — ka < a
and
< (p - ka)b < ab
But if p divides ab, then p divides pb — kab and this positive integer is a
smaller multiple of b than is ab. This argument leads to the conclusion
that there is always a positive multiple of b that is divisible by p and is at
the same time smaller than the one last found. Accordingly there would
be an infinite number of multiples of b between b and ab. The result is,
of course, impossible, and consequently p Jf ab.
Suppose now that not both a and b are less than p. Then
a = mip + ri
b = mp 2 + r2 < ri, r2 < p
PROPERTIES OF INTEGERS 29
Thus
ab = Kp + rir 2
and if p \
ab, it follows that and r 2 are positive and p |
nr 2 where both , r\
Theorem 3-7. If p is a prime and p does not divide a where i = 1,2, t-,
m > mi > m 2 > > 0, we need carry out this process only a finite
• • •
P1P2 • • •
pn = qiq2 '
qr
Therefore, p\ divides the product qiq 2 qr and must divide one of the
• * *
finally have
Pr+l * • '
Pn = 1
n
p r *, where the factorization is unique except for the use of an associate
in the place of any prime and the order of the factors.
The reader may well remember that an algebraic factorization of an
expression shows factors of all integers represented by the expression, and
30 ELEMENTARY THEORY OF NUMBERS
EXERCISES
3. Show that an integer can be represented as a difference of two squares if and only
if it is of the form 2n + 1 or 4n. Show also that the representation is unique when
the integer is a prime.
4. Find the positive integers x that make x(x + 42) a perfect square.
5. Find the positive integers x that make x(x + 84) a perfect square.
either or both integers are negative, the greatest common divisor is the
same as it is for the positive associates. Taking both a and b positive,
therefore, with a > b, we shall set up the Euclidean algorithm for finding
the greatest common divisor of a and b.
Applying the theorem of Euclid, we have
ri = m r2 + r3 3 < r3 < r 2
rk |
In like manner because r k divides r k -i and
r k -2 since it divides r&_i.
rfc-2, it must divide r _ 3 Using the steps of the algorithm in reverse
fc .
n = N a x +Nb 2
en = n vr^
3 =1
the exponents being positive integers or zero, the greatest common divisor
r
s
of the di is ] [ pj >, where each Sj is the smallest exponent that occurs for
3 =1
Pj in the factorizations of the a;.
573 = 291 + 282, 291 = 282 + 9, 282 = (31) (9) + 3, 9 = (3) (3)
EXERCISES
6.Prove that the number of divisions required to find the greatest common divisor
of two positive integers written in the scale of 10 by means of the Euclidean algorithm
does not exceed five times the number of digits in the smaller integer.
EXERCISES
1. If d = (a, b), where a and b are positive, show that ab is equal to the product of
d and the least common multiple of a and b.
2. Show that if 2 is the highest power of 2 that
k is a factor of an integer of the set 1,
k
then that integer of the set that a multiple of 2 is 2 itself and is the
fc
2, 3, . . . , n, is
Pi - 1 P2 — 1 Pr - 1
r
If m = ] J Pi
ai
, it is evident that each divisor of m which is also a divisor
i = l
1 + Pi + Pi
2
+ • • •
+ Pi
ai
(1)
Moreover, only these terms are divisors of both m and pi ai . In like man-
ner the terms of
1 + P2 + P2
2
+ ' ' • + P2"> (2)
1 + Pi + Pi
2
+ ' • '
+ Pi"
1
+ Vi + P1P2 + Pi
2
2>2 + '••• +
P2 + +
ai ai a*
Pi ' ' *
Pi p2
and it has («i + l)(a 2 + 1) terms.
Continuing the reasoning in this manner, we see that the terms of the
expansion of the product
(1 + Pi + • ' • + Pl 0(l
tt
+ P2 + ' ' ' + P2«
2
) * * '
= \\ +P + + Pf) = J! g
<r(m)
i = 1
(1 t .
• • •;
t -1
^~T
EXERCISES
r
i=l
p.»(«i+D - i
n P<
n - 1
i =l
smaller than 2 5 .
than 2 2 n 3-i3»H-i and both have n divisors. Consider the cases in which n 2 = n%, in
ri
7. Find by trial positive integers n such that the sum of the divisors of n is a
perfect square.
Find all primes that are one less than a perfect square. Is there a prime that
8.
is one than a perfect cube? Can you find a prime that is one less than n 4 ? Prove
less
a general statement to cover these results.
9. Find by trial positive integers n such that the sum of the divisors of n is a
multiple of n.
Prove that a positive integer is the sum of consecutive positive integers if and
10.
only not a power of 2.
if it is
11. Prove that the number of divisors of a positive integer is odd or even according
as the integer is or is not a square.
36 ELEMENTARY THEORY OF NUMBERS
12. Prove that the product of the divisors of a positive integer n is n 8/2 where
, s is
the number of divisors of n.
13. Prove that if r is the number of distinct prime factors of n > 0, the number of
ways inwhich n can be factored into two relatively prime factors is 2 r_1 .
(1 + 2 + • • •
+ 2^- 1 )(l + 2P - 1) = 2^(2^ - 1)
q + s = 2 k+l n
is Sn is 120. Fermat found the second one, which is 672. The third is
523,776. The first integer the sum of whose divisors is four times itself
is 30,240. Recently some new multiply perfect numbers have been
discovered. §
Two integers are said to be amicable if their sum is the sum of the
divisors of each one. The numbers is 220 and
smallest pair of amicable
284. Another pair, 17,296 and 18,416, was found by Fermat.
3-10. Scales of Notation. Have you thought of 5347 in the form of
the polynomial 5x z + Sx 2 + 4x + 7, where x = 10?
Theorem 3-14. Any positive integer m can be written uniquely in the
~l
form m = a r
n
+ a\r n + • • •
+ a n where r > 1 and the coefficients
,
m = qir -\- an
qi = qtf + a n _i
ft = ft fir + a n -i
fti-l = ft^r + Ol
?n = a
qn - 2 = a r2 + a±r + a2
-1
m = a rn + a xrn + • •
+ a„ vl'^
n > s, 6 = «n- s ,
and then
_ s _! =
aorn + . . .
+ (ln _s _ i Q
Since r > 0, the remaining coefficients must all be and the representa-
tion is unique.
on the basis of this theorem that we know we can write an integer
It is
in justone way in the Hindu- Arabic system, which uses the scale of 10
and the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The integer 363 in the
ordinary scale becomes 2423 in the scale of 5, while it is 101,101,011 in the
scale of 2.
Corollary. Any positive integer n can be expressed in one and only
one way as a sum of distinct powers of 2.
We can apply this corollary to show that for weighing approximately
any load not exceeding 127 lb but seven weights of 1, 2, 4, 8, 16,32, and 64 lb
each are needed for the scales, for 127 is written 1,111,111 in the scale of 2.
PROPERTIES OF INTEGERS 39
1 237
2 474
4 948
8 1896
16 3792
32 7584
Then all that was necessary was to find the sum, 237 + 948 + 1896 +
7584 = 10,665.
They carried out division in a similar manner. If 539 was to be divided
by 41, they used the process of doubling on the divisor until they could
find suitable multiples of it which, when added, would give a result smaller
than 539 but less than 41 units from it. Their work might be indicated
as follows:
1 41
2 82
4 164
8 328
constructed on the basis of this system, for but two digits, and 1, are
needed in each position. The mechanism is, therefore, decidedly simpler.
The calculator at the Institute for Advanced Study in Princeton is of this
type.*
EXERCISES
1. Prove that any positive integer can be expressed uniquely as a sum of distinct
powers of 3 with coefficient — 1, 0, or +1. From this representation show that a set
of five weights is sufficient to weigh any load of at most 121 lb if a balance scale having
two pans is used.
2. Set up multiplication tables for the scale of 5. Then write 42 and 352 in the
scale of 5, and find their product when they are so written. Check the answer by
converting the result to the ordinary scale of 10.
3. If 42 and 352 are in the scale of 6, find their sum and product in that scale.
remainder b — a occurs, show that half of the repeating cycle of digits has been found
and that the remainder of the cycle can be determined by finding in order the differ-
ences between 9 and the digits already established.
[[•]'
_ &
-hi
"lab]
n a
Let = a and = (3, so thaib
a T)_
and
[sl-'+N*]
However, r 2 is at most b — 1, and r± is at most a — 1, and thus ar 2 + n
isat most a(jb — 1) + a — 1 = a& — 1. Therefore,
p< s+,\
l p
Corollary 2. If n > a > and 6 > 1, then
Corollary 4. If n = wi + n2 + • •
+ n t , where the n^ for i = 1,
Letting — = a we have n; =
i; a»a + n with < n < a. Therefore,
and
= ai + a2 + * * * + OL t + •i + ;
;
•
+ n \
a J
Hence,
EJnl)
K+ [?]
+ -- + H \M-
42 ELEMENTARY THEORY OF NUMBERS
1, 2, . . .
, p, . . • , 2p, . . .
, V\ • • , n (4)
The last integer of the set that is divisible by p is p, and the coeffi-
cient of p shows that there are - multiples of p in this set. All other
Now take out one factor p from each of these multiples of p that are in
r-i
the set (4), thereby obtaining the factor pL^-l. Therefore,
«.o-[;]+*.0-> [;])
P = — o
2 P- We can, as before, ,? J from
remove the factor pLp 2
P J Lp J
the product of the integers of the new set, showing that
p
s
< n < p
s+1
, so that \
— ^ \ 0, while -^ = 0. Therefore,
n — > di
PROPERTIES OF INTEGERS 43
~l
Because n = ap s
+ aip s + + a s with < a < p and <
a,i < p for i — 1, 2, . . . , s,
n
= a p s_1 + aip s_2 + •
+ as _ 2p + a s _i
Lpj
n ~2
= a ps + ai7?
s_3
+ •
+ as_ 2
fe]-
Therefore
+ + a,_i
or
a ps + aip s
~1
+ • • •
+ a s _ip - ao --
Oi — • • •
— a 8 -i
tf,(n!) =
v- i
a ps + ' •
'
+ a s _ip + as — a - a s -i - - as
P- 1
n — (a + ai + + a.)
p- 1
= + = +
138 (27)5 3; [±|?] = 27; 27 (5)5 2;
^J = 5; 5 = (1)5
We may also use the second formula for E p (n\). Writing 138 in the
scale of 5, we have 53 + 0(5 2 ) + 2(5) + 3. Therefore J£,(138!) =
(138 - 6)/4 = 33.
t
w* - [=] + [>] + • •
+ [£] +
n n
+ 8
= (5)
Lp
44 ELEMENTARY THEORY OF NUMBERS
Since a\ + «2+ * * *
+ <H = n, if p
s+1
exceeds n, it exceeds each a*, and
therefore -^ = for i = 1, 2, . . .
, £. Hence,
--- +
*^-[|] + [p] + fe]
+ ...+[p]
*;'""; [?] + + + +
.fe] .7.'.
.;;; [r]
+ + ' '
+
L?J - L^J l_^j ' Yv
k
\
E p (n\) > E p ( ai \) + E p (a 2 \) + - - -
+ E p (a t \)
divisible by n\.
The + l)(fc + 2)
expression k(k (k + n - l)/n\ = (k + n - 1) !/ •
obtained by means of the multinomial theorem are integers, for any term
of the expansion takes the form
n \
j , bi
ai
b 2a * • ' b ra -
ai!a 2 !
•
ar \
The with d\ + a 2
expression p\/ai\a 2 ar — p, is
\
• • •
ar \, + • • •
+
an integer, and furthermore since each a,- either is positive and less than
p or is 0, there is no factor p in the denominator. Hence, (p — 1)!/
atlas! • • *
ar ! — M is an integer, and the required coefficient is Mp.
EXERCISES
3. If re is a real number and [x] is the largest integer that is less than or equal to x>
show that:
a. [(1 + \/S) n ], for n > 0, is odd or even according as n is even or odd.
b. [(1 + \/3)
2n
] +
1 is divisible by 2 n+1 for n > 0.
so that 402!, 403!, and 404! have the factor 3 197 but 405 has the factor 3 4 so that 405! , ,
has the factor 3 201 Hence, there is no n such that n\ has the factor required.
.
19
6. Find a positive integer n such that 5 is the highest power of 5 contained inn!.
7. Show that 95! ends with 22 zeros. With how many zeros does 100! end?
8. Find the highest power of 12 contained in 500!.
15. Prove that when (m, n) = 1 and m and n are positive integers,
(m +n - 1)!
m\n\
is an integer.
16. Prove that when m and n are positive integers,
(2m)!(2n)!
7n\n\(m + n)\
is an integer.
46 ELEMENTARY THEORY OF NUMBERS
17. If n = Oi + 0,2 + • • •
+ a>r with all en > and (ai, a2 , . . . , ar) = <2, then
I
d(n - 1)!
ai!a 2 ! • • • ar \
is an integer.
18. If m, n, and a are positive integers, under what conditions will
[t>[;]+*R]
19. Prove that (x - l)(x 2 - 1) • • • (z r - 1) is a factor of (x n - l)(x n+1 - l)
. . . (x»+r-i _ i) w hen n is a positive integer.
by showing that 2 32 +
1 = 4,294,967,297 has the factor 641. It has
been proved, however, that no rational function of x except a constant
can be a prime-representing function, f We shall prove the corresponding
well-known theorem about a polynomial.
Theorem 3-19. An integral polynomial of at least the first degree
cannot represent primes alone.
Suppose that, for x = x' where x' > 0, f(x) = a x n + + an ',
• • •
* W. H. Mills, Bull. Am. Math. Soc, Vol. 53, No. 6, p. 604, 1947. E. M. Wright,
Am. Math. Monthly, Vol. 58, No. 9, pp. 616-618, 1951.
t R. C. Buck, Am. Math. Monthly, Vol. 53, No. 5, p. 265, 1946.
PROPERTIES OF INTEGERS 47
n-
f(x' + mp) = a x' n + aix'
1
+ ' '
+ an + Kp
or
f{x' + Kp + mp) = p
Hence, p f{x' \
and f(x' + mp) is not a prime unless f(x' + ^p)
+ mp),
is p or —p. Suppose that, for m = 0, 1, 2, n — 1, f(x''+ mp) = . . .
,
f(x h a 2
, .,a n ) having but one variable would represent primes for all
. .
EXERCISE
~
Prove that for integral values of x an integral polynomial a x n + a\X n + l
• • •
+ a n of degree n > has an infinite number of distinct prime factors. (Assuming the
k
7r(n) = n +r— 1
Lf lPi\ Z/ IViVA
M= l
-
+ (-!)'
Pr\
1
P1P2 '
where i = 1,2, r. . . .
,
M 2
= [il
IPii
+ [ » 1 - \jl]
LP*} LP1P2J
is thenumber of integers from 1 through n that are divisible by either of
the two primes, pi and p 2
first .
Mi + +
fe] LVkj
+ [-=-1+
LP1P2P3]
LP1P2]
•••
LpiPz]
+(-««rLP1P2 —— •
-
•
iPk-iPk]
•
pk \
1 (
integers from 1 through n that are divisible by the next prime p k +i and
that are prime to all the first k primes.
The number of integers from 1 through n that are divisible by p k +\ is
n
Pk+ij
Of these integers are also divisible by pi, for if we
Pk+i Pi J
examine the set of multiples of Pk+i,
p k+h 2p*+i, . . .
, \-^-\ Pk+i
n
[-1
lPk+i \ Pk+i.
+ Pk
.
L P1P2
"
1 n
Pk+
-1 .Pk+i.
(-D ;
[pip 2
L Pk-iPk * * "
Pk:
PROPERTIES OF INTEGERS 49
PlP2
fjLl
*
* •
Pt
r
LP1P2 • •
5 —
•
p«p*+iJ
jlI
_p k +ii
_ r_5_i
LPiPk+i]
f_=_i
IPkPk+ij
+ \^—\ +
LPiPzPk+i}
(8)
p*p*+i.
the number (7) of integers from 1 through n that are divisible by at least
one of pi, P2,
M =-+...+
Pk, we
. .find
. that
,
the
-fe]
number
-
p*J
JL -]+
PkPk+ij
•••
LP1P2J
+(-i)4
LP1P2 - -
—
-
-
PkPk+ij
fore, holds for the first r primes. But by Theorem 3-2 any positive integer
less than or equal to n and greater than p r is a prime unless it is divisible by
one of these first r primes. Hence, n — r is the number of integers M
from 1 through n that are prime to pi, p 2 and p r Consequently, , . . . , .
this number counts the integer 1 and all primes greater than p r but it ,
w(n) = n — M r +r— 1
some, but even though his method has been improved upon,* no expe-
ditious method for finding the exact number of positive primes less than
a large n has been discovered.
On the other hand, due to the work of Legendre and Gauss (1777-1855)
in applying analysis to the theory of numbers, we have formulas which
approximate the number of primes not exceeding x. Legendre stated the
empirical formula
w
F(x) =
logx -
-
1.08366
which agrees very well with t(x) so long as x is not greater than 1,000,000.
Gauss discovered "the integral logarithm of x,"
[* dt
0) =
. ,
T ,
J 2 log t
As recently as 1948 Paul Erdos and Atle Selberg developed new and more
elementary methods for showing this limit.
As a matter of fact although many theorems about primes have been
demonstrated, we can still state a large number of theories that mathe-
maticians believe to be true but which remain unproved. We have seen
that Euclid established an interval within which there must be a prime.
Again it has been proved that if p 1} p 2 Pn-i are the first n — 1
, • •
,
n\ + 2, n\ + 3, . . . , n\ + n
PROPERTIES OF CONGRUENCES
Now we separate all integers n into \m\ classes according to the remainders
r upon being divided by m. We say that two integers
that they yield
are congruent modulo m if and only if the integers produce the same least
nonnegative remainder upon being divided by m ^ 0.
Gauss (1777-1855) introduced this idea of congruence, and it was he
who suggested the notation a = 6(mod m), which is read, "a is congruent
:
to b modulo m," or "a is congruent to b for the modulus ra." The value
of this concept and its symbol is that emphasis is placed upon the impor-
tant integers in the equations
a = giw +r
and
b = q m + r
2 < r < \m\
These definitions imply that each integer belongs to exactly one residue
class for a givenmodulus and that each residue class modulo m contains
one and only one of the integers 0, 1, 2, \m\ — 1. Hence, there . . .
,
prime to m, the set of remainders from 1 through \m\ — 1 which are prime
to m represents all and only the integers that are prime to m. These
integers, prime to m, are thus separated into residue classes modulo m
that are in one-to-one correspondence with the positive integers from 1
through \m\ — 1 that are prime to m.
Any set of integers prime to m and selected so that one and only one
of them belongs to each of the residue classes of integers prime to m for
the modulus m constitutes a reduced residue system modulo m. For the
modulus 5 the set 1, 2, 3, 4 is a reduced residue system, but for the
modulus 6 the integers 1 and 5, as well as the set 1 and —1, form such a
system.
It is evident also that the residue classes for the modulus m are iden-
ticalwith the residue classes modulo — m, for when the sign of m is
Thus any congruence that holds for either m or — m as modulus holds for
the other one. It is convenient, therefore, to use only positive integers
as moduli, and we
shall hereafter adhere to this convention without
making a statement of the fact in the discussion.
specific
4-2. Basic Properties of Congruences. The relation of congruence
has some properties similar to those of equality:
1. For any modulus m, a = a(mod m).
b (mod m).
4. If ac = be (mod m) and (c, m) = d, then a = 6 (mod m ), where
m =m d.
Examples. 1. We
can find the remainder when 2 30 is divided by 17
by simple operations on congruences. Since 2 4 = 16 (mod 17) and 16 =
— l(mod 17), we have 2 4 = — l(mod 17). Raising each member of the
congruence to the seventh power, we obtain 2 28 = — l(mod 17). But
22 = and therefore 2 30 = -4(mod 17), or 2 30 = 13(mod 17).
4(mod 17),
2. We know that 10 = l(mod3). Accordingly, a (10) n + a^lO)"- + 1
• •
+ a n = a Q + ai +
•
+ a n (mod 3). Thus a number written in
• • •
the scale of 10 is divisible by 3 if and only if the sum of its digits is divisible
by 3.
EXERCISES
1. Find the remainder when 7 10 is divided by 51; when 3 10 is divided by 51; when
21 10 is divided by 51.
2. Find the remainder when 5 21 is divided by 127. Do the same for 5 66 .
56 ELEMENTARY THEORY OF NUMBERS
3. Prove that 2 U —
has the factor 23 and that 2 23 — 1 has the factor 47.
1
greatest common divisor of b and m. State this result in terms of the integers of a
residue class modulo m.
5. If a + b = c(mod m) and b = d(mod m), show that a + d = c(mod m).
7. Since 2
4
= l(mod 5) and 4 = 9 (mod 5), is 2 9 = l(mod 5)? Explain.
8. Prove that an integer is divisible by 9 if and only if the sum of its digits is divisi-
ble by 9.
9. Prove that an integer is divisible by 8 if and only if the number formed by its
10. Prove that an integer is divisible by 1 1 if and only if the sum of the digits in the
odd-numbered places diminished by the sum of the digits in the even-numbered places
is divisible by 11.
11. If an integer N is written in the scale of r and then its digits are rearranged in
any way to form the integer M, the difference N — M
is divisible by r — 1.
16 = (2 + 10fc)(3 + 100
4(mod 6); that is, the same least positive residue 2 ^ 0(mod 6) can be
multiplied by either one of the distinct least positive residues 2 and 5 to
produce a number of the class of 4 modulo 6. If we examine the least
positive residues of any prime, we find that no such thing happens when
PROPERTIES OF CONGRUENCES 57
we do not choose the first factor from the class of zero for the given prime.
To prove this statement, let p be a prime, and suppose that aci =
6(mod p) 6(mod
and ac 2 = p). Therefore, aci = ac 2 (mod p),
and since
(a, p) = 1, C\ = c 2 (mod p). Hence, C\ and c2 must come from the same
residue class modulo p.
When we select the integers a and b and ask whether or not there is an
integer x such that ax = b (mod m), it is evident that we are dealing with
a problem in division, the inverse of multiplication. We have, therefore,
shown that when we divide b by a for the modulus m, have it is possible to
results that do not belong to the same residue class for that modulus.
It may happen, of course, that all answers are in but one residue class as
is true in the case of the congruence 5x = 1 (mod 6) But it is also pos- .
ab = 0(mod m)
0(mod m).
We call any integers ni and n 2 neither one of which is in the class of
,
EXERCISES
1. that although 2(6) = 26 (mod 14), 26 cannot be factored into integers such
Show
that one in the class of 2 and the other in the class of 6 modulo 14.
is
2. Find numbers in the class of 10 modulo 11 that can, and some that cannot, be
expressed as a product of two integers, one from the class of 2 and the other from the
class of 5 modulo 11.
58 ELEMENTARY THEORY OF NUMBERS
2x m 6 (mod 10)
2x = 3 (mod 4)
2x a 3 (mod 5)
Sx = 6(mod 15)
integers less than or equal to \m\ and prime to m. Thus 0(m) is the
number of integers in a reduced residue system modulo m, and 4>(m) =
0( — ra). Because of this last fact, it will be sufficient to use only positive
integers m in considering the function.
Examples. 0(1) = 1, 0(5) = 4, 0(6) = 2.
r n
1, 2, . . •
, p, . . • , 2p, . . .
, p , . . .
, p
= p (p — 1) of the n~ l n~ 1
of them are divisible by p. Therefore, p — p n
if it assumes only integral values for the sets of integral values of the
1 2 3 k a
a + 1 a + 2 a + 3 a +k 2a
2a + 1 2a + 2 2a + 3 2a + k 3a
sa + k = k(mod a)
with a, every integer in that column has that divisor in common with a,
and if k is prime to a, every integer in that column is prime to a. There
are then 0(a) columns of integers that are prime to a. How many of
these integers are prime to 6?
Consider the set of b integers in any column,
k a + k 2a + k ... (b - \)a + k
sa + k = ta + /c(mod b)
(t - s)a = 0(mod b)
and
t - s = 0(mod b)
4>(m) = <t>(p^)<t>(p2
n2
) • •
HPr nr )
from which we infer the desired result.
Corollary. If m> 2, <t>(m) is even.
Example. The number of positive integers less than 360 and prime
to 360 is 0(360) = 2 2 3 (2 - 1)(3 - 1)(5 - •
1) = 96.
EXERCISES
1. Show that the formulas for the number of divisors of an integer and the sum of m
the divisors are multiplicative functions.
2. Show that, for n > 1, the sum of the positive integers less than n and prime to n
is (n/2)<f>(n).
3. Show that the sum of the squares of the positive integers less than n and prime to
n is
4. Prove that if n = p\Pip%, where the pi, with i = 1, 2, 3, are distinct primes, then
the product of all the positive integers less than n and prime to n is
(n - 1)! [] ^~ 1)1
3 3
n cp*p< - 1)!
"
[1 pi<r -l)(Pfc-l)
i =i
i<j
Use the method so developed to find the product of all positive integers less than n and
prime ton = pi ai p2 a2 Pr
ar • • • .
6. Set up a method for finding by trial all integers x such that <f>(x) = n. Use your
method to find the solutions of <j>(x) =16.
Note that the symbol > ^>(d) is read "the sum over the divisors of n of </>(d)," and
d|n
m
0-5)0-£)-"(-s)
Some of these integers, however, are divisible by pk+i. We wish, there-
fore, to subtract from the above number the number of integers from 1
through m that are divisible by pk+i and at the same time are prime to
Pi, P2, • • .
, Pk- To find this number, first consider the integers of the
set from 1 through m that are multiples of p k+i. They are
p k+h 2p k+h 3p k+ i, . . .
, —
-TYl p k +i
Vk+l
1, 2, 3,
m
' '
Pk+i
m
Vk+ A pj\ vj \ Pk)
(2)
we have
m "
\ Pi)\~pJ \ p k)
m
Pk+ii \ Pi) \ pi) \
~ Ph)
p and
k also p*+i. Thus by induction we may write this formula so that
it includes the number of integers from 1 through m that are prime to
some or all of the distinct prime factors of m.
Example. If m = 23 • 32 • 53 , the number of integers from 1 through
m that are prime to 2 and 5 is 23 •
32 •
5 3 (1 - £)(1 - -J)
= 3600.
Theorem 4-6. If the positive integer m = kd, the number of integers
n from 1 through m having the property that d is the greatest common
divisor of n and m is <f>(k).
k multiples of d in this set, but the integers id and m = kd have the great-
est common divisor d if and only if t and k are relatively prime. Since t
has the values 1, 2, . . . , k, there are exactly 0(/c) integers from 1
symbol > <j>(d) is read, "the sum over the divisors of m of <£(d)," the sum
of the numbers indicating the sizes of these classes is > tf>(d)
ar h ar 2 , . . . , ar m
then
Ti = r,-(mod ra)
Moreover, if
n, r 2 , . . . , r^m)
ar h ar 2 , . . . , ar^m)
is also a reduced residue system modulo m, for this set contains exactly
</>(ra) integers, all of which are incongruent modulo
and each integer ra,
55, is a complete residue system modulo 12, while 5, 25, 35, 55 is a reduced
residue system modulo 12.
Again if r 1} r 2 r w is a complete residue system modulo ra,
, . . . ,
a + rh a + r2, . . . , a + rm
for any a ^ is another complete residue system, for there are m integers
in the set, and if two of them were congruent modulo m, when i ^ j,
a +n= a + ry(mod m)
then
Ti = ry(mod m)
ra — r = — r(mod ra)
19 m ra ra
U, 1, A, . . . ,
ra -—1
>
m -—1 ,
ra -
— 3
j . . . —2, —1
,
64 ELEMENTARY THEORY OF NUMBERS
Examples. For the modulus 14 the set —6, —5, —4, —1,0, . . . ,
7.
k, k + d, k + 2d, . . .
, k + (& - l)d
for the modulus b, and y takes all values in a complete residue system
kh k2 , . . . , ka (4)
and a \
(fa — kj), so that
k t = kj (mod a)
Hence,
a(ri — rs ) = 0(mod ab)
and
Ti — rs = 0(mod b)
Again when (a, b) = 1, if we use the form ax + by, letting x have the
values of (3) and y have the values of (4), the resulting ab integers form a
complete residue system modulo ab, for if
It is easy to show also that if x has the values in (3) that are prime to b
while y has the values in (4) that are prime to a, then when (a, b) — 1, the
integers ax +
by form a reduced residue system modulo ab.
EXERCISES
n n
in an array of s complete residue systems modulo pi ip2 Phnk 2 .
n~ x
3. Show that a + y generates a complete residue system modulo a n if x has the
l
values in a complete residue system modulo a while y has the values in a complete
~
residue system modulo a n l .
4. If f(x) is an integral polynomial and if there are \p(m) integers prime to m in the
a. 1 •
2, 2 •
3, . . . , m(m + 1).
, 1-22-3 m(m + 1)
b -
~T' -2~' • ' ' '
2
6. For m > set up all the permutations fc at a time with repetitions allowed of the
positive integers not greater than m. Then the number of these sets of k integers
whose greatest common divisor is prime to m is 4>k{m). Find a formula for <}>k(p n ), and
show that this function is multiplicative.
7. Without using an enumeration according to size, show that if a, b, and c are
positive integers and a = be, there are in a complete residue system modulo a exactly
c integers that are divisible by b. (Let ci, c 2 c c be a complete residue system , . . . ,
8. Can you find an integer the powers of which set up a complete residue system
modulo 13? Can all integers prime to 13 be used to form such a set?
9. By expanding (1 + 1 + + l) p prove that if p is a prime, a p = a (mod p)
• • •
,
fi(x 1} x 2 ,. . . ,x n ) =f 2 (x h x 2 ,. . . ,^)(modm)
where /i and f2 are integral polynomials in these variables, and if
fi(x h x 2 ,. . . ,x n ) m f2 (x h x 2 ,. . . ,x n )(modm)
calling this congruence an identical congruence although very often we
use only the ordinary sign of congruence to express this relation. Corre-
spondingly, an integral rational algebraic function f(xi,x 2 ,. ,x n ) with . .
gruence will be satisfied regardless of the integral values that are assigned
to the variables.
On the other hand, we shall call a congruence of the above form, but in
which the left- and right-hand members /i and f 2 are not identically con-
xb — x = 0(mod 5)
x 3
+ Sx 2 + 2x = 0(mod 6)
Likewise,
2x = 4(mod 6)
and
x2 = 2(mod 5)
are conditional congruences, the first one having two incongruent solu-
x2 - (x - 2)(x + 2) = 0(mod 4)
and
Qx 2 + x - 15 m x + 3(mod 6)
EXERCISES
3. xz + x = x - z (mod
2 3 2
2). 4. 2x 3 + 3x + x = 0(mod
2
6).
5. x2 - 4 = 0(mod 5).
6. x4 - 1 = (x - l)(x - 2){x - 3)(x - 4)(mod 5).
gruent integers or other expressions that are identically congruent for the
given modulus.
2. Substituting F(x) for f(x) in a term f(x)g(x) of a congruence if F(x)
is identically congruent to f(x) for the given modulus.
3. Multiplyingor, when possible, dividing the coefficients of each
0(mod m), the degree of the congruence is defined as the degree of the term
or terms of highest degree in f(xi,x 2 ,. . . ,x n ) whose coefficient or coeffi-
THE SOLUTION OF CONGRUENCES 69
3x 2 - 5x + 7 = 0(mod 12)
gruence can be broken up into the set of congruences f(x) = 0(mod mi).
Conversely, if (ra*, my) = 1, the set of congruences f(x) = 0(mod m t ) can
be combined to form f(x) = 0(mod m). We shall say in this case that
f(x) = 0(mod m) is equivalent to the set f(x) = 0(mod m^). For
example, 5x = l(mod 12) is equivalent to the set of two congruences
5x = l(mod 3) and bx = l(mod 4). It follows that if x = £ (mod 12) is
a solution of the first congruence, then x G also satisfies the last two. Con-
versely, any simultaneous solution of the set of two congruences implies
that the original congruence has the same solution, for the moduli 3 and 4
are relatively prime, and thus when 5x — 1 is divisible by both 3 and 4,
it isdivisible by their product.
But when two congruences are themselves not equivalent, the existence
of a solution of either one of them may often be determined by showing
the existence of a solution of the other one. In that case we speak of the
problems of the existence of the solutions as being equivalent. Notice
70 ELEMENTARY THEORY OF NUMBERS
EXERCISES
axi ss ax 2 (mod m)
and
Xi = .x 2 (mod m)
THE SOLUTION OF CONGRUENCES 71
Consider this class of integers all of which are of the form Xi km and +
obviously satisfy the given congruence. We wish to know whether these
integers constitute one or more solutions modulo m; that is, we should
like to know for which values of k these integers are in the same residue
class modulo m. We see that
Xi + kmo = Xi + sm (mod m)
if and only if
m Q (k — s) = 0(mod m)
that and only if k
is, if s = 0(mod d).— Consequently, when k ranges
from through d — 1, the integers xi + kmo represent exactly d solutions
that are incongruent for the modulus m and all solutions of the given
congruence lie in one of these d classes modulo m.
Example. Solve: 15x = 12(mod 36).
Since (15, 36) = 3 and 3 12, we reduce the congruence to hx =
|
4(mod 12) of which there is one solution x = 8(mod 12). Hence, the
solutions of the original congruence are x = 8, 20, 32 (mod 36).
EXERCISES
State with reasons the number of distinct solutions of the following congruences, and
find the solutions.
then q(x) is said to be the quotient and r(x) the remainder in the division
modulo m of fi(x) by f 2 (x). When r(x) = 0(mod m) identically, the
division is said to be exact and both f 2 (x) and q(x) are factors modulo m
offi(x) or divisors modulo m oifi(x). Moreover, fi(x) is a multiple modulo
m of f 2 (x).
Notice, for example, that if we divide 2a;
2
— x — 3 by a; — 3 using
ordinary long division, we find that there is a remainder 12 which is, of
course, in the class of for the modulus 6, and therefore we say that x — 3
is a divisor modulo 6 of 2a;
2 — x — 3.
2x - 5\ \x 2 + 1 1
2x ± 2
\x 2 - lOx
lOz + 1 = 4x + l(mod 6)
4x - 10
11 = 5(mod 6)
2x - 5[ 4x 2 + x + 1 1
2x
4x 2 - 10a;
But 2y = 5 (mod 6) has no solution, and the best we can do is to write the
identical congruence 4a;
2
+ x + 1 = (2x — 5)(2x) + 5x + l(mod 6).
However, if we change the form of the above divisor using —4a; — 5
instead of 2a; — 5, we have
THE SOLUTION OF CONGRUENCES 73
— 4x — 5| 4a;
2
+ x + 1 \-x + l
4a;
2
+ 5a;
- 4x + 1
— 4a; — 5
6 == 0(mod 6)
Hence, 4a;
2
+ +a; 1 = (-4x - 5)(-x + l)(mod 6).
We could obtain a like result by first adding Qx 2 to 4a; 2 +x+ 1 , for we
find that
2a - 5 [
10z 2 + x .+ 1 |
5s + 1
10x 2 - 25a;
by 3a;
2 — 1, getting three distinct quotients and three distinct remainders,
for
3a;
3
+ 1 = (3a;
2
- l)(x) + x + l(mod 6)
3a;
3
+ 1 = (3a;
2
- l)(3a;) + 3a; + l(mod 6)
and
3a;
3
+ 1 = (3a;
2
- l)(5x) + 5x + l(mod 6)
When the modulus is a prime and the polynomials are not constants, it
iseasy to show that the division modulo p of fi(x) by fz(x) can always be
accomplished, for any term present in either one of these polynomials has
a coefficient that is prime to the modulus and the congruence ay =
6(mod p) has exactly one solution when (a,p) = 1. The remainder r(x)
will, therefore, be congruent either to zero modulo p or to an expression
that is at least one degree lower than the degree of the divisor. In this
case, moreover, both q(x) and r(x) are unique, for if
If q\{x) — q 2 (x) f£ 0(mod p), let its leading coefficient be b ?£ 0(mod p),
and the leading coefficient of f 2 (x) be a ^ 0(mod p).
let Then the lead-
ing coefficient of f2 (x)[qi(x) — q 2 (x)] is a 6o ^ 0(mod p), and the degree
of this expression is at least that of f2 (x), thereby exceeding the degree of
r 2 (x) — ri(x). This is impossible, and we infer that qi(x) = q-ii-v) (mod p)
identically and likewise that 7*1(0;) = r 2 (o;)(mod p).
74 ELEMENTARY THEORY OF NUMBERS
EXERCISES
2.Divide x 2 - 2x + 5 by 2x - 3 modulo 7.
3.Divide 3x 2 - 2x + 4 by 2x - 1 modulo 15.
4. Divide x 3 - 2x + 5x - 1 by 2x - 3 modulo 11.
2
are integral polynomials with t < n, and if (b m) = 1, do polynomials g(x) and r(x) ,
exist so that /(a:) h= g(x)q(x) +r(a;)(mod m) with r{x) lower in degree than g{x)l
If so, are these polynomials unique modulo m?
with a ^ 0(mod m), then x — r is a factor of /(#) for the modulus m, and
conversely.
According to the remainder theorem of algebra, f(r) is the remainder
when f(x) is divided by x — r. Consequently,
be an integer. In like manner the fact that 6 -_i and bi — r6 -_i, where t t
f( x ) ~ f( r) = (x — r)q(x) (mod m)
and so
f(x) = (x — r)q(x)(mod m)
f(x) = (x — r)g(a:)(mod m)
then
f(r) = 0(mod m)
and x = r(mod m) is a solution oi fix) = 0(mod m).
THE SOLUTION OF CONGRUENCES 75
theorem brings out the fact that when ri, r 2 r s are incongruent , . . . ,
integers modulo p that satisfy /(#) = 0(mod p), the product (x — ri)(x —
r 2) •
(x — r s ) is a factor modulo p of f(x)
• *
.
f(x) = (x — ri)
ni
gi(x)(mod p)
/(r 2 ) = (r 2 - ri)
ni
gi(r 2 )(mod p)
But since /(r 2 ) = 0(mod p) and rx ^ r 2 (mod p), it is evident that gi(r 2 ) =
0(mod p) and, as above,
qi(x) = (x — r 2 ) m q2(x)(mod p)
76 ELEMENTARY THEORY OF NUMBERS
so that
f(x) = (x — ri)
ni
(x — r 2 ) n2 g 2 (V)(mod p)
identically.
If f(x) = O(mod
p) has one or more other distinct solutions for the
modulus we continue in this manner until either all the solutions which
p,
are fewer than n in number have been found or we have at most n linear
factors modulo p of f(x). In the latter case we find the identical
congruence
f(x) = a (x — ri)
rtl
(x - r 2 ) n2 • • •
(x — r k ) nk (mod p) (1)
where n\ +n + 2 •
+
n k = n, and hence there are n solutions, for a
solution of multiplicity where i = 1, 2, k, is counted ni times.
rii, . . . ,
/(«) = a Q (s - r^is - r 2 ) n2 • •
(s - r k ) n *(mod p) (2)
— u~v —
But if the leading coefficient of the expansion of (x ri) qi(x) qi(x)
is not congruent to zero modulo p, the leading coefficient of the last con-
gruence written in the expanded form cannot be congruent to zero modulo
p. The congruence states, however, that when it is written in the form
~
a xn +
aix n l + +
a n ss 0(mod p), all its coefficients are multiples
• • •
— w- y =
(x ri) giO) q 2 (x)(mod p)
- w- y =
(ri ri) gi(ri) # 2 (ri)(mod p)
THE SOLUTION OF CONGRUENCES 77
f(x) =
If /(a)
/(a)
=
+ (x-
0(mod p),/'(a)
a)f(a)
=
+ (x
O(modp),
- a) 2
^ . . .
+..-+.(*-
, and/^a) =
a)»
O(modp),
-^
f
and
/(x) = Or — a) r Q(x)(mod p)
78 ELEMENTARY THEORY OF NUMBERS
polynomial has been factored into two polynomials, this rule enables us
to set up an identity between two forms of f'(x), for if
f(x) = a Qx n + ciiX"-
1 +-••• + a* = (b Q x
r
+ • • •
+ b r )(c xs
+ ' • ' +C 8)
then
+ kXcowr- 1
+ • •
•"
+ c _i) + (b rx ~ +
8 Q
r l
• • •
+ & r_i)(co^
+ * •
+ c.)
Consequently, if f(x) = (x —
a) r q(x) (mod p), then the formula verifies
the statement that f (k) (a) = 0(mod p) for k < r, because clearly each
d s (x — a) r /dx s has a factor x — a when s < r. But (x — a) r+l is not a
factor modulo p of f(x), and so we infer from q(a) ^ 0(mod p) and
^ [(X
~dx^
X)]
= ( * ~ a ^ ^+ ir)
' ' '
+ r ( r!)(
^ ~ a WW + ( r!) ^W
that/ (r) (a) ^ 0(mod p).
To make it plain that the restriction which Theorem 5-7 places on the
degree of f(x) = 0(mod p) is a necessary one, consider the congruence '
10 —
a; x b = 0(mod 5). Its only solutions are x = 0(mod 5) of multi-
plicity 5and the simple solution x = l(mod 5). Nevertheless, f (k) (0)
and f (l) are congruent to modulo 5 for all positive values of k.
(k)
/
THE SOLUTION OF CONGRUENCES 79
~x
*Theorem 5-8. If r satisfies the congruence a Q x n + a\X n + • • •
+
a n = 0(mod m), then r is a factor modulo m of a n .
x such that
x = ai(mod mi)
x = a 2 (mod mi)
x = a n (mod mn )
n
In each case (M{, mi) = 1, and there is exactly one solution x = .x\(mod m z)
manner the integers in the residue class of X modulo M satisfy all the
given congruences.
But this class of integers is the only simultaneous solution of the set of
congruences, for if there were a second solution Xi, the substitution of X
and Xi in the given congruences (3) shows that
X= Xi(mod m,-)
X= Xi(mod M)
M = 385 x = 77M M* = 55 3 = 35 M
77x = l(mod 5) or 2x = l(mod 5) has the solution x = 3 (mod 5)
55a: = l(mod 7) or Qx = l(mod 7) has the solution x = 6 (mod 7)
S5x = l(mod 11) or 2x = l(mod 11) has the solution x = 6 (mod 11)
Hence, X= (77) (3) (2) + (55) (6) (6) + (35) (6) (5) (mod 385), or Xm
27(mod 385).
5-7. Other Simultaneous Linear Congruences. We shall demonstrate
a method for finding a solution, when it exists, of certain linear simul-
taneous congruences whose moduli are not relatively prime in pairs by
proving the following theorem by induction:
Theorem 5-11. The set of n linear congruences x = a;(mod mi) has
a solution if and only if the greatest common divisor of any pair of moduli,
m^ mj, i and j having the values 1, 2, . . . , n, with % ^ j, divides the
corresponding a -
z
— a,j. When the integer X satisfies each congruence
of the set,t all common solutions take the form X + Lt, where L is the
least common multiple of the m,- and t is any integer.
Taking the two congruences
x = ai(mod mi) . .
x = a 2 (mod m 2 )
f Oystein Ore gave the general form of the solution in Am. Math. Monthly, Vol. 59,
No. 6, pp. 365-370, 1952.
THE SOLUTION OF CONGRUENCES 81
with d\2 = (mi, m 2 ), let us suppose that x satisfies both of them. Then
since
x = ai(mod m x)
Xq = a 2 (mod m 2)
we infer that
Xq = ai(mod di 2 )
£ = a 2 (mod c? i2 )
and that
a-i = a 2 (mod d i2 )
of the congruence
first that satisfies the second one. Every solution of
the first congruence is of the form a\ nay, and if any of these integers +
satisfy the second congruence, the values of y are determined by the
congruence
cti + miy = a 2 (mod m 2)
or
miy = a2 — ai(mod m 2)
But since dn \
(a 2 — «i), there is at least one value y of y that produces
a simultaneous solution a\ miy of the two congruences. +
Moreover, if there are two integers x and x\ that satisfy the given
congruences (5), substituting them in these congruences shows that
X\ = x (mod mi)
x1 = x (mod 2) m
and hence that
Xi = ^ (mod L)
Hence,
X= a* (mod dik )
X= a k (mod d ik )
and therefore
di = a (mod d ik )
fc
determine a value for the parameter t so that this expression will produce
a solution of x = a (mod m k ). To prove this statement, consider the
fc
congruence
X + Lk-it = a k (mod m k)
in the form
Lk-it = ak — X (mod m k )
If p is a prime factor of any of the ra 4-, let w!i be the exponent of the
highest power of that prime contained in m*. The highest power of this
p power of p that is in any one of m h m 2
in Lk-i is the highest , . . .
,
be m's But
.
X — ar = 0(mod m r)
and hence
X - ar = 0(mod p
m/
)
Since a k —
is divisible by the greatest common divisor of m k and m r it
ar ,
X - ar = 0(mod p
m °')
and
ak — ar = 0(mod p vls ')
Therefore,
X - ak - 0(mod p
m>)
X = Xi(mod L -i) fc
X = Xi(mod m k )
and hence
X = Xi(mod Lk)
EXERCISES
a. x3 + x2 +3 = 0(mod 5)
6. 2z 3 +1 = 0(mod 3)
84 ELEMENTARY THEORY OF NUMBERS
a. x m 2(mod 11)
x = 4(mod 15)
x = 9 (mod 14)
b. x = 11 (mod 21)
x = 2 (mod 12)
x s 4(mod 10)
c. x a 12 (mod 46)
x = l(mod 31)
x = 16 (mod 28)
nr
• • •
p r there is a solution of the congruence
,
S{x) = 0(mod pi ni )
Six) = 0(mod p 2 »«)
/(x) = 0(mod p r nr )
congruences
x = £i(mod pi ni ) (8)
Let this solution be x = Xi(mod m). The integer X\ satisfies both the
set (7) and the original congruence (6) because for each i
Xi = x z (mod pi ni )
and therefore
SiX,) =f(xi)(mo&pf)
But
Sixi) = 0(mod pi**)
so that
SiX x)
m 0(mod p^-i)
and
SiX,) = 0(mod m)
THE SOLUTION OF CONGRUENCES 85
the set of congruences (8) we replace the solution of just one of the
If in
congruences of (7), say the first one, by a solution x[ distinct from X\
modulo pi ni the solution x ,
=X 2 (mod m) of the resulting set,
x = xi(mod pi ni )
x = ^(mod pfi) j = 2, 3, . . . , r
willbe distinct modulo m from the solution Xi of (8), for if the solutions
were the same,
Xi = X 2 (mod m)
Xi =X 2 (mod pi
ni
) i = 1, 2, . . . , r
Then
xi = xJ(mod pi ni )
i=i
and the pi are distinct primes.
We have, therefore, reduced the problem of solving a congruence
f(x) = 0(mod m) to that of solving a congruence whose modulus is a
power of a prime.
5-9. The Solution of f{x) = 0(mod p ). Any integer that satisfies s
The converse, however, is not true, but it is obvious that if the second
congruence fails to have a solution, f(x) = 0(mod p s ) can have no solution.
Suppose that f(x) = 0(mod p 8-1 ) has a solution x = a;' (mod p*~ ). l
Under what conditions will one of these integers, x' + kp 5-1 be a solution ,
fix' + kp 8 ' 1
) = 0(mod p
8
)
n~ l
When/(x) = a x + a\X + n
+ a n is a rational integral function
• • •
(n)
f (x')
n S -n J
+ frn
p
\_>_
nl
/
mQ( J p s\
is an identical congruence, the expressions (r) (re') /r! having been shown
~
to be integers. Moreover, if s > 2, then p rs r > p 8 f or r > 2 and hence
all except the first two terms of the expansion are congruent to for the
modulus p s so that ,
8- 1
p integers x' + kp is a distinct solution modulo p of fix) = 0(mod p ).
s 8
can be derived from x' unless x' itself satisfies fix) = 0(mod p ), in which
s
case x' + /cp s_1 yields exactly p incongruent solutions modulo p by letting
s
EXERCISES
3. 6a:
2
+ = 0(mod 500).
17a: - 20 4. a: - 19a; + 32a: + 34 = 0(mod 75).
3 2
7. x -
s - 2a; - 2 = 0(mod 2000).
a:
2
8. 2a: + - 6a: - 13 = 0(mod 340).
3
a:
2
reduced residue system modulo ra. The integers in the second set are,
therefore, in some order congruent to those in the first set. Hence,
ari 53 rn(mod m)
ar 2 = r» 2 (mod m)
ar^m) = n>(m)(mod m)
Therefore,
a (t>(- m)
r 1r 2 * • r^ (m) = nr 2 • • • r^ (ro) (mod m)
and
,<Kro) = l(mod m)
~l
Corollary 1. If p is a prime and a is prime to p, av = l(mod p).
Corollary 2. If p is a prime and a isany integer, a p = a (mod p).
Examples. 56 = l(mod 7); 2
48
= l(mod 105).
EXERCISES
a <t>(m) = i( mo d m)
Hence,
a^ m) b = 6(mod m)
x (p-d/2 _ 1 =
0(mod p) andx^-« /2 + 1 = 0(modp) has exactly (p - l)/2
solutions that are incongruent modulo p.
For p > 2,
x p-i _ 1 = (a^-D/ 2 - l)(x^-»' 2 + 1)
ifp is of the form 4fc + 1 and (p, a) = 1, both a and p — a satisfy the
same congruence, but if p is of the form 4k — 1, a satisfies one of the
congruences while p — a satisfies the other.
Corollary 2. If p is a prime greater than 2 and d divides p — 1, the
congruence x d — 1 = 0(mod p) has exactly d solutions that are incon-
gruent modulo p.
EXERCISES
1. Write the solution of Sx = 20 (mod 35), and reduce it to a least positive residue
modulo 35.
2. Find the solutions of x +
8
1= 0(mod 17) and x8 — 1 = 0(mod 17), and also of
x* + 1 = 0(mod 19) and x» - 1 = 0(mod 19).
How many solutions has the congruence x 3 — 1 = 0(mod 13)? Find them.
3.
Prove that the congruence x 2 + 1 = 0(mod p) in which p is a prime of the form
4.
xp — x = 0(mod p)
p, we observe that both the quotient Q(x) and the remainder R(x) are
integral polynomials and that
a x s= l(mod p)
the congruence
xp — x = f(x)Q(x) (mod p)
is identical and from Theorem 6-3 we infer that f(x) = 0(mod p) has
exactly n distinct solutions modulo p.
6-3. Wilson's Theorem
Theorem 6-7. If p is a positive prime, (p — 1)! +1= 0(mod p).
Since the integers 1, 2, . . .
, p — 1 of a reduced residue system
~
modulo p constitute the solutions of the congruence x v l
= l(mod p),
there are exactly p — 1 linear factors modulo p of o^
-1 —
1. Hence,
x p-i _ i = ( x _ i)( x _ 2) • • •
(z — p + l)(mod p)
-1 = (_i)P-i(p - l)!(mod p)
from 1, 2, . . .
, p — 1. Likewise, except for sign, the coefficient of
X P-r-i ;
for r = 1, 2, . . .
,
p — 2, is the sum of products of integers
selected r at a time from the same set. All these sums are, therefore,
(n - 1)! + 1 = 0(mod n)
Hence, n a prime.
is
EXERCISES
Show that, for p > 5, (p — 1) + 1 has a prime factor different from the prime p.
2. !
3. If p is a prime of the form 4.n + 1, prove that (2n)! is a solution of the con-
modulo p?
7. Show that if ri, r 2 r p _i is any reduced residue system modulo p, a prime,
, . . . ,
p-1
1
1 rt - = — l(mod p).
i=l
8. If r p _i is a reduced residue system modulo p, an odd prime, then p
n, r 2 , . . . ,
x 2 = l(mod p) and ax = l(mod p), where (a, p) = 1 and p is an odd prime. Notice
that of the integers 1, 2, 3, p — 1 only 1 and p — 1 satisfy the first congruence
. . .
,
and that when a is selected from the set 2, 3, p — 2, there is a solution of the . . .
,
qt where
St
, the factorizations are into powers of distinct positive primes.
If any n iy where i = 1, 2, . . , r, or S/, where j = 1, 2, . , t, is . . .
If m- 1,
J mM = m(1) = 1.
rf|i
factors chosen in all possible ways from these r primes. Thus we find
r Co -M(l)
,c 2 (--I) 2 viViVi)
n=l
The preceding theorem shows that
£ mWi) + £ /ift) + • • •
+ J "W») = X
di|l d 2 |2 dm|m
ju(l) will occur m times in the above sum; 2 will be a divisor of — of the
[1YI
— I
n= l d\n
and
m
n =l
g(m) =
^
d\m
f(d)
then
a\m/d
and
Kd)g
(j)
= mW J /(a)
a|m/d
Hence,
2^
d\m
)?
fe)
=
2d\m
M(rf)
2
a\m/d
/(a)
=
XX
d\m a\m/d
M(rf)/(a)
96 ELEMENTARY THEORY OF NUMBERS
But to say that a ranges through the positive divisors of m/d while d takes
on the values of the positive divisors of m is the same as saying that a
ranges through the positive divisors of m while d is a positive divisor of
m/a. Consequently,
= X /(a)
2
d\m/a
m(«0
d\m
m
</>(ra) =
5>3
d\m
d\m
0(m) = 7?i
/?l I
( 1 — • •
•
H h " • "
+
\ Pi Pr PlZ>2 Pr-l??r P1P2P3
•+(-1)' *
PlP2 ' ' •
)
Pr)
and
^..(i-l^i-i).. .(1-1)
EXERCISES
1. Is it necessary for the truth of Theorem 6-12 that /(ra) and g(m) be arithmetic
functions?
THE THEOREMS OF FERMAT AND WILSON 97
din d\n
ment by using a method analogous to that of Sec. 6-5, and then prove it by taking the
logarithm of each member of the given equation.
m
3. Prove that for any positive integer m, > v(n)/n < 1. Consider the value
n = l
m
of V (- - T-l) together with Theorem 6-11.1
n= l
CHAPTER 7
ON BELONGING TO AN EXPONENT
7-1. The X Function. We have proved that for any integer a prime
to m
a 4>(m) = l( mo d m)
In solving congruences, moreover, we have exhibited some cases in which
a positive power, smaller than <f>(m), of a particular integer a is sufficient
to produce modulo m even when a ^ 1. Take, for example, the con-
1
or
a2 = l(mod2 3
)
But
( a 2)2 = (l + 2 3 s) 2
or
a 22 = 1 + 2 4s + 2V
so that
a 22 = l(mod 2 4)
In like manner, if
a
2t
= l(mod 2k)
it follows that
or
"' 1
a2 m l(mod2 A:+1 )
ON BELONGING TO AN EXPONENT 99
this integral power of any integer prime to 2 yields the residue 1 for the
modulus 2 n . Accordingly, we proceed to give a name to this number
n
0(2 )/2 as well as to other numbers closely related to <f>(m).
It was R. Carmichael who used the symbol X(ra) to designate the arith-
metic function which E. Lucas had defined as follows:
1. If m = 2 n and n = 0, 1, or 2, X(ra) = <f>(m).
2. If m = 2 n and n > 2, X(ra) = 0(ra)/2.
3. li m = p n p being an odd prime, X(p n ) = <£(p n ).
,
4. If m = 2 npiWl2>2n2 Pr
nr the
p where i = 1, ' * •
, 4-, 2, . . . , r, being
distinct odd primes, then X(m) is the least common multiple of X(2 n ),
n ').
X(pi»0, • • • , X(Pr
Thus, when m has the form 2 n for n =
0, 1, or 2, the form p
n
or 2p n for ,
n >
and p an odd prime, the X function has the same value as the
function, but when m has the factor 2 n with n > 2, or 2 2 and an odd
prime factor, or two factors that are powers of distinct odd primes, the
X function is at most half of the function. <f>
• •
nr
p r and (a, m)
• = 1, we know, therefore, that
a X(2«) = i( mo d2»)
au P
ni
i ) = l(mod pi ni )
But X(m) is a multiple of each of the functions X(2 n ), \(pi ni ), and thus
n
X(ra)/X(2 ) and \(m) /\(pi ni ) are integers. Consequently,
( a xC2»))x<«)/x(2.) = i( mo d2 TC
)
and
( a X(p^))X(m)/X( Pi "») = l( mo d p .».)
n
Finally, since 2 , pi ni , . . .
, pr
nr
are relatively prime in pairs,
a x(m) = i(mo d m)
Therefore, if m is not of the form 2 1, or 2, and not of the form
n
for n = 0,
n
p or 2p f or n >
n
and p an odd prime, then the X function gives a better
result than does the function. It is on this account often advantageous
cf>
to have:
Theorem For (a, m) = 1, a Mm) = l(mod m).
7-1.
Example. Although 0(2800) = 0(2 4 )0(5 2 )0(7) = 960, X(2800) is the
least common multiple of 4, 20, and 6 and is only 60. Hence, for (a, 2800)
= 1, a 60 = 1 (mod 2800).
100 ELEMENTARY THEORY OF NUMBERS
ar = l(mod m)
But d is the least positive exponent such that a d = l(mod ra), and there-
fore r = Consequently, d k.
0. |
This corollary shows that we need try only divisors of X(m) to find the
exponent to which an integer belongs modulo m. For instance, to find
the exponent to which 7 belongs modulo 55, we try only the exponents
2, 4, 5, 10, and 20, for X(55) = 20. Thus 7 2 = -6(mod 55), 7 4 =
36(mod 55), 7
5
^ 32(mod 55), 7
10
^ 34(mod 55), and 7 20 = l(mod 55).
Hence, 7 belongs to X(55) modulo 55.
In 1844 A. L. Crelle gave a device for finding the exponent to which an
integer a belongs modulo m. To employ this method, first set up the
integers 1,2, m — 1 in a row, and under 1 put r h the least positive
. . . ,
residue modulo m of the integer a under 2 put the least positive residue ;
1 2 3 4 ... m- 1
n r2 r3 r4 ... r m -i
r h 2ri, 3fi, . . .
,
(m — l)ri
ON BELONGING TO AN EXPONENT 101
under t.
Thus, if m= 7 and we wish to find the exponent to which 3 belongs
modulo 7, we form the table
12 3 4 5 6
3 6 2 5 14
Then 3 = 3 (mod 7), and so we move to 3 in the first row. We find 2
under 3, and hence 3 2 = 2 (mod 7). Moving to 2 in the first row, we find
6 under it, and have 3 3 = 6 (mod 7). Continuing in this manner, we find
34 = 4, 35 = 5, and 36 = l(mod 7). The integer 3, therefore, belongs to
6 modulo 7. Moreover, the residues of the first six positive integral
powers of 3 are in order 3, 2, 6, 4, 5, 1, and it is evident that this cycle is
have only the values 1,2, d, the difference s — t is less than d and
. . . ,
EXERCISES
integer for which the congruence is true, then 2k is the exponent to which a belongs
modulo p.
102 ELEMENTARY THEORY OF NUMBERS
8. If the integer a belongs to d modulo p, a prime, show that the product of all the
distinct residues of the powers of a is congruent to 1 or — 1 according as d is odd or even.
9. Show that x = ba
K(m) ~ (mod m) is a solution of ax = b (mod m) if
(a, m) = 1.
1
Compare the fact that the powers of 2 will generate all the solutions of x 4
10.
= l(mod 5) with the corresponding property of the root i of the equation x 4 — 1 = 0.
What do you notice about the other solutions?
and suppose that the integer a belongs to d modulo p. Then each integer
of the set
a, a2 az , , . . . , ad
(a 8 )* = (a d ) s = l(mod p)
(a 8 ) do ss a Sod 3= l(mod p)
Since there are <f>{d) positive integers less than d and prime to d, exactly
<j>(d) of the powers a 8 where , s = 1, 2, . . . , d, belong to the exponent
d modulo p.
ON BELONGING TO AN EXPONENT 103
d/n modulo p.
To prove Corollary 3, notice that if p = 2, d can be only 1, for a is odd.
In the case of an odd prime, if d = d n, we saw that
(a s ) d ° == l(mod p)
Now suppose that
(a s Y = l(mod p)
follows that do \
t. This is impossible when t < do. Therefore, t = do,
(ab) st
= (a') '(&')' = l(mod m)
But if a6 belongs to k modulo m, so that
(ab) k = l(mod m)
then k \
st and k < st. Moreover,
(ab) ks = b ks = l(mod m)
and therefore t \
ks, so that t\k. In like manner,
(ab) kt
= a kt
= l(mod m)
and s |
kt, so that s |
k. Since (s, ^ = 1, it follows that st |
k and s£ < fc.
Consequently, k = st.
Theorem 7-6 (H. G. Erlerus, 1841). When pi and p 2 are odd primes,
if m = ai(mod pi) and m = a 2 (mod p 2 ), and if in addition ai belongs to
Since m = dl
l(mod pi) and m<* 2 = l(mod p 2), if L is the least common
multiple of di and d 2 then ,
Therefore,
mL = l(mod P1P2)
Therefore, di k, d 2 k, and L
\
k. \
Hence, k = L. \
EXERCISES
1. Find an integer that belongs to 2 modulo 19 and one that belongs to 3 modulo 19.
5. Show that 2 belongs to 12 modulo 13, and thus find the exponent to which 8
belongs modulo 13. Do any other integers belong to this exponent modulo 13?
6. Find the integer to which 7 belongs modulo 5 and modulo 11. Then determine
the integer to which 7 belongs modulo 55.
7. When p is a prime, if a and b are prime to p, and if a = b (mod p ), show that
n
a? = 6 p (mod p
n+1
), and hence by induction that a pr
= 6
pr
(mod p
n+r
).
7-3. Another Test for a Prime. If we can find one integer a prime to
the integer m and satisfying the condition
~l =
am l(mod m)
a m-i s i( mo d m)
Again we can answer negatively by showing a case in which the hypothesis
ON BELONGING TO AN EXPONENT 105
a 80 = 1 (mod 561)
because X(561) = 80. Consequently,
a 56o _ i( mo d 561)
Or we may reason that since the divisors of 46 are only 1, 2, 23, and 46,
and because 45 23 = (47 - 2) 23 = (-2) 23 = -l(mod 47), so that 45 does
not belong to 1, 2, or 23, then the integer 45 belongs to 46 modulo 47.
Hence, by virtue of Theorem 7-7, 47 is a prime.
7-4. Primitive Roots. Is there a positive integer k smaller than X(m)
and satisfying the condition that, for any integer a prime to m, a k =
l(mod m)? The answer has been completely determined because Gauss
showed that exactly <£(</>(m)) integers belong to </>(m) if m is 2 n with ,
R. Carmichael showed that for all other moduli there is at least one integer
that belongs to X(m). Consequently, there is no positive integer k
smaller than X(m) and such that, for all integers prime to m, a k =
l(mod m). We shall proceed to develop these ideas.
We call an integer that belongs to 4>{m) modulo m a primitive root of m
or a primitive root modulo m. It is evident that 1 is a primitive root of 1
and 2 and that 3 is a primitive root of 2 2 There are no other primitive
.
m) < 0(d)
0(<« + 0(d 2 ) + • • •
+ Hdr) = V - 1
4>(di) + <f>(d 2 ) + • •
+ <f>(d r ) = p - 1
Because no yp{d ) can exceed the corresponding 0(d/), if any \p(di) were less
z
than the corresponding 0((&), these statements could not both be true.
Therefore, for all i,
f(di) = 0(cfc)
Notice that 3 2 = 9(mod 17) belongs to the exponent 8 modulo 17, for
(2, 16) = 2 and ^- = 8. Moreover, the other integers that belong to 8
modulo 17 are of the form 3 s where (s, 16) = 2. Hence, s = 6, 10, and
,
14. The integers are, therefore, 3 6 3 10 and 3 14 and they reduce to 15, , , ,
8, and 2 modulo 17. In like manner we can find the integers that belong
to 4 modulo 17, for in this case (s, 16) = 4. Thus 3 4 and 3 12 belong to
4 modulo 17. There is just one integer that belongs to 2, and it is
3 8 = 16(mod 17).
ON BELONGING TO AN EXPONENT 107
EXERCISES
Now select any positive integer a 2 less than p and not one of the residues
of thepowers of a±. Then if a 2 is not a primitive root of p, a 2 belongs to
some d 2 modulo p.
The exponent d 2 cannot be a divisor of d\, for if d\ = kd 2 ,
a hd % = l( mo d p)
and a: =
a 2 (mod p) would be a solution of x dl = l(mod p), which is
impossible because the powers of a\ determine all the solutions of this
congruence.
If d 2 is a multiple of d h but not p — 1, we have found an integer that
belongs to an exponent modulo p that is greater than d\.
If (di,d 2 ) = I, then a x a 2 belongs to d\d 2 modulo p.
lib = (di, d 2 ) and b is neither 1 nor di, factor b into powers of distinct
primes so that b = pi ni p 2 n pr
nr
Then separate b into two rela-
* • • •
.
if
a p-i =£ i( mo d p
2
)
the condition
(a + kpY~ l
?£ l(mod p 2 )
n
and that this integer is a primitive root of p .
~ s
First, let us suppose that when a belongs to p — 1 modulo p, av l
l(modp 2
). Then
ON BELONGING TO AN EXPONENT 109
~l ~2
(a + kp) p = a?- 1 +~(p - l)a p kp + • • •
+ (fcp^-^mod p 2 )
= 1 — ap 2
/cp (mod p 2
)
p~
and consequently (a + kp) l
is congruent to 1 modulo p 2 if and only if k
is divisible by p. If we, therefore, choose k prime to p, then a + /cp will
(a + ftp)*'-
1
^ l(mod p 2 )
= r<^ = l(mod p n ).
n)
It is true that since (r, p) 1, But does r belong
n
to an exponent t modulo p smaller than 4>(p n )? If so, t is a divisor of
4>(p
n
) = p n~ l
(p — 1). More than that, since it is necessarily true that
r* = l(mod p) and r belongs to p that p — 1 — 1 modulo p, it is clear
divides if. Hence, has the form p s (p — 1) with s = 0, 1, 2,
£ or . . . ,
r
pn-2(p-l) _ l( m()( J pn)
We shall show, however, that the last congruence cannot be true and
hence that r cannot belong to an exponent less than </>(p n ) modulo p n .
~l
in the form rp = 1 + cp, where (c, p) = 1. Then
-i =
(r p y
n -*
(1 + cp) pn_2 (niod p")
n-2 _ ^
^ 1 + p^Cp + ^ ^_ ii ( cp )2 +
+ (cp)
;,n_2
(mod p n )
The (m + l)st term of this expansion is
p
n-2(
p
n-2 _ j) . .
( p
n-2 - m+ 1)
: 1/ p
m!
p
n
, that is,kp > n. But
unless n fcp* > t + 2. Each—term 2 — t -{- l
Hence, f or n > 3
rp»-HP -i) =£ i( mo d p
n
)
If n = 2, we know that
-
rp x
^ l(mod p 2 )
whereas
r p( P
-i) = i( mo d p
2
)
y y2 yP n_1 (p— 1)
s pn) = n~ 1 —
r
u
r v( mo d w, u 1, 2, . . .
, p (p 1)
n~ 1 — n
only if s is prime to p (p 1). There are, then, exactly <f>(4>(p ))
n
incongruent integers that are primitive roots modulo p .
EXERCISES
Find the primitive roots of 49. Find also all the integers that belong to the
2.
6. If r belongs to <j>(p ) modulo p and (s, <t>(p )) = d ?* 1, does r belong to <f>(p )/d
n n n 8 n
modulo p n ?
n
Theorem 7-10. There are exactly cf>(<j>(2p )) incongruent primitive
roots modulo 2p n .
.<f>(2pn)
l(mod 2p n )
n~ 1
< (p — 1) modulo p
n
and if a belonged to d p then since a is odd, ,
r+
(pn)
— 1 is divisible by 2 as well as by p
n
and if r belonged to an exponent ,
n n
smaller than 4>(2p ) modulo 2p it would belong to that exponent ,
modulo p n .
n
is also a primitive root of p because it is in the same residue class as r
modulo p n is odd and is of necessity a primitive root of 2p n
, .
other hand, if two of the <f>(<f>(p n )) odd primitive roots modulo p n selected
one from each of the residue classes modulo p n were congruent modulo
2p n they would be congruent modulo p n
,
There are, therefore, exactly .
n
incongruent primitive roots of 2p n
(f>(<l>(2p )) .
is not a primitive root of 578, it yields 152 289 = 441, which is. There +
are in all 0(272) = 128 incongruent primitive roots of 578.
EXERCISES
Find the primitive roots of 98. Determine the integers that belong to the
2.
exponent 3 modulo 98. Find a primitive root of 686.
3. Prove that the congruence x^ 2 ?") = l(mod 2p n ) has exactly 4>{2p n ) solutions
<f>(2p
n
) if and only if (s,<j>(2p ))
n =
Prove, furthermore, that if (s,(j>(2p n )) = d, then 1.
5. Show that if p is an odd prime, the product of two primitive roots modulo 2p n is
pk
n
*, where the p i} with i = 1, 2, . . . , k, are distinct primes, then an
integer r that satisfies both the congruences
x = ri(mod mi)
and
si r 2 (mod n
x pk ")
and
rs = l(mod p k Uk )
But r belongs to A (mi) modulo mi and to \{pk nk ) for the modulus p& n *.
Therefore, both A (mi) and \(pk nk ) divide s. This means that the smallest
s can be is the least common multiple of A (mi) and \(pk nk ). This integer
is exactly A(m). It is true, moreover, that r X(m) = l(mod m) since
(r, m) = 1. is a primitive A root modulo m.
Therefore, r
Carmichael also showed that when r is a primitive A root of m, the
powers of r whose exponents are prime to A(m) give </>(A(m)) incongruent
primitive A roots of m, and the product of these A roots is congruent to
I modulo m. These powers of r do not necessarily yield all the primitive
A roots of m, but the same powers of another primitive A root will either
repeat in some order the results obtained from r or give </>(A(m)) different
primitive A roots of m distinct from those generated by r.
Although the theory of numbers is a branch of mathematics that we
evaluate on the basis of the profundity of its truths and the variety and
simplicity of its methods rather than on its applicability to practical
problems, yet it is interesting to observe that in 1935 H. P. Lawther
showed how the theory of primitive roots and primitive A roots can be
applied to the problem of splicing telephone cables.*
Example. To find a primitive A root of 21, we first find a primitive
root of 7 and also of 3. It can be easily verified that 3 belongs to 6
modulo 7 and that 2 belongs to 2 modulo 3. We then find the common
solution of the congruences
x = 3 (mod 7)
x = 2 (mod 3)
The solution is x = 17 (mod 21), and this integer is a primitive A root of 21.
If we now find the powers of 17 that have exponents prime to A (21) = 6,
we have a set of 0(6) =2 primitive A roots of 21. They are 17 and
17 5 = 5(mod 21).
There are but two incongruent primitive roots of 7, and they are 3 and
5. When we use the integer 5 with the only primitive root of 3 to form
the set of congruences
x = 5 (mod 7)
x = 2(mod 3)
we is x = 5 (mod 21).
find that the solution But the set of powers, 5 and
5 5 repeat the
, two primitive A roots of 21 already found. This situation,
however, does not mean that there are no other primitive A roots of 21,
for the number 2 belongs to 6 modulo 21. Moreover, 2 and 2 5 =
II (mod 21) form a new set of two primitive A roots of 21.
* H. P. Lawther, Jr., Am. Math. Monthly, Vol. 42, No. 2, pp. 81-91, 1935.
114 ELEMENTARY THEORY OF NUMBERS
EXERCISES
modulo 2\
there are just three incongruent integers that belong to d
We have shown that the integer 3 is a primitive X root of 2 n if n > 3.
On this basis we shall show that for the modulus 2 n any integer having
the form 8/c + 3 cannot belong to an exponent smaller than 2 n_2 If .
n > 3,
2 "- 3 2n ~ 3 2 "- - 1
(8/c ± 3)
2 " -3
= (3 + 8/c) = 3 ± 2*- 3
(3)
3
(2 £0
3
+ • •
•
~ 2- -1 - (mod
± 2 W 3 3
3(2 /c)
3
+ (2
3
/c)
2 3
2")
Hence,
2 "- 3 "~ 3
(8k ± 3) = 32 (mod 2")
2n " 3 "2
But since 3 ^ l(mod 2 n ), 8/c ± 3 belongs to 2 M modulo 2 n if n > 3.
yielding all positive integers of the required form that are less than 2\
If n = 3, it is obvious that 3 and 5 belong to X(2 3 ) = 2 modulo 2 3 .
Again, if n > 3, we can prove that for the modulus 2 n all integers
having the form 8/c ± 1, in which k is prime to 2, belong to the exponent
2"~ 3 for ,
2 "" 3 2 "- 3
(8/c ± l) = 1 + 2"- 3 (2 3 /c) + • • •
+ (2
3
/c) (mod 2")
= l(mod 2 n
)
(8/c ± I)
2"
-4
s 1 + 2"- 4 (2 3 /c) + 2"- 5 (2— 4 - 3
1)(2 A0
2
± • • •
2n_4
+ (2
3
A-) (mod 2 n)
= 1 ± 2"" /c(mod 2 n
1
)
~
to 2 can be chosen from the integers 1,2,3 2 n_3 in 4>(2 n s ) ways,
ON BELONGING TO AN EXPONENT 115
and thus the form 8k ± 1 yields 20(2 n_3 ) = 2 n_3 integers from 1 through
2n " 4
(8Jfe ± l) = l(mod 2n)
n~a
(2V ± l)
2n_s
= 1 + 2 (2 s
r) + • • •
+ 8
(2 r)
2n
~'(mod 2 n )
= l(mod2 n )
2 "" s_1
= 2-- s - 1 n ~ s- 2 n- s~ l -
s
(2 r ± l) 1 ± s
(2 r) + 2 {2 l)(2 s r) 2 ± • •
2n ~ s-1
+ (2Y) (niod 2 n )
= 1 + 2 w -V(mod 2 n )
~s
so that in this case 2 s r ± 1 belongs to 2 n modulo 2 n . There are then
n~ s
<f>(2 ways of choosing r prime to 2 so that the integers 2 s r ± 1 are
)
n — n
it is also evident that 2 1 belongs to 2 modulo 2 Consequently, for .
n~ 2 ~
2 of them belong to 2 n 2 modulo 2 n
n- 3 = ~
2</>(2 ) 2 n 3 belong to 2"~ 3
n~ 4 = ~ ~
2<K2 ) 2 n 4 belong to 2 W 4
~s = ~s ~s
20(2 n ) 2n belong to 2 n
modulo 2 if n > 2.
n
n
7-9. Integers Belonging to a Divisor of (f>(p ) Modulo p n
*Theorem p is an odd prime and d is a divisor of 4>{p n ),
7-13. If
where n > 1, there is an integer that belongs to d modulo p n .
If d <f>(p ), d = kp
|
n u where k is
a divisor of p — 1 and
, < u < n — 1.
Take an integer a that belongs to k modulo p. Then a = l(mod p).
k
(a + rap^ = a* + ka - mp + k x
• • •
+ (mp) (mod p 2 ) fc
3= 1 + ka ~ mp(mo& k l
p
2
)
Hence, if (m, p) = 1,
(a + mp)* ^ l(mod p 2 )
Therefore, let r = +
mp. Then r belongs to k modulo p, and r k =
a
1 + cp with p) (c, =
Keeping in mind that the exponent to which r
1.
belongs modulo p n has the factor k, we see that for n > 2 and (w, p) = 1,
(r
&)«,p»-» = (1 + cp)
wpn
~\mod p n )
and
-l
(r*)^""
1
= 1 +
wcp n (mo& p n )
=z£ l(mod p n )
But
(^p--! == i( mo d p
n
)
n~ l
Therefore, r belongs to kp modulo p when n n
> 1.
a fc
ss l(mod p s_1 )
but
a* ^ l(mod p s )
there is an r = a(mod p*), where i = 1, 2, . . . , s — 1, such that
r k ss l(mod p s ),
for since a* = 1 — 2p
s_1 with (£, p) = 1,
~
(a + mp s l
)
k
= a k
-\- fca
ft_1
mp*~ 1 (mod p s )
ss 1 — £p
s_1
+ ka k ~ mp ~ (mod p l s l s
)
ON BELONGING TO AN EXPONENT 117
Let r = a + rap s_1 . Then r belongs to the exponent /c for each p*, where
i = 1,2, . . . , s.
(r + gp
s
)
k as l(mod p s+1 )
This v is in each of the moduli p% where i = 1, 2,
the class with r for
(v
a) WP »---i = (1 + cp wpn ~\mod s
)
~s
p
n
)
= 1 + wcp^^mod p w )
^ l(mod p n )
but
(^)p
n_s
= l(mod p n )
~s
Therefore, v belongs to kp n for n > s > 0. modulo p n
This result
implies that there is always an integer that belongs to a divisor of 4>(p n )
modulo p n .
x d = l(mod p n
)
Moreover, a s
, where s = 1,2, . . . belongs to d modulo p n if and only
, d,
f(di) + ffa) + • • •
+ Hdm) = v n~\v - l)
n
If r belongs to <t>(2p ) modulo 2p n the incongruent
, integers modulo
n
2p that satisfy the congruence
•*(2p») = l(mod 2p n )
(2pn)
are r, r2, . . . , r* . These are all the integers from 1 through 2p n
that are prime to 2p n In the manner previously employed we can show
.
(2pn) n
and b satisfies :r> == l(mod 2p ) and is, therefore, con-
the congruence
gruent to a power of modulo 2p n Consequently, all integers that belong
r .
will belong to d modulo 2p n But there are exactly cf>(d) integers s in the .
n n
set 1, 2, 3, ... <j)(2p ) that have with 4>{2p ) the greatest common
,
n
divisor )/d. Hence, exactly 4>(d) incongruent integers belong to
<j>(2p
d modulo 2p n .
nj
<t>(k(pj )) • Consequently, there are
r
n
^(X(2"»))(mod2 w <>)
Y[ cf>(\(pj 0)
y-i
nj
r, that contains exactly one divisor of each \(pj ) and such that the least
YHm) = i( mo d py
w ')
and that
YHm) = l( mo d m )
nj
to da modulo pj , there will be J] kq congruences (2) for one choice of
3 =1
r
the d^. Consequently, there are exactly \l/(di ) (mod 2 n °) ] J <f>(da) incon-
=1 3
g-f* = g2
S2t
(mod m)
But because the powers of g 2 repeat the S2
original 4>(\(m)) roots generated
by g 2 for a certain t, say ti,
,
•1*1 = g2
**i = g 2 (mod m)
This conclusion implies that our assumption is false. There will, there-
fore,be exactly
r
*(<fco)(mod2-) II *(*/)
0(X(m))
where i = 1, 2, q3 j = 1, 2,
. .
. . r, having the least common
.
, ,
. ,
Hence,
( 7 «>)<V = l(mod prt
and thus d,-,* divides wd^. Therefore, d^h divides d^. In like manner,
d it h divides d^h, and finally d^h = d;^, which is contrary to our assumption.
If there are q sets of divisors dij, the primitive X roots of m determined by
them are, therefore, distinct modulo m.
But each integer which belongs to X(m) modulo m and which is, there-
fore, prime to each of the p3 ni belongs to exactly one exponent that is a
divisor of \(p3 nj ) modulo p3 nj Hence, from all possible choices of sets of
.
forwhich the least common multiple of the da in a set is X(m), we find all
the incongruent primitive X roots modulo m, for if a belongs to X(ra)
modulo m, then
a\(pfi) = i( mo d py
n
j = 0, 1, . . . , r
If, however, the least common multiple of these dq were u < X(m), a
9 y=i
r
show that 10 and 19 are primitive X roots of 21. Notice that the powers
of 10 yield 0(X(21)) = 2 primitive X roots of 21, and they are 10 and
10 5 = 19(mod 21).
The integers 2 and 4 belong to 3 modulo 7, and 2 belongs to 2 modulo 3.
Therefore, the sets of congruences to be solved are
x = 2(mod 7) x = 4(mod 7)
x s 2(mod 3) x = 2(mod 3)
122 ELEMENTARY THEORY OF NUMBERS
Number of incongruent
Case Factors of X(2 3 ) Factors of A(3) Factors of A (7) primitive X roots of
168 determined
(1) 2 2 6 6
(2) 1 1 6 2
(3) 1 2 6 2
(4) 2 1 6 6
(5) 1 2 3 2
(6) 2 1 3 6
(7) 2 2 3 6
x = 3 (mod 8) x = 3 (mod 8)
x = 2 (mod 3) x = 2 (mod 3)
x = 3 (mod 7) x = 5 (mod 7)
x = 5 (mod 8) x = 5 (mod 8)
x = 2 (mod 3) x = 2 (mod 3)
x = 3 (mod 7) x = 5 (mod 7)
x = 7 (mod 8) x = 7 (mod 8)
x = 2 (mod 3) x = 2(mod 3)
x = 3 (mod 7) x = 5 (mod 7)
The primitive X roots of 168 so determined are 59, 131, 101, 5, 143,
and 47, respectively, and they occur in sets of 0(6) = 2, which are
5 and 5 5 = 101 (mod 168); 47 and 47 5 = 143 (mod 168); and 59 and
59 5 = 131(mod 168).
x = l(mod 8) x = l(mod 8)
x = l(mod 3) x = l(mod 3)
x = 3(mod 7) x = 5(mod 7)
x ss l(mod 8) x 3= l(mod 8)
a; s 2 (mod 3) x = 2 (mod 3)
x = 3(mod 7) x = 5(mod 7)
x = 3(mod 8) x = 3(mod 8)
a; ss l(mod 3) x = l(mod 3)
a; = 3(mod 7) a; s= 5(mod 7)
x = 5(mod 8) a: = 5(mod 8)
x 3= l(mod 3) x = l(mod 3)
x = 3(mod 7) x 3= 5(mod 7)
a: 3= 7(mod 8) x = 7(mod 8)
x = l(mod 3) x = l(mod 3)
a; s= 3(mod 7) a; = 5(mod 7)
The solutions modulo 168 are 115, 19, 157, 61, 31, and 103, respectively,
and they form the sets 19 and 19 5 = 115 (mod 168); 31 and 31 5 =
103(mod 168); 61 and 61 5 = 157(mod 168).
x = l(mod 8) x = l(mod 8)
x = 2 (mod 3) x = 2 (mod 3)
x = 2(mod 7) x = 4(mod 7)
x = 3(mod 8) x = 3(mod 8)
x = l(mod 3) x = l(mod 3)
x = 2(mod 7) x = 4(mod 7)
x = 5(mod 8) x = 5(mod 8)
x 3= l(mod 3) x = l(mod 3)
x = 2(mod 7) x = 4(mod 7)
a; 3e 7(mod 8) a; 3e 7(mod 8)
x 3= l(mod 3) a; = l(mod 3)
a; 3s 2(mod 7) a; = 4(mod 7)
The solutions modulo 168 are 163, 67, 37, 109, 79, and 151. They form
the sets 37 and 37 5 = 109(mod 168); 67 and 67 5 = 163(mod 168); 79 and
79 6 = 151(mod 168).
124 ELEMENTARY THEORY OF NUMBERS
x = 3(mod 8) x hh 3 (mod 8)
x = 2 (mod 3) x = 2 (mod 3)
x = 2(mod 7) x = 4 (mod 7)
x = 5(mod 8) x 5 (mod 8)
x = 2(mod 3) x s= 2(mod 3)
x = 2(mod 7) x = 4(mod 7)
x = 7 (mod 8) x = 7 (mod 8)
x = 2 (mod 3) x = 2(mod 3)
x = 2 (mod 7) x = 4 (mod 7)
The solutions modulo 168 are 107, 11, 149, 53, 23, and 95, and they form
the sets 11 and ll 5 = 107 (mod 168); 23 and 23 5 = 95(mod 168); 53 and
53 5 = 149(mod 168).
EXERCISES
INDICES
n = r
s
(mod p)
Gauss called the exponent s of r the index of n modulo p relative to the base r.
To express this idea, we write s = ind r n, but we usually omit the base r
when there is no danger of confusion as is true in the case of the con-
gruence r indn = ft (mod p).
As thus defined, the index of n modulo p is unique for the modulus
p — 1, for if
n = r
s
= r
(
(mod p)
and if s > t, then
-* = l(mod p)
and
s = 2(mod p — 1)
It is, therefore, convenient to use the least positive exponent s such that
n =
r (mod p) as the index of n modulo p.
s
Obviously the index of n
modulo 2 is useless.
Of course, the index of n determined by the primitive root r may be
different from that determined by another primitive root of p. For
instance, for the modulus 7, ind 3 2 = 2(mod 6) but inds 2 = 4(mod 6).
Theorem 8-1. If m= n(mod p), their indices relative to a particular
primitive root of a prime p are the same modulo p — 1, and conversely.
The proof follows immediately from the fact that if r is a primitive root
of p, the congruences r indm = r indn (mod p), and ind r m = ind r /t(mod p — 1)
imply each other.
Theorem 8-2. If p is a prime, and m and n are prime to p, then
md mn =
r ind r m+ ind r n(mod p — 1).
125
126 ELEMENTARY THEORY OF
Since
n = r indn (mod p)
and
m 53 r indm (mod p)
it follows that
mn = r
indm+indn (mod
p)
But
mn = r
indmn (mod
p)
Therefore,
ind r mn = ind r m+ ind r w(mod p — \)
If
n = r indn (mod p)
then
nk = r fcindn (mod p)
Also
nk = r indn^ m()CJ p)
Hence,
ind r n k = k ind r n(mod p — 1)
It is evident from these laws that the index of an integer plays a role
which is analogous to that played by the logarithm of a number. This
analogy is further emphasized by the following formula for changing the
base of a system of indices from one primitive root of p to another
Theorem 8-4. If p is a prime and n is prime to p, then ind ri n =
ind r2 n ind ri r 2 (mod p — 1).
or
ind ri n = ind r2 n ind ri r 2 (mod p — 1)
ri
ind ri r2 = r 2 (mod p)
ind ri r2 ind r2 r x ss ind r2 r2 (mod p — 1)
and
ind r r 2 ind r2
, r\ = l(mod p — 1)
Therefore,
n ind x = ind 6 — ind a(mod p — 1)
£, i + ra , i + 2ra , . . . , i + (d — l)ra
Therefore,
j. s r i+A;mo( mo ^ p) k = 0, 1, . . . , d ~ 1
ind 2 3 4 5 6 1 7 8 9 10
4 8 5 10 9 7 3 6 1
Then •
Hence, x = 10(mod 11), and all solutions of the original congruence have
the form x = 10 + 11/c. Therefore,
and
ind 7 + ind k = ind 5 (mod 10)
so that
ind k = 7(mod 10)
and
k = 7(mod 11)
Therefore,
x = 87(mod 121)
congruence.
Suppose that r is a primitive root of m and that c = r s (mod m). If
x = c(mod m) has a solution x = r (mod m), it follows that r kn =
n fc
c
<j>(m)/d = r
s4>(m)/d = (
r
<}>(m)\s/d = 1 (mod Til)
Conversely, if
c <Km)/d = i(mod m)
then
r s<t>(m)/d = i( mo d m)
Therefore, scf)(m)/d is a multiple of <t>(m), and s/d is an integer. As a
result, the congruence nk = s(mod 4>{m)) is satisfied by just d incongruent
values modulo cf>(m) of k. Corresponding to these integers, there are
exactly d incongruent values modulo m of x that form the complete set of
solutions of x n =
c(mod m).
Theorem If p is a prime and d = (n,p — 1), there are (p — l)/d
8-7.
incongruent values modulo p of c, prime to p, such that x n = c(mod p)
has a solution.
According to Theorem 8-6, the congruence x n = c(mod p) has a solution
~ 1)/d =
if and only if c (p l(mod p) where d = (n, p — 1). But the con-
~ 1)/d
gruence x ip = l(mod p) has a solution. There are, thus, exactly
130 ELEMENTARY THEORY OF NUMBERS
c
^m)/d == i( mo d m ) ?
the congruence x d
c(mod m) has a solution. =
Hence, if d ^ n, a residue of an nth power modulo m is always a residue
of a power that is smaller than n and is a divisor of both n and 4>(m). It
is thus clear that when p is a prime of the form 5k + 2, 5k + 3, or 5k + 4,
the test for a solution of x 5 = c(mod p) is the same as the test for a solu-
tion of x = c(mod p). Since the last congruence is always solvable, an
integer c, prime to p, is always a residue of a fifth power for prime moduli
of the form 5k + 2, 5k + 3, and 5k + 4. But if p = 5k + 1, c is a
residue of a fifth power modulo p if and only if c k = 1 (mod p) If p is a .
prime of the form 4A; — 1, the very test for a residue of a fourth power
modulo p, c 2fc_1 = l(mod p), is the same as that for a second power and
hence in this case the set of residues of fourth powers modulo p is identical
with the set of residues of second powers. If p = 4k + 1, then 4 =
(4, 4Jc) and no such statement can be made. Again, if p is of the form
3k + 2, every integer not a multiple of 3 is a cubic residue modulo p, but
if p is of the form dk + 1, c is a cubic residue if and only ifc = l(mod p). fc
EXERCISES
modulo p.
3. Prove that the odd prime divisors of x A + 1 are of the form Sn + 1.
4. If p is a prime, determine when the existence of a solution of x 6 = c(mod p)
is dependent upon the existence of a solution of x a = c(mod p) with n < 6.
6. Determine whether or not there is a solution and, if so, solve the congruences:
a. x3 = 5(mod 13)
b. x* = 7(mod 13)
6. Show that if r is a primitive root of p, then r^' 1 ^ 2 = — l(mod p), and thus that
a. 5x m 4 (mod 13)
b. 5x 2 = 6 (mod 13)
INDICES 131
n 1 2 3 4 5 6 7 8 9 10
ind 192 34 84 68 1 118 104 102 168 35
n 11 12 13 14 15 16 17 18 19 20
ind 183 152 141 138 85 136 31 10 145 69
n 21 22 23 24 25 26 27 28 29 30
ind 188 25 162 186 2 175 60 172 123 119
n 31 32 33 34 35 36 37 38 39 40
ind 82 170 75 65 105 44 5 179 33 103
n 41 42 43 44 45 46 47 48 49 50
ind 151 30 24 59 169 4 29 28 16 36
n 51 52 53 54 55 56 57 58 59 60
ind 115 17 77 94 184 14 37 157 148 153
n 61 62 63 64 65 66 67 68 69 70
ind 47 116 80 12 142 109 18 99 54 139
n 71 72 73 74 75 76 77 78 79 80
ind 177 78 91 39 86 21 95 67 167 137
n 81 82 83 84 85 86 87 88 89 90
ind 144 185 122 64 32 58 15 93 147 11
n 91 92 93 94 95 96 97 98 99 100
ind 53 38 166 63 146 62 158 50 159 70
n 101 102 103 104 105 106 107 108 109 110
ind 134 149 107 51 189 111 154 128 160 26
n 111 112 113 114 115 116 117 118 119 120
ind 89 48 41 71 163 191 117 182 135 187
n 121 122 123 124 125 126 127 128 129 130
ind 174 81 43 150 3 114 13 46 108 176
n 131 132 133 134 135 136 137 138 139 140
ind 20 143 57 52 61 133 110 88 190 173
n 141 142 143 144 145 146 147 148 149 150
ind 113 19 132 112 124 125 100 73 155 120
n 151 152 153 154 155 156 157 158 159 160
ind 126 55 7 129 83 101 140 9 161 171
n 161 162 163 164 165 166 167 168 169 170
ind 74 178 23 27 76 156 79 98 90 66
n 171 172 173 174 175 176 177 178 179 180
ind 121 92 165 49 106 127 40 181 42 45
n 181 182 183 184 185 186 187 188 189 190
ind 56 87 131 72 6 8 22 97 164 180
n 191 192
ind 130 96
INDICES 133
ind 1 2 3 4 5 6 7 8 9 10
n 5 25 125 46 37 185 153 186 158 18
ind 11 12 13 14 15 16 17 18 19 20
n 90 64 127 56 87 49 52 67 142 131
ind 21 22 23 24 25 26 27 28 29 30
n 76 187 163 43 22 110 164 48 47 42
ind 31 32 33 34 35 36 37 38 39 40
n 17 85 39 2 10 50 57 92 74 177
ind 41 42 43 44 45 46 47 48 49 50
n 113 179 123 36 180 128 61 112 174 98
ind 51 52 53 54 55 56 57 58 59 60
n 104 134 91 69 152 181 133 86 44 27
ind 61 62 63 64 65 66 67 68 69 70
n 135 96 94 84 34 170 78 4 20 100
ind 71 72 73 74 75 76 77 78 79 80
n 114 184 148 161 33 165 53 72 167 63
ind 81 82 83 84 85 86 87 88 89 90
n 122 31 155 3 15 75 182 138 111 169
ind 91 92 93 94 95 96 97 98 99 100
n 73 172 88 54 77 192 188 168 68 147
ind 101 102 103 104 105 106 107 108 109 110
n 156 8 40 7 35 175 103 129 66 137
ind 111 112 113 114 115 116 117 118 119 120
n 106 144 141 126 51 62 117 6 30 150
ind 121 122 123 124 125 126 127 128 129 130
n 171 83 29 145 146 151 176 108 154 191
ind 131 132 133 134 135 136 137 138 139 140
n 183 143 136 101 119 16 80 14 70 157
ind 141 142 143 144 145 146 147 148 149 150
n 13 65 132 81 19 95 89 59 102 124
ind 151 152 153 154 155 156 157 158 159 160
n 41 12 60 107 149 166 58 97 99 109
ind 161 162 163 164 165 166 167 168 169 170
n 159 23 115 189 173 93 79 9 45 32
ind 171 172 173 174 175 176 177 178 179 180
n 160 28 140 121 26 130 71 162 38 190
ind 181 182 183 184 185 186 187 188 189 190
n 178 118 11 55 82 24 120 21 105 139
QUADRATIC RESIDUES
4a y + 4a aii/ + 4a a 2 = 0(mod 4a n)
(2a y + ai)
2
= ai
2 — 4a a 2 (mod 4a n)
Now let
4a n = m
2a y + «! = z(mod m)
and
«i
2
— 4a a 2 = 6(mod m)
The original congruence is thereby reduced to the form
z
2
= b(mod m)
Suppose that (b, m) = d = e k, where e 2 is the largest square contained
2
e
2
k 2w 2 = b (mod m)
or
kw 2 = 6 (mod m )
x = kw (mod m )
134
QUADRATIC RESIDUES 135
Then
x2 s= b k(mod m )
and if we set
b k ss a(mod m )
w 2
= l(mod 5). Hence, w = 1, 4(mod 5), 2 = 3, 2 (mod 5), and finally,
x = 9, 6(mod 15).
2. Solve: x = 24(mod 60).
2
Since (24, 60) = 12, let x = 6z(mod 60). Then Sz 2 = 2(mod 5). Let
z = 3^ (mod 5), so that w = l(mod 5).
2
Therefore, w = 1, 4 (mod 5),
z = 3, 2(mod 5), and finally, x = 18, 48, 12, 42(mod 60).
EXERCISES
Solve the congruences:
a. x2 = 28 (mod 84)
b. x2 = 64(mod420)
diX = a(mod p) i = 1, 2, . . .
, p — 1
aidj = a (mod p)
and
a k a,j = a (mod p) i f^ k ^ j
then
di = a^mod p)
whereas these integers are distinct modulo p. The integers a are thereby z
separated into (p — l)/2 pairs, and the product of these pairs implies that
«i«2 * * '
cip-i = a (p_1)/2 (mod p)
Therefore,
= -l(modp) (p-i)/2
s= r 2
(mod p). Hence, the congruence
diX 3= a (mod p)
0,10,2
,'
r(p
*
—
'
^zia^^modp)
r)
But
r(p — r) s= — r = — a(mod
2
p)
Therefore,
(p - 1)! 33= -tf(p-»/J(modp)
and
a (p-D/2 = i( m odp)
Furthermore, if a (p_1)/2 = l(mod p), a must be a quadratic residue of
(p_1)/2 = — l(mod This condition is, therefore,
p, for if it were not, a p).
a test for a quadratic residue of p if p is an odd prime and a is prime to p.
Examples. Since 5 3
= 6 (mod 7), 5 is a quadratic nonresidue modulo
7, and because 2
3
= l(mod 7), 2 is a quadratic residue modulo 7.
It is interesting to observe that if the modulus is a composite m, the
following theorem gives a necessary condition for a quadratic residue of m :
(r
2)*(m)/2 = a ^^ )/2 (mod m)
But
r *(»») = i( mo d m)
Hence,
a <^(m)/2 = i( mo d m)
It is obvious that if m> 2, <£(ra) may be replaced by X(m) in the above
proof.
This result, however, does not provide a sufficient condition for a
quadratic residue of m, for although (7, 48) = 1, \(48)/2 = 2, and 7 2 =
l(mod 48), still x 2
= 7(mod 48) has no solution.
138 ELEMENTARY THEORY OF NUMBERS
a = r 2k (mod p)
or
a = r 2k+1 (mod p)
(r
2fc+i)(p-i)/2 _ i( mc.dp),
the exponent of r must be a multiple of p — 1. But then (2k l)/2 +
would have to be an integer, and that is impossible. Hence, in the second
case a is a quadratic nonresidue of p. Thus the set of quadratic residues
of p even powers of a primitive root of p.
consists of the
Corollary 1. The odd powers of any primitive root of an odd prime p
coincide with the quadratic nonresidues of an odd prime p.
Corollary 2. There are exactly (p — l)/2 incongruent quadratic resi-
dues and the same number of incongruent quadratic nonresidues of an
odd prime p.
Corollary 3. The product of two quadratic residues or two quadratic
nonresidues of an odd prime p is a quadratic residue of p, but the product
of a quadratic residue and a quadratic nonresidue of p is a quadratic
nonresidue of p.
When is at hand, it is convenient to use the even
a table of indices
powers of a primitive root of p to set up the quadratic residues of p, but
if a primitive root of p must be computed, the method implied by the
following theorem is usually the more expeditious one for finding quadratic
residues
M
I—=— 1 are the incon
l
2
, 22 ,
. . . , (
— =— J
to determine the quadratic residues modulo p. Each of
di
2
= a 2 2 (mod p)
then
(ai — a 2 )(«i + a 2) = 0(mod p)
QUADRATIC RESIDUES 139
EXERCISES
1. Is 15 a quadratic residue of 17?
2. Find all quadratic residues of 29 and 31.
3. Prove that the product of the distinct quadratic residues of a prime p = 4n — 1
tic functions and the theory of numbers, but he also wrote a book on
geometry which was so well received that at the time it rivaled Euclid's
" Elements" in popularity. In 1830 he published two volumes on the
theory of numbers that organized his own researches and those of his
predecessors in this subject. In this work he partly proved the remark-
able law of quadratic reciprocity.
+ 1.
140 ELEMENTARY THEORY OF NUMBERS
(?) - (?)
3. Euler's criterion shows that if p is an odd prime and (a, p) = 1, then
- = -
a (p 1)/2 (mod p).
J
4. Corollary 3 of Theorem 9-4 implies that if p is an odd prime and
(?)
5. If ai and a 2 are prime to p, ( — ) (
— )
= + 1, as well as ( — J
= \
—\
expresses the fact that &i and a 2 have the same quadratic character with
Then because ( - ) = (
^=— ) (
- )> the quadratic character of a with
W ~ \ v )\v)\v) \v)
and therefore our question about the prime moduli of which a is a quad-
of the first set of primes, and it is a quadratic nonresidue of the second set.
Example. There is no solution of x 2 = — l(mod 31), but there are
two solutions of x 2 = — l(mod 29), and they are x = 12 and x =
-12(mod29).
Theorem 9-7 (The Lemma of Gauss). Take p an odd prime and q
prime to p. Find the least positive residues modulo p of the integers
q, 2q, . . .
, [(p — l)/2]q. If u is the number of these residues that are
q, 2J, 3q, . . .
,
E
^q (1)
1, 2, . . .
, p - 1 (2)
Let
ai, (Li, . . . ,
au
represent the least positive residues greater than p/2 of the integers in
(1), while
bi, b2 , . . . ,
bv
denote those least positive residues which are less than p/2. Then
u + v = (p - l)/2.
The integers of the set
p — ai, p — a2 , . . .
, p — au
are prime to p, less than p/2, and are incongruent modulo p. Moreover,
these integers are distinct from the bi, for if
bi = p — a/(mod p) i = 1, 2, . . . , v; j — 1, 2, . . . , u
then
bi + a,j = 0(mod p)
sand t are positive and less than p/2, the sum s + t cannot be divisible
by p. Thus 6t + a,- cannot be divisible by p. Consequently, the integers
61, b 2 , . . . , bv , p — ah p — a2 , p — au
616. b v (p - di)(p - a 2) • • •
(p - au ) = —
V ——-
1
! (mod p)
and
(-l) u bA b v aia 2 • • •
au = ^—^ — ! (mod p)
But the bi and the a; are the residues of the products in (1). Therefore,
b v a\a 2 au = V g(mod
6162 • • • • • '
q •
2q •
o p)
P- h ^-^(mod
niv
p) !
and
~ 1)/2
(-1) U ^-7T^^ (P = ^-o-^!(modp)
By multiplying by (
— 1) M and dividing by [(p — l)/2]!, we have
f(p-l)/2 = — l) M (mod
( p)
But
- 1)/2
= g( p (mod p)
V
(j)-(-l)»(modp)
that(j) = (-l)«.
Theorem 9-8. If p is an odd prime and q is odd and prime to p, and if
V ~
M + + 1 q
then (-1)*.
-[?H
—
Let (p l)/2 = s. Also let
2 p\
the least positive residues modulo p of
)
= v
q
M+"
2q = p
_P J
sq
sq = p + rs
_P_
Adding these equations and using the fact that 1 + 2 +
[(p - l)/2] = (p - l)/8, we have
2
p
2
- 1
8
g = pM + ri + r2 + +r 8
£l__l 9 = pM + A + B (3)
But in Theorem 9-7 we also showed that the p — a together with the ? fey
p- 1
= pu — A +B (4)
8
v2 - 1
- = -
8
(q l) p (M u) + 2A (5)
= (-!)•- (-1)"
2q
On the other hand, if q = 2, then = 0, 0,
V
(P ~ l)g/2 l
= p- 1
= 0. Hence, M = and Eq. shows that
P J LP
[ 0, (5)
since p = 2& + 1,
p< 1
= -(2k + l)M(mod 2)
— u = w(mod 2)
144 ELEMENTARY THEORY OF NUMBERS
when p = Sn ± 3, (p
2 - l)/8 = Sn ± Qn 2
+ 1, and ( - )
- !
^J
We shall present a proof of this theorem that is based upon a geometric
demonstration given by F. G. Eisenstein (1823-1852).
c E
D
v^f
^<-
;
; ;
X
B A 4
• • •
j (<7
~ l)/2, we find that the number of lattice points within the
triangle OEC is
[?H?] + ;
"
+ [ViH
Hence, the number of lattice points within the rectangle OAEC is
_<_,,„
d) (,)
and consequently when p and g are distinct odd primes,
—
M -[ + 2q
+ •
+ p
2
1
q]
V J _ P.
2p — l V
N + + •
+ ff
-fe] L q J 2 q.
& = 1, 2, . . .
, (p — l)/2, no /bg/p is an integer, for both k and g are less
= +r+
sp g. But —^
T
is at most 1. Therefore, ^+ 1)g
is at
most s + 1.
pq -
+p p v -
can be written [**-' + = (2 - D/2,
2p 2p J
because p — q < 2p.
Assuming that for ft < (p — l)/2 the integer — is the last term of
the expression for M whose value is s, we shall find the number k of this term
P P
Hence,
and therefore
k
-[*¥>]
is the number of the last term of the expression for M having the value s,
where < s < (q — l)/2. It follows then that the number of the last
all nonnegative s < (q — l)/2, the number of terms of M that have the
QUADRATIC RESIDUES 147
— •
> p^i - [f ]
Moreover, the number of terms of M
that have the value — l)/2 — l)/2 Therefore,
(q is (p
-I^f]
~
M- - 2g
+ •
+ P Hi
B] P.
Oyg 3p 2p
+ 1
- + 2
2 J ([?] [?]) L 2 J LQ J
+ + +
+ g ~ 1
J 2 ~ 1
_ ["
g ~ *
g
[|]-[f]
- -
[^!]+^^
N+p 1 q 1
Hence, ikf + JV = ^—^ — • ^—^ — > and the quadratic reciprocity law
follows.
Corollary 1. If at least one of the primes p and q is of the form 4n + 1,
-©(J)--*-
both
Ms)-®-
primes and the form 4^ + then
Corollary 2. If p q are of the 3,
©6)-— (!)-©
=
Examples. 1. Test z 2 15 (mod 17) for a solution.
= +L
Also f
^) = (-1) 8 = +1, and
(~J
= (-l)tt«>U«>/8 Hence,
x = l(mod 2)
and one of
x = 1, 4(mod 5)
quadratic residue of all primes of the form 10A; + 1. On the other hand,
x = l(mod 2)
x = 2, 3 (mod 5)
If ( - J
is to be — 1, then either
p = 3(mod4) and (^ )
= +1
or
x = l(mod 4)
xsl,2, 4(mod 7)
x = 3 (mod 4)
and one of
x = 3, 5, 6(mod 7)
q = 4n +L Then = = (_l)(f-»/» If 2g is to be
(|) (?) (j) (j).
a quadratic residue of p, it follows that either
p = ±l(mod 8) and f = +1
?J
Ox'
If either
p m ±l(mod8) and (?
or
p m ±3(mod 8) and (
'
)
- fl
(!)
then 2g is a quadratic nonresidue of p.
When the given integer is of the form 2q with the prime q = 4n + 3, it
is evident that
(^J
= (-1)^-^ ( £j. But \S\ == (_i)(p-d/2 M ?
P\ + -
f^J = (-1)(p +4 P -5)/8
2 f The exponent 2
so that (p 4p 5)/8 is
and (-) = -
or when
( — J
I
— )• By combining the first two cases it is clear that the primes p
determined by those of which both qi and q 2 are quadratic residues are
characterized by the following statements:
1. They satisfy x = l(mod 2).
2. They are quadratic residues of q\.
3. They satisfy x =
l(mod 4) and are quadratic residues of q 2 , or they
satisfy x = 3 (mod 4) and are quadratic nonresidues of q 2 .
satisfy x = l(mod
and are quadratic nonresidues of q 2
4) .
z sa 3, 5, 6(mod 7)
From the first set we find that p = 1,9, 11, 25, 43, 51(mod 56), and from
the second, p = 5, 13, 31, 45, 47, 55(mod 56).
2. Find the odd primes of which 35 is a quadratic residue.
( — j
= (-)(-)> an d both symbols must be +1 or both —1 for ( — J
x = +l(mod 10)
and one of
x = 1, 3, 9, 19, 25, 27(mod 28)
giving p = 1,9, 19, 29, 31, 59, 81, 109, 111, 121, 131, 139(mod 140), or p
satisfies one of the congruences
x = 3, 7(mod 10)
and one of
x = 5, 11, 13, 15, 17, 23(mod 28)
with the result that p = 13, 17, 23, 33, 43, 67, 73, 97, 107, 117, 123,
127 (mod 140).
EXERCISES
10. Prove that there are infinitely many primes of the form An + 1. (Assume
the number of these primes is finite and use them to construct an integer 4£ 2 + 1.
Consider the form of the prime factors of this integer.)
11. Show that there is an infinite number of primes of the form Sn + 1.
12. Prove that 3 is a primitive root of every prime of the form 2 2 " + 1 by considering
the quadratic character of 3 with respect to such a prime.
152 ELEMENTARY THEORY OF NUMBERS
following manner:
\p) ~ xpJ
where the symbols to the right of the equality sign are Legendre symbols.
W '
W
When P = pip 2 p r and Q = qiq 2 q s with the pi and qj,
• ' ' * • •
,
- (?) fe>
H«- (") - fe) fe) © (s) fe) fe)
Theorem 9-12. If m and n are prime to the positive odd integer P and
if m= n(mod P), then
(p-J
= ( p)*
?
-=- ) = (
— 1) (P-D/2
V[( Pi -l)/2]
(
— 1) *
, where i = 1, 2, . . . ,
r. But P = p xp 2 • " *
pr
QUADRATIC RESIDUES 153
i l i,k l
i<k
- P- 1
- O(mod 2), so that P= 1 + > (p.- l)(mod 4). Hence,
i =l
r
i -
pi -
P |j = (- l)<
1 >' 8
Theorem 9-14. If is a positive odd integer, f .
- 1)J{1 + (?>2
2
- 1)} • • • {1 + (p,* - 1)} = 1 + 2 (Pi
2
" 1) +
i =l
r r
1 (Pi
2
- i)fe 2
- 1)
+"••• + n fe
2
- !)• But since ^- 1 =
i,&=i z=i
P —
0(mod 8), it follows that P = 2
1 +
Y"\
> fe
2
- l)(mod 64), and
2
x—= 1
» =1
V Pi2 ~ 1
(mod 8). Hence, (^\ = (-1)Cp*-u/8.
(0-©©-©^©-(s)te)---(^"-
factoring (
p) in like manner and forming the pairs ( ) ( r we find
, where i = 1, 2, . . . , r and
1,3
j = 1, 2, . . . , *.
i = l
154 ELEMENTARY THEORY OF NUMBERS
evident that
r
(^ - i)(* - = - - i)}
J {(»
i) 1) (p<
J J
- p " !)fe- l)(mod8)
X(y
- (P- 1)
Jfo- l)(mod8)
Hence,
Therefore,
©®-<-» w
According to the definition of the Jacobi symbol, (^ ) is +1 when all
(?)
w—
I )
congruences
= +1 or when an even number are — 1. In the first case the
x2 = m(mod P) (7)
But in the second case the congruences (6) fail to have a solution for cer-
tain pi, and therefore (7) has no solution. Hence, if the Jacobi symbol
(AX?) - «•
and (-3- J = ( r) = — 1. Hence, (770) = — 1. Furthermore,
+1.
(A)(t)-
But
(?) = (I) " - 1 and '
so
(A) - -1 -
Hence '
(m) +1,
and therefore the given congruence has a solution.
Now consider the congruence x 2 = 21 (mod 253), where 253 is not a
/2l\ =
Hence, \kfo ) +1? but this is a Jacobi symbol, and we can reach no
conclusion as to the existence of a solution of the congruence. However,
tion of x = 21 (mod
2
11). Hence, there is no solution of the given
congruence.
EXERCISES
1. Apply both Jacobi and Legendre symbols to determine whether or not the con-
gruence x 2 S3 35 (mod 71) has a solution.
2. Evaluate the following symbols and interpret the results : ( q= > ( r^ry ) > ( ^rz )
•
the congruence x 2
= a(mod 2) has the solution x = l(mod 2), but if
a l(mod
ss 4), in which case there are two solutions 1 and 3 modulo 4.
Theorem If n > 3 and x = a(mod 2 n ) has a solution, then
2
9-16.
a ss l(mod 8).
Suppose x satisfies the congruence. Then x 2
= a(mod 2 n ), and there-
fore x a(mod 8)
2
ss But x is odd, and its square is, therefore, congruent
.
~
Therefore, x 2 = ^i(mod 2 n l ), or x 2 = — Xi(mod 2 n_1 ). But when x\
satisfies x 2
= a(mod 2 ),n — X\ does also. Consequently, all four integers
n~ l =
±X\, ±xi + 2 satisfy x 2
a(mod 2 n
), and they are incongruent
modulo 2n .
QUADRATIC RESIDUES 157
~
2n. Therefore, the 2 n odd positive integers less than 2 n separate into
1
2 n_3 sets of four such that all four integers in a set satisfy one and only one
~
of the 2 n 3 congruences x 2 = a (mod 2 n ) determined by the permissible
values of a.
Example. In the case of x 2 = a(mod 16), a can have only the values
1 and 9 modulo 16. The solutions of x 2 = l(mod 16) are 1, 7, 9, and 15
modulo 16, and those of x 2 = 9 (mod 16) are 3, 5, 11, and 13 modulo 16.
EXERCISE
First find the values that a can have in order that there be a solution of x 2 = a (mod
64), and then find all the solutions of these congruences.
CHAPTER 10
mining g(k) and sheds no light on the actual value of g(k). Since then
Hardy and Littlewood have developed by analytical means a formula
that determines an upper bound for g(k) for every k.
From these few remarks we can obtain some idea of the magnitude of
this problem, and certainly a perusal of a few of the original proofs will
give an appreciation of the ingenious adaptation of the tools of the theory
of functions of a complex variable to the problems of the integers. We
are not concerned here with the presentation of any of these powerful
methods, but we shall give two of Euler's* proofs that every prime of the
form 4n + 1 can be represented uniquely as a sum of two squares and then
reproduce a proof, due to Euler and Lagrange, f that uses only the ideas
of the classical theory of numbers to show that every integer can be
expressed as a sum of at most four squares.
Let us recognize first that the identity
formula gives but one representation of the product as a sum of two posi-
tive squares. Does the formula ever fail to give at least one solution
when (a, b) «= 1 and (c, d) — 1? In this case ac = bd, and ad = be.
But if ac = bd, then a = d and b = c, and so the two given sums are
If ad = be as well, then a = b = 1.
2 2
identical. Hence, in the single
case (1 + 1)(1 + 1) = 2 -f-0, the formula fails to give a sum of two
2
positive squares.
It is also apparent that when (a, b) = 1 and (c, d) = 1, the squares in
the expression for the result of the product need not be relatively prime,
for example, (8
2
+ 2
1 )(9
2
+ 2 2) = 70 2 + 25 2 . On the other hand, if
Euler's first proof of the fact that a prime of the form 4n + 1 can be
represented as a sum oftwo squares is a little cumbersome, but it is
instructive to study it and to compare it with the second, more elegant
proof which Euler published about 25 years later. The second proof
exemplifies the enormous improvement in the directness of the presenta-
tion that a mathematician often attains when the initial proof is reviewed.
Lemma 10-la. If a prime p = c 2 + d 2 and if there is a q > 1 such ,
If the prime p = c
2
+ d 2 then
, (c, d) = 1, and if pg = a2 + 52 , we have
c (a
2 2
+ fr
2
)
— a 2
(c
2
+ d 2
) = c
2
pq — 2
a p = mp
But
c {a
2 2
+ b
2
)
- a 2 (c 2 + d2) = b 2c 2 - a 2d 2 = (be - ad) (be + ad)
b = tc +r
and
a = —td-\-s
Then
cr = be — tc
2
and
ds = ad + id 2
so that
cr - - ds = be — ad — t(c
2
+ d2) = =
Hence,
cr = ds
r = dn and s = en
6 = kc + r
and
a = kd + s
give
cr = be — kc 2
and
ds = ad — kd 2
Hence,
cr + ds = be + ad — k(c 2 + d 2) =
and
cr = — ds
In this case
r = dn and 5 = — en
In the first case
pq = a2 + b
2
= (
— td-\-
en) + (tc + 2
dn) 2
= (r2+ n )(c + d 2 2 2
)
= p(t + n2 2
)
Consider Lemma 10-la, and let P = pip 2 Pk, where each prime ' ' '
= Qp < p
~2
Any common divisor of ri and r must divide Q, and thus the last equation 2
Lemma 10-2a, it is now evident that P has a prime factor pi that is not a
sum of two squares, and furthermore, pi < p/2. Using the fact that pi
divides a\ 2 +
we can repeat this process. The method, therefore,
bi
2
,
squares. But this statement is contrary to fact, for the prime factors of
all sums of two sufficiently small relatively prime squares are themselves
each of the pairs a and b, c and d, one integer is even while the other is
odd. Then
a2 _ C
2 = d2 _ h2
and
(a - c)(a +c) = \d - b)(d + b)
m(a + c) = n(d + b)
(r
2
+ s
2
)(m 2 + n 2) = mr +ms +nr +ns
2 2 2 2 2 2 2 2
= (a - c) + (d + 6) + (d -
2 2
6)
2
+ (a + c)
2
(r
2
+ s
2
)(m 2 + Q = a2 + 62
+
c
2
+ cP
4 2 2
= p
Thus, and s are even, p has been factored into the integers (r 2 + s 2 )/4
if r
and m + n 2 both of which are greater than 1. But if r and s are odd,
2
,
r and s cannot both be 1, nor can both m and n be 1, for in either case
2
(p /4) + 1 < p
2
. Thus mp < p 2 and m < p. Hence, , it is true that
there are integers a and b, with (a, b) = 1 and < a, b < (p — l)/2,
which satisfy the equation a 2
+ b
2
= mp, m being an integer in the
interval 1 < m < p. If m> 1, we shall show that we can produce a
positive integer mi < m such that rri\p is sum of two squares.
a
Set a = qim + ri and b = q2 m+ r2 , with |ri| and \r 2 not greater than \
m/2. As a result
a2 + b2 = n + 2
r22 +m 2
( qi
2
+ g2
2
) + 2m(r l9l + r 2q 2) (1)
and
mp = ri
2
+ r22 + mK
so that
fi
2
+ r22 = mim
But
ri
2
+ r22 < 2 feY
for not both |ri| and \r 2 \
can be m/2 because (a, b) = 1. Hence,
mim <
^ —
m 2
and
mi <m
Applying the identity exhibited just before Lemma 10-la, we have
(ri
2
+ r 2 )fei
2 2
+ g2
2
) = (r iqi + r 2q 2 ) 2
+ (nq 2 - r 2qi )
2
or
mmiqi 2 + ?2
2
) = s
2
+ t
2
(2)
where
s = ngi + r<# 2
and
t = r x qi — r 2 qi
mp = mim +m 2
(qi
2
+ <?2 )
2
+ 2ms
and
p = mi + m(qi 2 + q2
2
) + 2s
Therefore,
m x p = mi 2
+ mim(qi 2 + g2
2
) + 2miS
and, according to (2),
mp =x mi 2 + s
2
+ t
2
+ 2mis
or
mip = (mi -f s)
2
+ £
2
164 ELEMENTARY THEORY OF NUMBERS
Hence, it is clear that upon the assumption that m > 1 we have con-
structed another integer rrti < m such that mip is a sum of two squares.
We must conclude, therefore, that m 1. —
The unicity of this representation of the prime p = ^n -f- 1 was proved
at the end of the first proof of Theorem 10-1.
Recalling that the even prime 2 = l 2 + l 2 we shall now proceed to the ,
second problem stated above by showing in the following steps that any
odd prime can be expressed as a sum of four squares or fewer:
Lemma 10-16 (Euler's Identity). (xi + x£ -r-z + Z4 )G/i + 2/2 2 + 2
3
2 2 2
2/3 +2
= {x±yx + x y + x y + x y + (xiy — x y\ + x y± — x y
2/4 )
2
2 2 z z 4 4)
2
2 2 z 4 z)
2
+ (xiy — x y
5 x y — x y z + (xiy* — x y + x y — x y
x -f- 4 2 2 4)
2
A x 2 z z 2)
2
.
Xi + ix 2 x3 + 1x4 Vi
--
W2 -2/3 - iy* A - %B C -iD -
Xz + ixi Xi — ix 2 -
y* - iy* y\ + iyi -C -- iD A +iB
A + B + C + D'
2 2 2
where
A = xiyi x 2y 2 + xzyz + x y 4 4
B = xiy 2 x 2 yi + x y — x±yz z 4
than p.
Again, let yi same interval and form the
represent the integers in the
numbers —1 — y These integers are also incongruent modulo p, for
2
.
if — 1 — yi = — 1 —
2
yj (mod p), where i 7* j, then yf
2 — y^ = 0(mod p),
and we have seen that this congruence is impossible.
Because the Xi 2 and — 1 — y^ taken together form a set of p + 1
integers, two of them must be congruent modulo p. Therefore, some
x^ must be congruent to a particular — 1 — yj 2 Calling these integers .
x' as ?/
2
(mod p)
SOME FAMOUS PROBLEMS 165
and
x2 + y
2
+ l
2
+ 2
= 0(mod p)
so that x 2
+ y
2
+ l
2
+ 2
= tp, where t is a positive integer.
< p /4. Therefore, (p /4) + (p /4) +
and y 2 <
2 2 2 2
Moreover, x 2 p /^,
> 1 > tp. However, since p > 2, it is evident that
2 2
1 tp, and (p /2) -\-
( xi + V
a? 2 , / a?i — S2Y ,
/ ffs + gj V ,
(x3_-_Xi\
2
_ xi
2
x 22
\ 2 / "•"
\ 2 /
"*"
\ 2 /
"*"
\ 2 / '
2 ^ 2
#3 . Xi t
Thus there is an integer t/2 smaller than t and such that tp/2 is a sum of
then there exists a positive integer s less than t and such that st = yi
2
+
2/2
2
+ 2/3* + 2/4
2
.
\ Vi
2
— X ^ m °d 2
(
Hence,
4
V ?/,
2
= tp = 0(mod
Therefore, y x 2 + 2/2
2
+ y%
2
+ ?A
2
= s£. The integer s is not or each
2/» would be 0, and then each Xi would be divisible by t. In this case t 2
would divide tp, and t would divide p. Hence, t would be 1. Moreover,
4
since \y { \
< t/2, it follows that yi
2
< Z
2
/4 and V y- 1 < t
2
. Hence,
i=l
< t
2
,
and s < t. Consequently, 1 < s < t.
166 ELEMENTARY THEORY OF NUMBERS
xi
2
+ x22 + x, 2 +x = A
2
tp 3 <t < p
yi
2
+ yi
2
+ yz
2
+ yi = 2
st 1 < s < t
t
2
sp = (xtfji + x 2y 2 + x y + x y^) + (x y - x yi + x y — x yz)
z d A
2
x 2 2 z A 4
2
Xiyi +x 2 y2 + x y% + x±y± = Xi + x +
z
2
2
2
xz2 + x± 2 = tp = 0(mod t)
Also,
2
It is apparent, therefore, that t divides each of the four squares in the
right-hand member of (3) and that sp, with s < t, is a sum of four squares.
But this conclusion contradicts the fact that t was chosen the least posi-
tive integer such that tp is a sum of four squares. Hence, t = 1, and the
theorem is proved.
Theorem 10-3. Every integer is a sum of at most four positive
squares.
Upon factoring the given integer into primes, the theorem follows
immediately from Euler's identity.
It may also be added that we must use at least four positive squares to
express some integers as a sum of squares, for we shall show that no integer
that is congruent to 7 for the modulus 8 can be a sum of three squares.
Suppose that Xi 2 x 2 2 + x z 2 = n. Not all the x i} where i = 1, 2, 3,
+
can be even, nor can just one be, for n = 8k + 7 is odd. But if all the
Xi are odd so that Xi = l(mod 8), then xi + x 2 + £ 3 = 3 (mod 8).
2 2 2 2
EXERCISES
1. Prove that integers of the form 4 r (8n + 7) with r and n > cannot be expressed
as a sum of three squares.
2. Write (xi
2
+ x22 + x 32 + 2
rc 4 )
2
as a sum of three squares. What does the result
prove?
SOME FAMOUS PROBLEMS 167
x = 2kvw y = k(v 2 — w 2
) z = k(v 2 +w 2
)
EXERCISES
10-3. Fermat's Last Theorem. About 1637 Fermat stated that there
isno solution in positive integers of the equation x n + y n = z n if n > 2.
This theorem is known as Fermat's last theorem, and about it he wrote,
"I have discovered a truly remarkable proof but this margin is too small
to contain it." To this day mathematicians have been baffled by the
statement, for they have been able neither to prove nor to disprove the
general theorem. The equations (x m ) 4 + (y m ) 4 = (z m ) 4 and (x m ) p +
m p = (z m p show that the proof can be broken up into the cases in
(y ) )
+ y = z
4
xA 2
.
even, the other odd. Then the area of this triangle, which we assume is a
perfect square, is A = ab(a 2 — b 2 ) = r 2 Since (a, b) = 1, the integers .
a + b = m 2
+ n2 = u2
and
a — b = m — n2 = 2
v
2
As a result
2m = u 2 2
+ v
2
and
2n 2 = u — 2
v
2
= (u — v){u + v)
Thus (u, v) = 1, and the last equation shows that u — v and u + v are
even integers. Hence, n is even, and 2n = 2
8q
2
= (u — v)(u + v).
Therefore, one of the integers ——-— —-2—
1£ y
>
<££ —1_ p
is even. Accordingly, let
either
or
-^ =
U
2s 2 and ^ 2
= t*
^1 = t
2
and ^±1 = 2s<
Then
2n 2 = SsH'
and
n2 = 4sH'
u = 2s 2
+ t
2
and v = t
2 - 2s 2
u = 2s 2 + t
2
and v = 2s 2 - t
2
But m =
2
v
2
+ n2 = t* - 4sH 2 + 4s 4 + 4s 2 £ 2 = 2
(t ) Thus m
2
+ (2s 2 ) 2 .
If both p 2 + q
2
= m and p 2 — q 2 = n 2
2
, consider the right triangle
p — q and p + q*.
2 2 4
4 A
whose sides are 2p q , , Hence, the area is
p q (p
2 2 i
— q
A
) = p 2
q
2
m 2
n
But we have shown that if the sides are integers, the area cannot be a
perfect square. Consequently, there is no solution in integers of the
given set of equations.
10-5. The Generalized Wilson Theorem
integers less than m and
Theorem 10-8. The product of the positive
prime to m is congruent to — 1 modulo m if m = 4, p n or 2p n with p an ,
odd prime, but the product is congruent to + 1 modulo m for all other
moduli.
If ra = product 1 3 = — l(mod 4).
4, the
If m= p
n
t be a quadratic nonresidue of the odd prime p, and let
, let
Oi, where i = 1, 2,
n
(f>(p ), be the least positive integers forming a
. . . ,
reduced residue system modulo p n Then, for each a,-, the congruence .
ctiX = £(mod p ) has a solution x = a,- (mod p ) from the set of the a,, and
n n
for cti 2 f£ £(mod p). The integers a are, therefore, separated into 4>(p n )/2 {
If m= 2p n
be a quadratic nonresidue modulo p, and
, let s let t satisfy
both of the congruences
x = s(mod p)
x = l(mod 2)
~ 1)/2
P= ^ n >/ 2
(mod 2p n )
But t
(p = — l(mod p), and thus t^ pn)/2 = — l(mod n
p j. However,
£ is odd, and (j>(2p
n
) = <t>{p ).
n
Therefore, P = — l(mod 2p n ).
If m = > 2, then —1 is a quadratic nonresidue of 2 U
2U , where u .
pc-o/i = +i(modpi»0
172 ELEMENTARY THEORY OF NUMBERS
Moreover, t = 1 + p r k, so that t^
2p 2 p 3 m)/2 =
"
(1 + 2p 2 ps •
j t<i,(m)/2 = -f l (mod p 2
n2 n3 nr 2u ~ l
k)4>(m)/2 anc Furthermore,
p r } P2 Vr ) t ' ' '
•
1(2/2
- x 2 a) - {y x - Xia)\ <
ni
or
|(?/2
- 2/i) - (x 2 - Xi)a\ < m
an infinite number of pairs of integers r and s with s > that satisfy the
inequality < \r
2
- 2
s b\ < 1 + 2 \/b.
SOME FAMOUS PROBLEMS 173
—
mi
< |fl-«lV^I
—
mi
< \n — Si \/b\
for i = 1, 2, 3, . . . . This means we can find integers r -+i, s,+i that give t
Thus
\ri+1 — s i+1 y/b\ < \fi — Si y/b\
and in this way we can set up an infinite number of pairs of integers r», Si
Hence,
< \n
2
- Si b\
2
<— + 2-v 5<l+2v
2
/ /6
Therefore, there are infinitely many pairs of integral values of r and s with
s > 0, such that |r
2
— 2
s b\ lies between and 1+2 y/b.
Lemma 10-3c. If 6 is a positive integer that is not a square, there
exists an integer k ^ such that the equation x 2 — by 2 = k is satisfied by
an infinite number of pairs of integers x and y.
174 ELEMENTARY THEORY OF NUMBERS
^1^2 — 2/i2/2?> — Xi
2
— byi
2
ss 0(mod k)
and
xiy 2 — x 2y x = Xiiji — xiiji = 0(mod k)
Therefore, let
Hence,
Xi
2
— by i 2 = (u 2 — bv 2 )(x 2 2 — by 2 2 )
or
k = k(u 2 — 2
v b)
so that
u2 — bv 2 = 1
#i + 2/i V^> has the least positive value, then any solution x, y of the
equation is determined by the formula x + y s/b = ± (x± + 2/1 y/b) n
for n = 0, ±1, ±2, ... .
Oi +
1
and if xi, 2/1, is a solution of the given equation, then x*, y± determined by
X4 — 2/4 y/b = (xi — 2/1 y/b) n for n ,
= 1, 2, . . . , is also a solution of
x2 — fo/
2 = 1-
But the
pairs of integers x, y determined by the formula constitute all
the solutions of x 2 —
by 2 = 1, for if X, Y with both and positive is X Y
176 ELEMENTARY THEORY OF NUMBERS
that is,
Adding (4) and (5) shows that x' > 0, and subtracting (5) from (4) gives
< f
2y Vb, which implies that y' > 0. Under these circumstances,
however, it is impossible that x' + y' Vb be less than X\ + y\ Vb, for
EXERCISES
POLYNOMIALS
11-1. Integral Domains and Fields. Let us recall that the set of
rational integers has certain salient properties with respect to the oper-
ation of addition which can be summarized in the following manner:
1. The sum of two elements in a certain order is a unique element of
the set.
2.Addition is commutative.
3.Addition is associative.
4. Each element has an inverse with respect to addition.
2. Multiplication is commutative.
3. Multiplication is associative.
4. Multiplication is distributive with respect to addition.
5. There an element 1, called the unity element, or unity, such that
is
a •
1 = a for any a.
6. The elements obey the cancellation law, so that if ab = ac and
a ^ 0, then b = c.
a field. This set includes the field of the coefficients itself, and conse-
177
178 ELEMENTARY THEORY OF NUMBERS
quently it contains the numbers and 1, which are called the identity
elements with respect to addition and multiplication, respectively. Con-
stants not are polynomials of degree zero, whereas is said to have no
degree. The laws of elementary algebra show very easily that this set of
polynomials f(x) has the first nine characteristics enumerated above, but
we must clear up another idea before showing that the cancellation law
also holds.
Two polynomials in x are said to be identically equal if and only if they
have equal values for all values of the variable x. But a polynomial in x
of the nth degree with n > is not reduced to zero by more than n values
of x, and therefore f(x) vanishes identically if and only if all of its coeffi-
cients are zero. If, then, the product of two polynomials with coefficients
thermore, every polynomial f(x) divides zero, so that there can be but one
null polynomial.
Theorem 11-3. All the elements except zero of a field F are unit poly-
nomials of the set of polynomials with coefficients in F.
It is evident that a constant not zero of F divides every polynomial
whose coefficients are in this field. But a polynomial of degree n >
cannot divide any constant except zero.
A polynomial with coefficients in a field F whose leading coefficient is
unity is a monic polynomial.
The associates of a polynomial with coefficients in a field F are the prod-
ucts of that polynomial by the unit polynomials of the set of polynomials.
A polynomial with coefficients in F that is not a unit and that is divisi-
ble only by its associates and the units is a prime polynomial.
A polynomial with coefficients in F that is not zero, a unit, or a prime
polynomial is a composite polynomial.
A common divisor of two or more polynomials with coefficients in F is a
polynomial of the set that divides each of the given polynomials.
A greatest common divisor of two or more polynomials, not all zero, with
coefficients in F is a common divisor that is divisible by every common
divisor of the given polynomials. When the coefficients of the given poly-
nomials are in a field F, the monic polynomial that is an associate of a
greatest common divisor is called the greatest common divisor of the set.
If the greatest common divisor of two or more polynomials with coeffi-
cients in a field F is 1, the polynomials are relatively prime.
Theorem 11-4. If f(x) ^ and g(x) are polynomials with coefficients
in a field F, there exists a unique pair of polynomials q(x) and r(x) with
coefficients in F that satisfy the identity g(x) = f(x)q(x) + r(x) with
either r(x) = or of lower degree than fix).
~ =
If g(x) = a xn +
aix n 1 an + • • •
+ is of lower degree than f(x)
~l
b xm + bix m +•••+&•», take q(x) = and r(x) = g{x) and the
theorem is satisfied. Do likewise if g(x) = 0.
~
If g(x) is not of lower degree than f(x), take qi(x) = kx n m where ,
a = kb n ~
Then ri(x) = g(x) — kx f(x) is lower in degree than g(x)
m
.
and
g(x) = f(x)q 1 {x) + n(x)
If ri(x) =
or if its degree is lower than that of f(x) } the existence of the
pair of polynomials has been demonstrated, but if neither is the case,
repeat the operation, using f{x) and r±(x). Thus we obtain
Again, if r 2 (x) = or if its degree is lower than that of f(x), the required
180 ELEMENTARY THEORY OF NUMBERS
polynomials are qi(x) + #2(2) and r 2 (x), but if not, the process is repeated
until after a finite number of steps we obtain
r s _i(z) = f(x)q 8 (x) + r s (x)
Hence,
g(x) = f(x)[qi(x) + q 2 (x) +••+ q.(x)] + r a (x)
If Ri(x) f^ 0, solve for each Ri(x) that is not zero, and substitute the
expression in the succeeding equation of the algorithm. Thus when
R t+1 = 0, we find that
R {x) = g{x) -f(x)Q (x)
l 1
Hence if f(x) and g(x) are not relatively prime and if R t (x) is not a monic
polynomial, by dividing through by its leading coefficient, we have
1 = F(x)f(x) + G(x)g(x)
In the last case the term of highest degree of F(x) comes from the
product Qi(x)Q 2 (x) Q +i(x). The degree of Qi(x) is n — m, of
• • •
t
As a result Di(x) and Z>2(^) can differ only by a constant factor; that is,
Di(x) = cD 2 (x). But each one is a monic polynomial. Therefore,
c = 1, and Di(x) = D 2 (x).
Then
MiWW + f*(x)f t (x)F t (x) -/,(*)
Applying the distributive law, evident that f\ (x) divides /3 (x).
it is
only one pair of polynomials F(x) and G(x) with coefficients in F satisfying
the condition F(x)f(x) + G(x)g{x) =
and such that the degree of F(x) 1
But since f(x) and g(x) are relatively prime, g(x) divides F(x) — Fi(x).
Unless F(x) = F\(x) }
this division would be impossible, for the degree of
F{x) — Fi(x) is less than that of g(x). It is then obvious that G(x) =
(x 2 - 4x + 3)( + l) + (2.r - 6) (- | + lj = x - 3
and
(x 2 - 4x + 3)(-l) + (2x - 6)
©
I - ) = x - 3
When the field F containing the coefficients of f(x) is the set of complex
numbers, on the basis of the fundamental theorem of algebra, we know
POLYNOMIALS 183
that, except for the order of the factors, f(x) can be factored into linear
factors, each with leading coefficient unity and absolute term in F, and a
constant factor, in exactly one way. Hence, the identity
~ — — — —
fix) = a xn + aix n l
+ ' '• '
+ a>n cto(x r l )(x r 2) • • * (x r„)
and
f 2 (x) = b xm + b x x™- 1 +•+&.
with n > m, have integral coefficients that are relatively prime. Their
product necessarily has integral coefficients, but suppose that a prime p
divides each of these coefficients. Then there is a first a;, say a r and a ,
first bj, say 6S , that is not divisible by p. Now consider the coefficient of
a r + s bo + • • *
+ a r +ib s -i + a rb s + a r-ib s+ i + • • • + a r+s -m b m
184 ELEMENTARY THEORY OF NUMBERS
and p is a prime, then fi(x)f2 (x) = p[g(x)f 2 (x)] and the product is not
primitive.
Theorem 11-11. If f(x) is a polynomial with integral coefficients and
leading coefficient unity, fix) is factorable into the product of two monic
polynomials in the field of the rational numbers if and only if it is factor-
able in the domain of the rational integers.
Let f(x) = fi(x)f2 (x), where fi(x) and/2 (z) are monic polynomials with
rational coefficients, and suppose that not all the coefficients of the
factors are integers. Reduce all fractional coefficients to their lowest
terms, and let d\ and d 2 be the least common multiples of the denominators
of the coefficients of fi(x) and 2 (#), respectively. Then the coefficients
of both g(x) = difi(x) and h(x) = d 2f2 (x) are relatively prime integers.
Consequently, the product g(x)h(x) = did fi(x)f (x) is a primitive poly-
2 2
nomial. But then f(x) — fi(x)f2 (x) = g(x)h(x)/did cannot have integral
2
cpi(x)p 2 (x) • • •
p r (x) = kq 1 (x)q 2 (x) • • •
q s (x)
unique.
Theorem 11-14. If fi(x) and f2 (x) are integral polynomials, not both
zero,we can choose a greatest common divisor of them so that it is an
integral polynomial.
Since the coefficients of fi(x) and f 2 (x) are rational, their greatest
common divisor D(x) exists and can be written
^ = fl{x) m+ Mx) m
Multiply both members of this equation by the least common multiple of
d, g, and h. Thus
k,d(x) = fi(x)[k 2 g(x)] +f (x)[kzh(x)]
2
where kid(x) is an associate of the monic polynomial D(x) and has integral
coefficients.
Very often we use the primary associate of kid(x) in place of the greatest
common divisor of fi(x) and f 2 (x) even though we may not be able to
write it in the above form with k 2 g(x) and k z h(x) integral polynomials.
Example. The greatest common divisor x — § of 3a; 3 — 2x 2 — 3x + 2
and 3a; 2 — 8a; + 4 can be expressed in the form
x -#= i(3a;
3
- 2a;
2
- 3a; + 2) - £(a + 2)(3a; 2 - Sx + 4)
186 ELEMENTARY THEORY OF NUMBERS
EXERCISES
are rational integers. If a is a rational integer, apply this definition to the roots of
the equation x m = a and consider the problem of factoring a.
x x2 x2 +x x2 + 2x x2 + Sx x2 + 4z
x +1 x2 +l x2 +x +1 x2 + 2x + 1 x 2
+ Sx + 1 ic
2
+ 4z +1
x +2 x2 +2 x2 +x +2 z2 + 2z + 2 z2 + 3x + 2 z2 + 4x +2
x +3 x2 +3 x2 +x +3 x2 + 2x + 3 x2 + 3x + 3 z2 + 4z +3
£ +4 z 2
+4 £2 +z +4 z2 + 2z + 4 a;
2
+ 3z + 4 z2 + 4z +4
Of these the following are prime polynomials modulo 5:
x x +3 x 2
+ 3 x 2
+ 2^+3 x 2
+ 4x + l
z-fl x +4 z2 +
-f- £ 1 x2 + 2^ + 4
£ + 2 z2 +2 x2 + + ^ 2 z2 + 3z + 4
The associates of this set of primary prime polynomials modulo 5 repre-
sent the incongruent prime polynomials modulo 5 of the first and second
degree.
A greatest common
divisor modulo p, a prime, of a set of integral poly-
nomials, not congruent to zero modulo p, is a common divisor of the
all
Then every common divisor modulo p of fi(x) and/2 (V) divides r k (x), and
r k (x) is a common divisor modulo p of these polynomials. Therefore,
r k (x) is a greatest common divisor modulo p offi(x) and Or). 2 By solving
successively for the n{x) in terms of fi(x) and f 2 (x), we find
5 —
algorithm to a; x and a; 5 + x z + x 2 — x + 3 shows that D(x) = x 2 —
3x + 2 (mod 5) and therefore that the only distinct solutions of the given
congruence are x = 1, x = 2(mod 5). But x b + x z + a; 2 — x + 3 =
3a; + 2)(x + 3a; + Sx + 4) (mod 5). The congruence z 3 + 3a; 2
2 - 3 2
(a;
EXERCISES
PARTITIONS
ing the theory concerned with the separation of an integer into all possible
summands selected from a given set, for example, the representation of 4
by 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1, where selections are
made from 1, 2, 3, and 4. To Euler, however, is due a large part of the
basic theory. This additive theory of numbers is a difficult subject. We
shall develop only the fundamental ideas. The student can refer to the
work of G. H. Hardy, one of the modern experts in this field, for an
extensive treatment of this topic.
If from any set of positive integers a», where i = 1, 2, 3, . . . , finite
or infinite, we select m numbers so that n = ax + a2 + •
+
a m the
•
,
Q(n, U, q).
12-2. Partitions with Repetitions. To separate n into m parts with
repetitions let each of the m parts have one unit, and then distribute the
remaining n — m units to one part, to two parts, . . . , to m parts.
Thus when n > m and the selections are from the positive integers, we
have
P(n, m) = P(n - m, 1) + P(n - m, 2) +
+ P(n — m, m)
But then
P(n - 1, m- 1) = P(n - m, 1) + P(n - m, 2) + • •
•
+ P(n — m, m— 1)
Hence,
P(n, m) = P(n — 1, m— 1) + P(n — m, m)
equal to P(n — 1, m— 1) +
P(n — m, m).
Example. To find the number of partitions of 7 into three parts, we
find P(7, 3) = P(6, 2) + P(4, 3). Repeating the application of the
recursion formula of Theorem 12-1, we obtain
Hence,
P(7, 3) = 4
1 + (2n - 1)
2 + (2w - 2)
n -f- (2n — n)
1 + 2n
2 + (2n - 1)
n + (n + 1)
m, the Values of n
number
of parts 1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4 4 5 5 6
3 1 1 2 3 4 5 7 8 10 12
4 1 1 2 3 5 6 9 11 15
5 1 1 2 3 5 7 10 13
6 1 1 2 3 5 7 11
7 1 1 2 3 5 7
8 1 1 2 3 5
9 1 1 2 3
and P(n, n — =
account for the two diagonals of l's. Passing to
1) 1
the second row, to find P(3, 2), we merely add the numbers in the column
under 3-2=1. To find P(4, 2), add the numbers under = 2, 4-2
etc. To write the third row, sum the numbers under 4 — 3 = 1 for
P(4, 3), the numbers under 5 — 3 = 2 for P(5, 3), the numbers in the
first three rows under 6 — 3 = 3 for P(6, 3), the numbers in the first three
and always employ at least one q, and then remove one q from each of the
from all possible selections of one, two, and three distinct summands from
the set 1, 2, 3. Consequently, the coefficient 2 of x 3 gives the number of
ways 3 can be produced by adding together distinct integers selected from
1, 2, and 3. Similarly the coefficient of x n in the expansion of (1 +
x)(l -f- x 2 ) (1 + x q ) is the number of partitions of n into dis-
- - •
194 ELEMENTARY THEORY OF NUMBERS
zx nis multiplied by z
m ~ l to produce z mx n z 2x n by z m ~ 2 etc. Thus the
; , ;
quotient 1/(1 — m
x ), is absolutely convergent for < x < 1 enabled
Kronecker* to prove that the coefficients of the expansion of the gener-
ating function 1/(1 — x)(l — x 2 )(l — x z ) give the number of par- • • •
first n +
would merely reproduce the product of the first n
1 factors
factors, and the next term would add n + 1 to each of the exponents of x
already produced so that the resulting exponents would exceed n. It is
evident also that all succeeding exponents so derived would exceed n.
Moreover, any term developed from the product of the first n factors is
the result of selecting exactly one term from each of these factors. The
choice can be represented as the selection of one of each of the factors
x a x 2b x 3c
, ,x nk where the values of the integers a, 26, Be, . . . , rik
, . . . , ,
2b as the sum of b 2 s, 3c as the sum of c 3's, etc. Each time the sum of
?
(1 + x )(l + z )(l +
3 4
Z 5)
Then the expansion is
the partitions of n into odd integers with repetitions permitted and that
1/(1 — x 2 )(l — x A )(l — x 6) • - •
does the same when the parts are even.
EXERCISES
4. Show that the number of partitions of n in terms of odd integers with repetitions
isequal to Q(n, U).
5. Write a generating function which will enumerate the partitions of n into parts
n — r into even parts that do not exceed 2q with repetitions permitted. Show also
that when n — r is even, the same function enumerates the partitions of (n — r)/2
into parts not larger than m
with repetitions.
7. Find a method for listing all the partitions of n into m parts by starting with
Carmichael, R. D., "The Theory of Numbers," John Wiley & Sons, Inc., New
York, 1914.
Chrystal, G., "Algebra," A. & C. Black, Ltd., London, Vol. I, 1931, Vol. II,
1932.
Dickson, L. E., "History of the Theory of Numbers," Carnegie Institution of
Washington, Washington, D.C., 1920.
, "Introduction to the Theory of Numbers," University of Chicago Press,
Chicago, 1929.
, "Studies in the Theory of Numbers," University of Chicago Press,
Chicago, 1930.
, "Modern Elementary Theory of Numbers," University of Chicago
Press, Chicago, 1939.
Hancock, H., "Foundations of the Theory of Algebraic Numbers," The Mac-
millan Company, New York, Vol. I, 1931, Vol. II, 1932.
Hardy, G. H., "Some Famous Problems of the Theory of Numbers," Oxford
University Press, New York, 1920.
and E. M. Wright, "The Theory of Numbers," Oxford University Press,
New York, 1938.
Hecke, E., "Theorie der algebraischen Zahlen," Akademische Verlagsgesell-
schaft m.b.H., Leipzig, 1923.
Kraitchik, M., "Theorie des nombres," Gauthier-Villars & Cie, Paris, Vol. I,
Diophantine equations, solutions of, 16, Fermat, P., 30, 37, 88, 89, 105
17, 19, 21 last theorem, 168
Diophantus, 1, 16, 88 method of descent, 30, 168
"Arithmetica," 169 Fermat numbers, 32
Dirichlet, L., 27, 172 Field, 177
Discrete set, 3 Finite induction, 4, 10-11
" Disquisitiones arithmeticae," 136 Form, 14
Distribution of primes, 50, 51 degree of, 14
Distributive law, 3, 177 linear, 14r-16
Division, 7, 178 quadratic, 46
by 3, 55 Franqui, B., 37n.
by 8, 9, and 11, 56 Fundamental theorem of arithmetic, 29
modulo ra, 55, 57, 72
Divisor, 7
common, 7 Garcia, M., 37n.
greatest, 7, 14-15, 18, 62, 179, 180, Gauss, C., 50, 53, 107, 136
185, 187, 188 law of quadratic reciprocity, 145-147
Divisors, of an integer, 34 lemma of, 141
number 34-35of, Goldbach, C., 51
sum of, 34-35 Goldberg, B., 127
of zero, 57, 178 Greater than, 3
Greatest common divisor, 7, 14-15, 18,
62, 179, 180, 185, 187,188
Egyptians, 1, 39
used for solving congruences, 188
Eisenstein, R. G., 144
Greeks, 1, 16
"Elements," 9, 139
Gupta, H., 37n.
Equals, 4
Equivalent congruences, 68-70, 91
Eratosthenes, 25
Hancock, H., 197
Erdos, P., 27, 50
Hardy, G. H., 158n., 190, 197
Erlerus, H. G., 103
Heaslet, M., 198
Euclid, 9, 36
Hecke, E., 197
"Elements," 9, 139
Hilbert, D., 158
formula for perfect numbers, 36
Hindu- Arabic system, 38
theorem, 9, 14
Hindus, 1, 172
Euclidean algorithm, 31
Euler, L., 36, 46, 58, 159
criterion for solvability of x n sb
Ideals, 168
c(mod m), 129, 136
Identical congruence, 66
identity, 164
Identically equal polynomials, 67, 178
<t>
function, 58-60, 96, 106
Identity element, 178
Even integer, 10
Incongruent integers, 53
Exponent, of a prime contained in n!,
Index of n, 125
40-43
Indicator, 58
to which an integer belongs, 100
Indices, 125-131
used in solving congruences, 127-129
Factor, 178
7, Institute forAdvanced Study, 40
common, 7 Integer, associate of, 8
greatest, 7 divisors of, 34-35
(See also Divisor) expressed as a sum, 190
of a polynomial, 74, 178 of 4 squares, 158, 164-166
Factorization, 28-30, 183-185 in terms of a base, 37
INDEX 201
complete, 54 <r(m), 34
least numerical values, 63 r(m), 34
reduced, 54 Symmetric property, 4, 55
Riemann, G., 50
Roots, primitive (see Primitive roots) Table, of indices for prime 193, 132-133
of primes, 52
Taylor's theorem, 77, 86
Sarrus, F., 88 Tchebysheff, P., 50
Scale of notation, 37-40 Telephone cables, 113
ScientificAmerican, 40n. Transitivity, 4, 55
Selberg, A., 27, 50
Sequence, 4
Uhler, H. S., 37
Shapiro, H. N., 27
Unique factorization, 28-30, 183-185
Sieve of Eratosthenes, 25
Unit, 8, 178, 186
Simultaneous congruences, 79-83
Unit polynomial, 178, 179
Single-valued function, 58
Unity, 177
Smith, D. E., 197
Unity element, 177
Smith, H. J. S., 21n.
Uspensky, J., 198
Solution, of f(x) = 0(mod p°), 85-86
of ax = b (mod m), 89
Vandiver, H. S., 168
of ax + by = n, 19-20
Vinogradov, I., 51
of x n + yn = zn , 168
Solutions, of Diophantine equations, 16,
17, 19, 21 Wallis,J., 172
of f(x) = 0(mod
p), 75, 91, 92, 188
Waring, E., 158
multiplicity of, 76-78 Wertheim, G., 127
y = z 167
of x 2 +2 2
,
Wilson's theorem, 92-93, 136
of x 2 - by 2 = 1, 175 generalization of, 170-172
Squares, integers that are, 12 Wright, E. M., 46n., 197
primes between, 51 Wright, H. N., 198
Stewart, N., 198
Substitution, 4, 55 Zassenhaus, H., 27
Subtraction, 3, 5, 54 Zeller, C., 145
Sum, of the divisors of an integer, 34-35 Zero, 1, 4-5, 178
over the divisors of an integer, 60, 62 divisors of, 57, 178
of 2 squares, 159-164 no degree, 178
of 4 squares, 158, 164-166 as null element, 8