A.

WElL
NUMBER THEORY FOR BEGINNERS
I
We assume as known the concepts of "set" and "subset";
E means "element of". We use Z for the set of all
integers, and Q for the set of all rational numbers. We
assume the basic properties of integers and of rational
numbers:
(1) (x + y)+ z = x+(y + z).
(2) x+y=y+x.
(3) The equation a + x = b has a unique solution x (in Z, if
a,b are in Z; in Q, if they are in Q).
(4) O+x=x.
(1') (xy)z = x(yz).
(2') xy=yx.
(3') The equation ax= b has a unique solution x in Q, if
a,b are in Q and a=t=O.
(4') lx= x.
(5) x(y + z) = xy + xz (this is the "distributive law").
2
The unique solution of a+ x = b is written b- a. For
a=FO, the unique solution of ax= b is written .!!__
a
A rational number is positive ( > 0) or negative ( < 0);
only 0 is both; b>a (or a<b) means b-a>O; b>a (or
a<b) means b>a, b=Fa.lf x>O andy>O, then x+y>O
and xy>O.
If a,b,x are integers, and b =ax, b is said to be a
multiple of a; a is said to divide b or to be a divisor of b;
when that is so, we write alb.
Finally, we have:
(6) Any non-empty set of positive integers contains a least
integer.
In fact, such a set contains some integer n; then the
first one among the integers 0, 1, . .. ,n -1, n to be con-
tained in the set has the property in question. An equiv-
alent form of (6) is the "principle of mathematical induc-
tion":
(6') If a statement about a positive integer x is true for
x = 0, and its truth for all x <n implies its truth for
x = n, then it is true for all x.
PROOF. Call F the set consisting of the positive integers
for which the statement is not true. If F is not empty,
apply (6) to it; the conclusion contradicts the assumption
in (6').
ExERCISES
1.1. Show that the relation (-1)(-1)=+1 is a consequence
of the distributive law.
I
3
1.2. Prove that any integer x > I has either a divisor > 1 and
< Vx or no divisor > I and <x (in the latter case it is
called a prime; cf. IV).
1.3. Prove by induction that
J3+ 23+ +n3=[ n(n
2
+I) r
1.4. Prove by induction that 4
2
n+
1
+3n+l is a multiple of 13 for
n>O.
1.5. If one is a balance, and n weights of I, 3, 32, ... , 3n -t
lb .. show that it is possible, by placing some
m one pan and some in the other, to weigh out any
of N_ lb., with N an integer > I and < 1/2 (3n -1)
(Hmt: constder all sums of the form
eo+ 3el +32e2 + ... +3n-le
n-1'
where each e; is 0, +I or - 1).
1.6. Show that the number of terms in any polynomial of
degree d in n variables is at most ( n +d)! (Hint: use
. d . d nld!
m uct10n on , and observe that the number of terms in a
homogeneous polynomial of degree d in n variables is the
same as that of a polynomial of degree din n- I variables).
II
Lemma. Let d, a be integers, d > 0. Then there exists a
unique largest multiple dq of d which is <a; it can be
characterized by dq<a<d(q+l), or also by a=dq+r,
O<r<d.
(In that relation, r is called the remainder of the divi-
sion of a by d; dis called the divisor, and q the quotient).
PROOF. The set of integers of the form a-dz with z EZ
contains positive integers, since z can be taken negative
and large in absolute value (i.e. z = - N, with N a large
positive integer). Apply (6) of I to the set of all positive
integers which can be written in that form; take its
smallest element r, and write it as a- dq; this is 0 and
< d, since otherwise a - d( q + 1) would belong to the same
set and would be <r. 0
Theorem 11.1. Let M be a non-empty set of integers, closed
under subtraction. Then there exists a unique m 0 such
that M is the set of all multiples of m: M = { mz} z EZ = mZ.
5
6 II
PROOF. If x EM, then, by assumption, 0 = x- x EM and
-x=O-xEM.If alsoyEM, theny+x=y-(-x)EM,
so that M is also closed under addition. If x EM and
nx EM, where n is any positive integer, then (n + l)x =
nx + x EM; therefore, by induction, nx EM for all n ~ 0,
hence also for all n EZ. Finally, all linear combinations of
elements of M with integral coefficients are in M; as this
property of M obviously implies that M is closed under
addition and subtraction, it is equivalent with our
assumption on M.
If M = {0}, the theorem is true with m = 0. If not, the
set of elements > 0 in M cannot be empty; take for m the
smallest one. All multiples of m are then in M. For any
x EM, apply the lemma and write x =my+ r with
0 <r <m; then r= x- my is in M. In view of the defini-
tion of m, this implies r = 0, x = my. Therefore M = mZ.
Conversely, since m is the smallest element > 0 in mZ, it
is uniquely determined when M is given.
Corollary 1. Let a, b, ... , c be integers in any (finite) num-
ber. Then there is a unique integer d ~ 0 such that the set of
all linear combinations ax+ by+ + cz of a, b, ... , c with
integral coefficients x,y, ... ,z is the set of all multiples of d.
PROOF. Apply theorem 11.1 to that set.
0
Corollary 2. Assumptions and notations being the same as
in corollary 1, d is a divisor of each one of the integers
a,b, .. . ,c, and every common divisor of these integers is a
divisor of d.
PROOF. Each one of the integers a, b, ... , c belongs to the
set of their linear combinations. Conversely, every com-
mon divisor of a,b, ... ,c is a divisor of every one of their
linear combinations, hence in particular of d.
II
7
Definition. The integer d defined in the corollaries of
theorem 11.1 is called the greatest common divisor (or in
short the g.c.d.) of a,b, ... ,c; it is denoted by (a,b, ... ,c).
As the g.c.d. (a,b, ... ,c) belongs to the set of linear
combinations of a, b, ... , c (since it is the smallest element
>0 of that set, unless a,b, .. . ,care all 0), it can be written
in the form
(a,b, ... ,c)=ax
0
+by
0
+ +cz
0
where x
0
,y
0
, ... ,z
0
are all integers.
EXERCISES
11.1. Prove that (a,b,c)=((a,b),c)=(a,(b,c)).
11.2. Prove that, in the "series of Fibonacci" 1,2,3,5,8, 13, ... ,
in which each term after the second is the sum of the two
preceding ones, every two consecutive terms have a g.c.d.
equal to I.
11.3. Ifp,q,r,s are integers such thatps-qr= I, and a,b,a',b'
are integers such that
a'=pa+ qb, b'= ra+sb,
~ r o v that (a,b)=(a',b') (Hint: solve the last two equa-
tlons for a,b).
11.4. Let_ a,b be two integers >0. Put a
0
=a, a
1
=b; for n ;;.I,
defme an+t by an_ 1=anqn+an+t O<an+t<an, provided
an> 0. Prove that there exists N ;;. I such that aN+
1
= 0,
and that aN is then equal to (a, b).
11.5. Notations being as in exercise 11.4, prove that an can be
written in the form ax+by, with integral x,y, for all n;;.O
and <N.
8
II
11.6. Use the procedure described in exercises 11.4, 11.5 to find
(a,b) and to solve ax+by=(a,b) in each one of the
following cases: (i) a=56, b=35; (ii) a=309, b= 186;
(iii) a= 1024, b = 729.
11.7. If a,b, ... ,c,m are integers, and m>O, show that
(ma,mb, ... ,mc)= m(a,b, ... ,c).
11.8. Prove that every rational number can be written in one
and only one way as m with (m,n)= I and n >0.
n
III
Definition. Integers a, b, ... , c are called mutually rela-
tively prime if their g.c.d. is 1.
In other words, they are mutually relatively prime if
they have no other common positive divisor than 1.
If two integers a, b are mutually relatively prime, then a
is said to be prime to b, and b prime to a; when that is so,
every divisor of a is also prime to b, and every divisor of b
is prime to a.
Theorem 111.1. Integers a, b, ... , c are mutually relatively
prime if and only if the equation ax+ by+ + cz = 1 has
a solution in integers x,y, ... ,z.
In fact, if (a,b, ... ,c)= 1, then, by corollary 1 of theo-
rem II.l, the equation in question has a solution. Con-
versely, if it has a solution, then every common divisor
d > 0 of a, b, ... , c must divide 1 and must therefore be 1.
9
10
III
Corollary. If d is the g.c.d. of integers a,b, ... ,c, then
abc II tt.
d, d, ... , d are mutua 0' re atzve [)' pnme.
This follows at once from the fact that d can be written
in the form ax
0
+ by
0
+ + cz
0

Theorem 111.2. If a, b, c are integers such that a is prime to
b and divides be, then a divides c.
As (a,b)= 1, we can solve ax+by= 1. Then we have
c = c(ax +by)= a( ex) +(bc)y.
As a divides both terms in the right-hand side, it divides
c.
Corollary 1. If a,b,c are integers, and if a is prime both to
b and to c, it is prime io be.
If d is a positive common divisor of a and of be, it is
prime to b (since it divides a) and must therefore divide c,
by theorem 111.2. As (a,c)= 1, d must be 1.
Corollary 2. If an integer is prime to each one of the
integers a,b, ... ,c, it is prime to their product.
This follows from corollary 1 by induction on the
number of factors in that product.
EXERCISES
III. I. If (a,b)= I and both a and b divide c, show that ab
divides c.
111.2. If m > I and a is prime to m, show that the remainders
III 11
obtained by dividing a,2a, ... ,(m-I)a by m (cf. II,
lemma) are the numbers 1,2, ... ,m-l, in some order.
111.3. Show that, if N is an integer >0, either it is a "perfect
square" (i.e. of the form n
2
, where n is an integer >0) or
VIii is not a rational number (Hint: use exercise 11.8).
111.4. Any integer >I which is not a power of 2 can be written
as the sum of (two or more) consecutive integers.
111.5. If a,b are positive integers, and (a,b)= I, show that every
integer ;;. ab can be written in the form ax+ by with
positive integers x,y.
111.6. Using exercise 111.5 and induction on m, show that, if
al>a
2
, ,am are positive integers and d=(a
1
,a
2
, ,am),
every sufficiently large multiple of d can be written in the
form a
1
x
1
+ a
2
x
2
+ + amxm, where the X; are positive
integers.
IV
Definition. An integer p > 1 is called a prime if it has no
other positive divisor than itself and 1.
Every integer > 1 has at least one prime divisor, viz., its
smallest divisor > 1. If a is any integer, and p is a prime,
then either p divides a or it is prime to a.
Theorem IV.l. If a prime divides the product of some
integers, it divides at least one of the factors.
For otherwise it would be prime to all those factors,
and therefore, by corollary 2 of theorem 111.2, it would be
prime to their product.
Theorem IV.2. Every integer > 1 can be written as a
product of primes; it can be so written in only one way
except for the order of the factors.
13
14
IV
Take a> 1; call p a prime divisor of a. If a= p, the
theorem holds for a; if not, ; is > 1 and <a; if the first
statement in the theorem holds for !!:.., it holds for a.
p
Therefore that statement follows, by induction on a.
The second statement can also be proved by induction,
as follows. Assume that a is written in two different ways
as a product of primes, say as a = pq ... r and as a=
p' q' ... s'; asp divides a, theorem IV.l implies that p must
divide one of the primes p',q', ... ,s', say p'. Then p=p';
applying the second part of the theorem to !!:._, we see that
p .
q', ... ,s' must be the same as q, ... ,r, except for then
order. By induction, this proves the second part.
It is worth while to give another proof. Write a as a
product of primes, a= pq ... r; let P be any prime; let n be
the number of times that P occurs among the factors
p,q, ... ,r of a. Then a is a multiple of pn; on the
hand since a p -n is a product of primes other than P, 1t
is a multiple of P, by theorem IV.l, and therefore a is
not a multiple of pn +I. Thus n is uniquely determined as
the largest integer such that pn divides a; we can write
n = vp(a). Thus, for any two ways of writing a as a
product of primes, the same primes must occur, and
occur the same number of times in both products; th1s
again proves the second part of our theorem.
2 is a prime; it is the only even prime; all others are
odd. The first ten primes are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Let PI= 2,p
2
,p
3
, be all the primes in their natural (i.e.
increasing) order. Let a be any integer ;;;. 1; for each i;;;. 1,
let a be the number of times that P; occurs among the
I
IV
15
prime factors of a when a is written as a product of such
factors (with a;= 0 if P; does not divide a). Then we have
provided r has been taken large enough (i.e. so large that
all distinct prime divisors of a occur among pi,p
2
, ,pr).
Theorem IV.3. There are infinitely many primes.
In fact, if p, q, ... , r are primes in any finite number, any
prime divisor of pq ... r+ 1 must be distinct fromp,q, ... ,r.
(This is Euclid's proof for that theorem; for other proofs,
cf. the exercises).
EXERCISES
IV.l. Let n be an integer ;;;. I, and p a prime. If for any rational
number x we denote by [x] the largest integer <x, show
that the largest integer N such that p N divides n! is given
by
IV.2. Prove that, if a,b, ... ,c are integers ;;;.I, then
(a+b+ +c)!
a!b!. .. c!
is an integer. (Hint: using ex. IV.l, show that every prime
occurs at least as many times in the numerator as in the
denominator).
IV.3. If a,m,n are positive integers, and m=l=n, show that the
g.c.d. of a
2
m + I and a
2
" + I is I or 2 according as a is even
or odd (Hint: use the fact that a
2
"- I is a multiple of
a
2
m +I for n >m). From this, deduce the existence of
infinitely many primes.
16
IV
IV.4. If a=paq/3 ... rr, where p,q, ... ,r are distinct primes and
a, /3, ... , 'I are positive integers, prove that the number of
distinct divisors of a, including a and I, is
(a+ I)( f3 + I) ... ( y + I)
and that their sum is
pa+t_l q/3+1_1 ,r+t_l
p-I . q-I ... r-I .
IV.5. Prove that, if D is the number of distinct divisors of a,
their product is aD/
2

IV.6. If n,a,b, ... ,c are integers >I, then the number of dis-
tinct integers of the form aab/3 ... c
1
which are <n (where
a,f3, ... ,y are positive integers) is
<(I+ logn)(t+ logn) (t+ logn).
loga Iogb loge
Using this fact, and the fact that
lim (Iognf =0
n ~ o o n
for every r >0, prove that the number of primes is infinite
(Hint: assuming it to be finite, take for a,b, ... ,c all the
distinct primes).
IV.7. If (a,b)= I and a
2
-b
2
is a "perfect square" (cf. ex. 111.3),
show that either a+ b and a- b are perfect squares, or
each is twice a perfect square (Hint: show that the g.c.d.
of a + b and a- b is I or 2).
V
Definition. A commutative (or "abelian") group is a set
G, together with a binary operation between elements of
G, satisfying the following axioms (in which the group
operation is denoted by + ):
I (Associativity). ( +y)+z=x+(y+z) for all x,y,z in
G.
II (Commutativity). + y = y + x for all x,y in G.
III If x,y are in G, t e equation x + z = y has a unique
solution z in G ( itten z = y- x).
IV There is an eleme t in G, called the neutral element
(and denoted by such that 0 + x = x for all x in G.
For instance, the integers, the rational numbers (and
, the real numbers) are commutative groups under the
'operation of addition. There are of course many cases of
commutative groups where the group operation is not
written additively, i.e. is not denoted by +; then the
17
18
V
notations y- x in III, and 0 in IV, are to be suitably
modified. If the operation is written as a multiplication,
then one usually writes y , or y / x, or y x-I, for the
X
element z in III, and 1 for the neutral element in IV.
Non-zero rational numbers give an example of a com-
mutative group under multiplication.
In the present book, no groups will occur, other than
commutative groups; therefore the word "commutative"
will mostly be omitted. A subset of a group G which
makes up a group under the same binary operation as G
is called a subgroup of G. If G is written additively, a
subset of G is a subgroup if and only if it is closed under
addition and subtraction, or even merely under subtrac-
tion (cf. the proof of theorem 11.1). Theorem 11.1 may be
expressed concisely by saying that every subgroup of Z is
of the form mZ with m > 0.
Examples will now be given of finite groups.
Definition. If m,x,y are integers and m > 0, x andy are
said to be congruent modulo m if x-y is a multiple of m;
then one writes x y (mod m), or more briefly x y (m).
The lemma in II shows that every integer is con-
gruent modulo m to one and only one of the integers
0, 1, ... ,m -1, and that two integers are congruent modulo
m if and only if they have the same remainder in the
division by m.
The relation of congruence modulo m has the following
properties:
(A) (Reflexivity) x=x (mod m);
(B) (Transitivity) x y and y=z (mod m) implies x=z
(mod m);
(C) (Symmetry) x y (mod m) impliesy=x (mod m).
V
19
(D) x y, x' y' (mod m) implies xx' yy' (mod m).
(E) x y, x' y' (mod m) implies xx' yy' (mod m).
(F) Let d > 0 divide m, x andy; then x y (mod m) if and
only if = (mod ; ).
As to (E), it is a consequence of the identity
xx'-yy' = x(x'-y') + (x- y)y';
verification of all the other statements is immediate.
Properties (A), (B), (C) are expressed by saying that the
relation of congruence modulo m is an "equivalence rela-
tion" between integers.
Definition. A congruence class of integers modulo m is a
set consisting of all the integers which are congruent to a
given one modulo m.
If x is any integer, we write (x mod m) (or simply (x) if
no ambiguity can occur) for congruence class of the
integers congruent to x moduloyn. By (A), x belongs to
the class (x mod m); it is calle a representative of that
class. From (A), (B), (C), it follo s that any two classes
(x mod m), (y mod m) coincide "f x -y (mod m) and are
disjoint (i.e., have no element in c mmon) otherwise. Thus
the set of all integers is separate into m disjoint classes
(0 mod m), (1 mod m), ... ,(m-1/mod m).
We define the addition of congruence classes by put-
ting:
(x mod m)+(y mod m)=(x+y mod m);
this is meaningful, for (D) shows that the right-hand side
depends only upon the two classes in the left-hand side
20
V
and not upon the choice of the representatives x,y for
these classes.
Theorem V.l. For any integer m > 0, the congruence classes
modulo m, under addition, make up a commutative group of
m elements.
It is immediate, in fact, that the equation
( x mod m) + ( z mod m) = (y mod m ),
for given x,y, has the unique solution (y-x mod m), and
that (0 mod m) has the property required of the neutral
element.
EXERCISES
V.I. If x
1
, ... ,xm are m integers, show that the sum of a suitable
non-empty subset of that set is a multiple of m (Hint:
consider the distinct classes modulo m among those de-
termined by O,x
1
,x
1
+x
2
, ... ,x
1
+x
2
+ +xm)
V.2. Prove that every "perfect square" (cf. ex. 111.3) is con-
gruent to 0, I or 4 modulo 8.
V.3. Prove by induction that, if n is a positive integer, then
2
2
n+
1
=9n
2
-3n+2 (mod 54).
V.4. Show that, if x,y,z are integers, and x
2
+y
2
=z
2
, then
xyz=O (mod 60).
V.5. If x
0
,x
1
, ... ,xn are integers, show that
x
0
+I0x
1
+ +Ionxn=x
0
+x
1
+ +xn (mod9).
V.6. Show that a necessary and sufficient condition for the pair
of congruences x=a (mod m), x=b (mod n) to have a
solution is that a=b (mod d), where d=(m,n). If d= I,
show that the solution is unique modulo mn.
V 21
V.7. If n is an integer > 0, show that any n + I of the first 2n
integers contain a pair x,y such that y is a power of 2
(Hint: for each one of the given intege:S x
0
,x
1
, ,xn, call
x; the largest odd divisor of X;, and show that at least two
of these must be equal).
V.S. When x,y are two integers >0, write x--y if y is a power
of 2, i.e. of the form 2n with n EZ; show th;t this is an
equivalence relation, and that x--y if and only if the odd
divisors of x are the same as those of y.
VI
If m is any integer > 0, we define the multiplication of
congruence classes by putting
(x mod m)(y mod m)=(xy mod m);
in fact, property (E), that the right-hand side
depends only upon the classes in the left-hand side
and not upon the choice representatives x,y.
Definition. A ring is a set R, with two binary
operations, an addition (written +) and a multiplication
(written or X) satisfying the following axioms:
I. Under addition, R is a group.
II. Multiplication is associative, commutative and distrib-
utive with respect to addition: (xy)z = x(yz), xy = yx,
x(y+z)=xy+xz for all x,y,z.
23
24 VI
If R is a ring, then, by the distributive law
(xO) +(xz) =x(O+ z) =xz,
so that xO=O by the additive group property. Similarly,
x( -y)= -xy.
If there is in R an element e such that ex= x for all x,
this is unique; for, if f is also such, then ef = f and
ef = fe =e. Such an element is called the unit element and
is frequently denoted by lR or by I; a ring is called
unitary if it has a unit element.
The set Z of the integers, and the set Q of the rational
numbers, are unitary rings.
Theorem VI.l. For any integer m > 0, the congruence
classes modulo m, under addition and multiplication, make
up a unitary ring of m elements.
The verification is immediate. The unit element is the
congruence class (1 mod m); for that class, we will usually
write 1, and 0 for the class (0 mod m); we have 1 'FO
unless m= 1. The example m=6 shows that, in a unitary
ring, xy may be 0 without either x or y being 0 (take for
x,y the classes of 2 and of 3 modulo 6); when that is so, x
andy are called zero-divisors. The rings Z, Q are without
zero-divisors.
If a is prime tom, and a'= a+ mt, then every common
divisor of a' and m must also divide a= a'- mt; this
shows that all integers in the congruence class (a mod m)
are then prime to m. Such a class will be called prime to
m. If (a mod m), (b mod m) are both prime tom, so is
(ab mod m), by corollary 1 of theorem 111.2; in particular,
such classes cannot be zero-divisors in the ring of con-
gruence classes modulo m.
VI
25
Theorem VI.2. Let '!l a, b be integers, with m > 0; put
d=(a,m). Then the congruence ax=.b (mod m) has either
exactly d solutions modulo m, or no solution; it has a
solution if and only if b=O (mod d); there are exactly ;
distinct values of b modulo m for which this is so.
In fact, x is a solution if and only if there is an integer
y such that ax - b =my, i.e. b =ax -my; by corollary 1 of
theorem 11.1, this has a solution if and only if d divides b
. '
1.e. b = dz; we get all distinct values of b modulo m of that
form_ by giving to z the values 0,1, ... ,; -1. If xis a
solution of ax =b (mod m), then x' is also a solution if
and only if a(x'- x)=O (mod ";); by property (F) of
congruences, this is quivalent to d(x'- x)=.O (mod ; ),
and therefore to x' = (mod ; ) by theorem 111.2 and
the corollary of theore 111.1. This shows that all the
solutions of ax' =b (m d m) can be written as x' =
x + ; u; the distinct sol tions modulo m are then ob-
tained by giving to u the alues 0, l, ... ,d-1.
Corollary. The congruence classes prime to m modulo m
make up a group under multiplication.
This follows at once from corollary 1 of theorem 111.2,
from theorem VI.2, and from the fact that the class
(1 mod n) is the neutral element for multiplication in the
ring of congruence classes modulo m.
Definition. For any integer m > 0, the number of con-
gruence classes prime tom modulo m is denoted by <p(m),
and <p is called the Euler function.
26
VI
Accordingly, we have
<p(l) = <p(2) = 1, <p(3) = <p(4) =2, <p(5) =4, etc.
If m > 2, <p(m) can also be defined as the number of
positive integers prime to m and ..;; m - 1. If p is a prime,
<p(p)=p-1.
Definition. A field is a ring whose non-zero elements
make up a group under multiplication.
The ring Q of rational numbers is a field; the ring Z of
integers is not a field. A field has no zero-divisors; the
example of Z shows that the converse is not true.
Theorem Vl.3. For any integer m > 1, the ring of con-
gruence classes modulo m is a field if and only if m is a
prime.
If m is a prime, all classes modulo m, other than 0, are
prime to m and therefore make up a multiplicative group,
by the corollary of theorem VI.2. On the other hand, if m
is not a pr#Jte, it has a divisor d which is > 1 and <m;
then 1 < d < m, so that the classes (d mod m),
( mod m) are not 0 while their product is 0. Therefore
they are zero-divisors, and the ring modulo m is not a
field.
If p is a prime, the field of congruence classes modulo p
will be denoted by FP; it hasp elements.
EXERCISES
VI. I. If F(X) is a polynomial with integral coefficients, and if
x=.y (mod m), show that F(x)=F(y) (mod m).
VI
Vl.2. Solve the pair of congruences
5x-7y=9(mod 12), 2x+3y=.IO(mod 12);
showthat the solution is unique modulo 12.

Vl.3. For all values of a and b modulo 2, solve
x
2
+ ax+ b=.O (mod 2).
Vl.4. Solve x
2
-3x+3=0 (mod 7).
27
Vl.5. If m >I, show that the arithmetic mean of all positive
. . m
mtegers pnme to m and <m is T.
Vl.6. If m is any odd integer, prove that
Im+2m+ +(m-I)m=.O (mod m).
Vl.7. If m,,are integers >0, and (m,n)= 1, prove that cp(mn)
= (Hint: use exercise V.6).
VI.S. Show if m >I and p, q, ... , r are all the distinct
prime diviso'\ of m, then

VI.9. If p is any pnme, prove by induction on n, using the
binomial formula, that nP =n (mod p) for all integers n.
VI.IO. If p is any prime, and n > 0, prove by induction on n
that, if a=b (modp), then aP"=.bP" (modpn+
1
).
VI. II. If p is an odd prime, and x
2
=.y
2
(mod p ), show that x is
congruent either toy or to - y modulo p, but not to
both unless p divides x and y; hence conclude that
x
2
=a (mod p) has a solution x for exactly half of the
integers a among I, 2, ... ,p-I.
VI.l2. Show that the numbers of the form x+yV2, where x
andy are integers, make up a ring; if x,y range over all
rational numbers, show that they make up a field.
VII
\
The definition of a) group and of a subgroup makes it
clear that the intersection of subgroups of a group G (in
any number, finite or not) is again a subgroup of G.
Definition. Let a,b, ... ,c be elements of a group G. Then
the intersection G' of all the subgroups of G (including G
itself) which contain a, b, ... ,c is said to be generated by
a, b, ... , c, and these are said to be genera tors of G'.
This can also be expressed by saying that G' is the
smallest subgroup of G containing a,b, ... ,c; it may
happen that it is no other than G itself.
Let G be a group, x an element of G, and call Gx the
subgroup generated by x. Suppose that G is written addi-
tively. As usual, write - x for 0- x; this must be in Gx.
Also, write Ox for 0; for every integer n >0, write nx for
the sum x + x + + x of n terms all equal to x, and
(- n)x for - (nx); by induction on n, all these must be in
29
30 VII
Gx. Also by induction, one verifies at once the formulas
mx+nx=(m+n)x, m(nx)=(mn)x.
for all m,n in Z. The first formula shows that the elements
nx, for n EZ, make up a subgroup of G; clearly, this is no
other than Gx. For convenience, we state this as a theo-
rem only in the case when G is written multiplicatively;
then we write x
0
for the neutral element 1 of G, x-
1
for
the element x' defined by x' x = 1, x n for the product
xx ... x of n factors equal to x, and x-n for (xn)-
1

Theorem VII.l. Let G be a group under multiplication;
then, for every x E G, the subgroup of G generated by x
consists of the elements x n for n E Z.
G and x being as in theorem VII.l, call Mx the set of
those integers a for which x a= 1. As x
0
= 1, Mx is not
empty. Also we have, for all integers a,b:
which shows that X
0
=Xb if and only if a-b is in Mx; in
particular, Mx is closed under subtraction. Therefore Mx
satisfies the assumptions in theorem 11.1 (in other words,
it is a subgroup of the additive group Z) and consists of
the multiples of some integer m > 0; if m is not 0, it is the
smallest integer > 0 such that x m = 1. Thus, if m = 0, all
the elements xa are different; if m >0, xa is the same as
x b if and only if a =b (mod m ).
Definition. An isomorphism between two groups G, G' is
a one-to-one correspondence (a "bijection") between the
elements of G and those of G', transforming the group
operation in G into the group operation in G'.
VII
31
When there is such a correspondence, G and G' are
said to be isomorphic. The concept of isomorphism can be
transported in an obvious manner to rings and fields.
With this definition, the results obtained above can be
reformulated as follows:
Theorem VII.2. Let G be a group under multiplication,
generated by a single element x. Then either G is infinite,
and the mapping

is an G onto the
additive group Z, or it consists of a fini number m of
elements, and then the mapping

od m) is an
isomorphism of G onto the additive group congruence
\
I
Of course, if G is any group and x any ele\nent of G,
theorem VII.2 can be applied to the of G
generated by x. I.
Definition. The number of elements of a finite group is
called its order. If a group of finite order is generated by a
single element, it is called cyclic; if an element x of a
group generates a group of finite order m, m is also called
the order of x.
EXERCISES
VII.l. If F is a finite field, show that the subgroup of the
additive group ofF generated by I is of prime order p
and is a subfield of F, isomorphic to the field FP of
congruence classes modulo p.
VII.2. Show that a non-empty finite subset S of a group G is a
subgroup of G if and only if it is closed under the group
operation (Hint: if a E S, then is a bijection of S
onto itself).
32
VII
Vll.3. Show that a finite ring is a field if and only if it has no
zero-divisors.
VII.4. If G is a (commutative) group, and n any integer, show
that the elements xn, for x E G, make up a subgroup of
G.
VII.5. If G', G" are subgroups of the (commutative) group G,
show that the elements x'x" with x'EG',x"EG",
make up a subgroup of G.
VII.6. Let G be a (commutative) group, x an element of G of
order m, andy an element of G of order n. Show that,
if (m,n)=l, then x')'b=I if and only if x
0
=yb=I:
hence show that the group generated by x and y is
cyclic of order mn, generated by xy.
VII.7. Show that, if m>2, n>2, and (m,n)= I, the multiplica-
tive group of congruence classes prime to mn modulo
mn is not cyclic (Hint: use exercise V.6 and the fact
that a cyclic group has at most one subgroup of order
2).
Vll.S. Find all the values of n for which the multiplicative
group of odd congruence classes modulo 2n is cyclic.
VII.9. Show that, if G is a (commutative) group and n an
integer > 0, the elements of G whose order divides n
make up a subgroup of G.
VII.IO. Show that, if G is a finite (commutative) group, the
product of all elements of G is I or an element of order
2.
Vll.ll. If p is a prime, show that (p- I)!= - I (mod p) (Hint:
consider the multiplicative group modulo p, and reason
as in ex. VII.IO).
VIII
Theorem 11.1 shows that every subgroup M of Z is either
0 or generated by its smallest element m >0; in the latter
case it is generated by m or also by - m, but by no other
element of M. For cyclic groups, we have:
Theorem VIII.l. Let G be a cyclic group of order m,
generated by an element x. Let G' be a subgroup of G; then
there is a divisor d of m such that G' is the cyclic group of
m
order d generated by x d.
Let M be the set of those integers a for which X
0
E G'.
The formula xa-b=(x
0
)(xb)-
1
shows that M is a sub-
group of Z; as it contains m, it consists of the multiples of
some divisor d of m. Therefore G' consists of the elements
xda with a EZ, i.e., it is generated by xd. We have xda =
xdb if and only if da =db (mod m); by property (F) of the
congruence relation ( V), this is equivalent to a =.b
(mod ).
33
34
VIII
Corollary 1. For every positive divisor n of m, a cyclic
group of order m has one and only one subgroup of order n.
Let G be as in theorem VIII.l, and put d= m; by that
n
theorem, if G' is a subgroup of G of order n, it must be
the one generated by xd, and xd does generate such a
subgroup.
Corollary 2. G,m,x, G' being as in theorem VIII.l, an
element x a of G generates G' if and only if (a, m) = d.
If (a,m)=d, xa is in G'; moreover, by theorem V1.2,
we can solve at=.d (mod m), and then we have xd=(xa)
1
,
so that the group generated by x a contains x d and hence
G'.
Corollary 3. G,m,x being as above, xa generates G if and
only if (a,m)= 1, and G has exactly <p(m) distinct genera-
tors.
Corollary 4. For every integer m >0, we have
L <p(d) = m.
dim
(Here the sum in the left-hand side is taken over all
positive divisors d of m).
Consider a cyclic group G of order m (e.g. the additive
group of congruence classes modulo m). By corollary 1,
for every divisor d of m, G has exactly one subgroup Gd of
order d, and is a one-to-one correspondence be-
tween the divisors of m and the subgroups of G. For each
d, call Hd the set of all distinct generators of Gd, whose
number is <p(d) by corollary 3. Each element of G belongs
VIII
35
to one and only one set Hd, since it generates one and
only one subgroup of G.
Let G be a group, and X a subset of G; for every a E G,
we write aX for the set of the elements ax with x EX. The
definition of a group implies that is a bijection of
X onto aX, so that, if X is finite, all sets aX have the same
number of elements as X.

Definition. If G is a group and H a subgroup of
set of the form xH with x E G is called a coset of H G.
'" Lemma. Let xH,yH be two cosets of a subgroup H
group G; then, either they have no element in common, or '
xH=yH.
If they have a common element, this can be written as
xh with hE H, and also as yh' with h' E H. This
gives y-
1
x=h'h-
1
EH, and hence xH= y(y-
1
x)H =
y (h'h-
1
H)=yH.
Theorem VIII.2. If H is a subgroup of a finite group G, the
order of H divides the order of G.
In fact, every element x of G belongs to some coset of
H (viz., to xH), and, by the lemma, only to one. As the
number of elements of each coset is equal to the order of
H, the order of G must be a multiple of that number.
Corollary. If x is any element of a group of order m, its
order divides m, and x m = 1.
As the order d of x is the order of the subgroup of G
generated by x, theorem VIII.2 shows that it divides m.
Then xm=(xd)mfd= 1.
I
I
36
VIII
(N.B. The above results, and their proofs, are valid also
for other than commutative groups; as mentioned before,
these remain outside the scope of our treatment).
Theorem VIIT.3. If m is any integer > 0, and x an integer
prime to m, then x <p(m) = 1 (mod m ).
This is the special case of the above corollary, when it
is applied to the multiplicative group of congruence
classes prime tom modulo m (or, as one says more briefly
but less accurately, to the multiplicative group modulo m).
Corollary. If pis a prime, then xp-
1
= 1 (modp)for every x
prime top, and xP =x (mod p) for every x.
The first assertion is a special case of theorem VIII.3,
and the second one is an immediate consequence. Con-
versely, the latter also implies the former, in view of
theorem VI.2 (or of theorem 111.2). For another proof of
the second assertion, cf. exercise Vl.9.
The corollary was known to Fermat and is known as
Fermat's theorem; a proof was first published by Euler,
who also gave a proof (substantially the same as the one
given above) for theorem VIII.3, which is known as
Euler's theorem.
EXERCISES
VIII. I. If G is a group of order m, and if n is prime tom, show
that every element of G can be written in the form xn
with some x E G.
VIII.2. If pis a prime, show that every group of order pn, with
n > 0, contains an element of order p, and that every
group of order p is cyclic.
VIII
VIII.3.
VIII.4.
37
If P is an odd prime divisor of a
2
" +I, with n > I, show
I (mod 2n+I) (Hint: find the order of (a modp)
m the multiplicative group modulo p) (N.B. This was
used to that 2
32
+ I is not a prime,
Fermat s guess that all integers 2
2
" + 1 are
pnme).
If a,b are integers >0, and a =2"5!3m, with m prime to
10, show that the decimal fraction for !!._ .has a period
number of whose digits divides cp(m); show that, if
It no period with less than m- I digits, then m is a
pnme.
IX
In order to consider polynomials with coefficients in a
field FP, and equations over such fields, we begin by
reviewing some elementary properties of polynomials over
an arbitrary field K; these are independent of the nature
of that field, and quite analogous to the properties of
integers described above in II, III, IV.
In this , a field K (the "groundfield") is to be regarded
as fixed once for all. A polynomial P over K (i.e. with
coefficients in K), in one indeterminate X, is given by an
expression
with a
0
,a
1
, , an inK. If an *0, Pis said to be of degree n,
and we write n =deg(P); every polynomial except 0 has a
degree. Addition and multiplication being defined in the
usual manner, such polynomials make up a ring, usually
written K[X]. If P, Q are non-zero polynomials, then
deg( PQ) = deg( P) + deg( Q ).
39
40
IX
Lemma. Let A,B be two polynomials, with B=I=O; put m =
deg(B). Then there is a unique polynomial Q such that
A- BQ is 0 or of degree <m.
(This should be compared with the lemma in II). If
A = 0, there is nothing to prove; we proceed by induction
on n=deg(A): first we prove the existence of Q. If n<m,
we take Q=O. Otherwise, call bXm the term of degree m
in B, and aX" the term of degree n in A; as the poly-
nomial is of degree <n, we can
write it as BQ' + R with R = 0 or of degree <m, by the
induction assumption. Then A = BQ + R, with
Q = Q' + xn-m. As to the unicity of Q, let A- BQ and
A- BQ
1
be 0 or of degree <m; then the same is true of
B(Q- Q
1
); since this is of degree m+deg(Q- Q
1
) unless
Q- Q
1
is 0, Q must be the same as Q
1
D
If R = 0, A = BQ, A is said to be a multiple of B, and B
a divisor of A. If B =X- a, R must be 0 or of degree 0, i.e.
a "constant" (an element of K), so that we can write
A=(X-a)Q+r
with r E K. Substituting a for X in both sides, we get
A( a)= r; if this is 0, a is called a root of A. Thus A is a
multiple of X- a if and only if a is a root of A.
Just as theorem 11.1 was derived from the lemma in
II, we have:
Theorem IX.l. Let we be a non-empty set of polynomials
(over K), closed under addition and such that, if A is in we,
all multiples of A are in we. Then we consists of all the
multiples of some polynomial D, uniquely determined up to
multiplication by a non-zero constant.
IX
41
If we={O}, the theorem is true with D=O. Otherwise
take in we a polynomial D =1=0 of smallest degree d. If A is
in we, we can apply the lemma to A and D and write
A= DQ + R, where R is 0 or of degree <d. Then R =
A+ D(- Q) is in IJJ1, hence 0 by the definition of D, and
A= DQ. If D
1
has the same property as D, then it is a
multiple of D and D is a multiple of D
1
, so that they have
the same degree; writing then D
1
=DE, we see that E is of
degree 0, i.e. a non-zero constant.
Call aXd the term of degree din D; among the poly-
nomials differing from D only by a non-zero constant
factor, there is one and only one with the highest
coefficient 1, viz., a-
1
D; such a polynomial will be called
normalized.
Just as in II, we can apply theorem IX.l to the set we
of all linear combinations AP + BQ + + CR of any
number of given polynomials A,B, ... ,C; here P,Q, ... ,R
denote arbitrary polynomials. If then we consists of the
multiples of D, where D is either 0 or a normalized
polynomial, D will be called the g. c. d. of A, B, ... , C and
will be denoted by (A,B, ... ,C). As in II, Dis a divisor
of A, B, ... , C, and every common divisor of A, B, ... , C
divides D. If D= 1, then A,B, ... ,C are said to be mutu-
ally relatively prime; they are so if and only if there are
polynomials P, Q, ... , R such that
AP+BQ+ + CR= 1
If (A,B)= 1, A is said to be prime to B, and B to A.
A polynomial A of degree n > 0 is said to be prime, or
irreducible, if it has no divisor of degree > 0 and <n.
Every polynomial of degree 1 is irreducible. One should
note that the property of a polynomial of being irreduc-
42
IX
ible need not be preserved when one changes the ground-
field: for instance X
2
+ 1 is irreducible over Q, and also
over the field of real numbers, but not over the field of
complex numbers, since X
2
+ 1 =(X+ i)(X- i).
Exactly as in IV, we could prove now that every
polynomial of degree > 0 can be written, essentially
uniquely, as a product of prime polynomials. All we shall
need is a weaker result:
Theorem IX.2. Let A be a polynomial of degree n > 0 over
K; this can be written, uniquely up to the order of the
factors, in the form
where 0 <m <n, a
1
,a
2
, ... ,am are in K, and Q is without
roots inK.
If A has no root, this is clear; otherwise we use induc-
tion on n. If A has a root a, write A =(X- a)A'; as A' is
of degree n -l, we can apply the theorem to it; writing A'
in the prescribed form, we get a similar product for A. If
A can be written as above and also as
A =(X- b
1
)(X- b
2
) (X- b,)R
where R has no root inK, then the root a of A must occur
among the a; and also among the bp and then, dividing by
X- a, we get for A' two products which, by the induction
assumption, must coincide. D
Corollary. A polynomial of degree n >0 has at most n
distinct roots.
IX 43
EXERCISES
IX.l. Find the g.c.d. of the polynomials over Q:
X
5
-X
4
-6X
3
-2X
2
+5X+3, X
3
-3X-2.
Also, find their g.c.d. over the field F
3
if the coefficients
are interpreted as congruence classes modulo 3.
IX.2. Show that X
4
+ 1 is a prime polynomial over Q, but has
divisors of degree 2 over the field defined in exercise
VI.l2.
IX.3. Let K be any field, and R a subring of K[X] containing
K. Prove that there exists a finite set of polynomials
P
1
,P
2
, ... ,PN in R such that R consists of all the poly-
nomials in P
1
,P
2
, ... ,PN with coefficients inK (Hint: call
d the g.c.d. of the degrees of all polynomials in R, take
P
1
,P
2
, ... ,Pm in R such that the g.c.d. of their degrees is d,
and then apply the conclusion in exercise 111.6).
X
Lemma. Let G be a group of order m. If, for every divisor d
of m, there are no more than d elements of G satisfying
xd = 1, G is cyclic.
For every divisor d of m, call tf;(d) the number of
elements of order din G; we have to prove that tf;(m) >0.
In any case, since every element of G has an order which
divides m, we have
m = L tf;(d).
dim
If, for some d, tf;(d) > 0, then G has an element of order d,
and this generates a cyclic group G' of order d. As all the
d elements of G' satisfy xd= 1, our assumption on G
implies that all the tf;(d) elements of G of order d are in
G'; by corollary 3 of theorem VIII.l, there are exactly
q;(d) such elements. Therefore, if tf;(d) is not 0, it has the
value q;( d). Since 2: tf;( d) has the value m, and 2: q;( d) has
45
46
X
the same value by corollary 4 of theorem VIII.l, this
implies that tf;(d)=q;(d) for all d; in particular, tf;(m)=
q;(m)>O.
Now we consider an arbitrary field K, and, denoting by
K x the multiplicative group of the non-zero elements of
K, we consider the elements and subgroups of finite order
of K x. If x is an element of K x of order m, it satisfies
xm= 1, and xa=xh if and only if a=b (mod m); tradi-
tionally, x is then called a root of unity, and more pre-
cisely a primitive m
1
h root of unity. For any n, an element
x of K which satisfies x" = 1 is a root of unity whose order
divides n. In the field of complex numbers, the number
2
; 21T . . 21T
e 1TI m =cos- + l sm-
m m
is a primitive m
1
h root of unity; so is e
2
1ria/m for (a,m)= 1.
Theorem X.l. If K is any field, every finite subgroup of K x
is cyclic.
For every n >0, an element of K satisfying x" = 1 is a
root of the polynomial X"- 1; by the corollary of theo-
rem IX.2, there are at most n such elements in K. Our
theorem follows now at once from the lemma.
Corollary 1. If K is a finite field, K x is cyclic.
Corollary 2. If K is any field, and n an integer > 0, the
elements of K satisfying x" = 1 make up a cyclic group
whose order divides n.
It is clear that they make up a subgroup of K x; this is
cyclic, by theorem X.l; if it is generated by x, the order of
x, which is also the order of the group, must divide n.
X
47
Theorem X.2. If p is any prime, there is an integer r prime
toP such that l, r, r
2
, r
3
, , rP -
2
, in some order, are respec-
tively congruent to 1, 2, ... ,p - 1 modulo p.
This is only the traditional formulation for the fact that
the classes erime to p modulo p make up the
mulhphcahve group FP of the field FP of congruence
classes modulo p, and that, by corollary 1 of theorem X.l,
this must be cyclic; if (r mod p) is a generator' of that
group, r has the property stated in theorem X.2.
If m is an integer > 1, the multiplicative group of
classes to m modulo m is not always
cyclic (cf. e.g. exerctses VII.? and VII.8). It is cyclic if
and only if there is an integer r prime to m such that
mod m) is of order q;(m) in that group, i.e., if and only
1f the smallest integer x > 0 such that rx = 1 (mod m) is
q;(m); when that is so, r is called a primitive root modulo
m. Then, to every integer a prime to m, there is an integer
x such that rx =a (mod m); this integer x, which is
determined only modulo q;(m), is called the index of a and
denoted by ind,(a). By theorem VII.2, if r is a primitive
root modulo m, the mapping
(a mod mod q;(m))
is an isomorphism of the multiplicative group of con-
gruence classes prime to m modulo m onto the additive
group of all congruence classes modulo q;(m). In particu-
lar, we have, for a and b prime tom:
ind,(ab) =ind,(a) +ind,(b) (mod q;(m)).
The analogy with logarithms is obvious.
48
X
ExERCISES
X. I. If m is any integer > 1, show that the number of primitive
roots modulo m is either 0 or <p( <p(m)).
X.2. Find a primitive root r modulo 13; tabulate ind,(a) for
1 <.a<. 12; use the table to find all primitive roots modulo
13, and to tabulate 5
1
h and 29
1
h powers modulo 13.
X.3. Use the existence of a primitive root modulo p, where p is
a prime, to show that 1"+2"+ +(p-1)" is congruent
to 0 or to - 1 modulo p according to the value of the
integer n 0.
X.4. Show that a primitive root modulo an integer m > 1 is also
a primitive root modulo every divisor of m (Hint: use
exercise V.6).
X.5. Using the binomial formula, prove by induction that, if p
is an odd prime, then, for all n 0:
(l+pxY"=1+p"+
1
x (modp"+
2
)
(cf. exercise VI.IO). Hence show that, if r is a primitive
root modulo p, it is a primitive root modulo p" if and only
if p
2
does not divide rp-!_ 1, and that in any case either r
or r + p is a primitive root modulo p n.
X.6. Find all the integers m > 1 such that there exists a primi-
tive root modulo m (Hint: use exercises X.4, X.5, VII.7,
VII.8, and the fact that if r is a primitive root modulo an
odd integer m, then either r or r + m is a primitive root
modulo 2m).
X.7. An integer m > 0 is called "square-free" if it has no divisor
of the form n
2
where n is an integer > 1. For every m > 0,
put p.(m) = (- 1 )' if m is square-free and the product of r
primes (with r=O if m= 1), and p.(m)=O otherwise. Prove
that p.(ab) = p.(a)p.(b) if a is prime to b; hence show that
L p.(d) is 1 if m= 1, and 0 if m> 1 (Hint: write mas in
dim
exercise IV.4).
X
49
X.8. Let K be a field containing a primitive m
1
h root of unity x;
for each divisor d of m, call FAX) the product of the
factors X -xa for O<.a<m, (a,m)=;. Show that Fd is of
degree <p(d) and prove the formula
xm-1 = II FiX);
dim
hence, using exercise X.7, prove that
Fm(X)= II (Xmfd_l)"(d)_
dim
X.9. K being as in exercise X.8, prove that the sum of all
primitive m
1
h roots of unity in K is p.(m). State the special
case of this result for K = FP, m = p- 1.
_\
l
.:l
XI
Now we will consider equations of the form xm =a, in a
field K (or occasionally in a ring); the case a= 1 has been
discussed in X. As the case a= 0 is trivial, we assume
a*O. If then, in the field K, x is a solution of xm=a,
an element x' of K is also a solution if and only if
(x' / x)m = 1. Therefore, if xm =a has a solution in K, it
has as many solutions as K contains mth roots of unity,
i.e. roots of xm- 1.
Here we are chiefly concerned with the field FP of
congruence classes modulo a prime p.
Theorem XI.l. Let p be a prime, man integer >0, and a
an integer prime to p; put d = ( m,p- 1 ). Then the con-
gruence xm=a (mod p) has either exactly d solutions
modulo p or no solution; it has a solution if and only if the
congruence yd =a (mod p) has a solution; this is so if and
only if a<P- I)/ d = 1 (mod p ), and there are exactly p :
1
such values of a modulo p.
51
I
52
XI
We use the fact that the group FPx is cyclic, or, what
amounts to the same, that there is a primitive root r
modulo p (cf. X). Put a=r
1
, x=ru (mod p), i.e. t=
ind,(a), u=ind,(x). Then the congruence xm=a (modp)
is equivalent to mu =t (mod p- 1 ), and our conclusions
follow at once. from .theorem V I ~ frovided we note t ~ a t
t=O (mod d) 1s eqmvalent to 7 t=O (mod p -1), 1.e.
to a<P-!)/d= 1 (modp).
Take for instance the congruence x
3
=a (mod p ), with a
prime top. For p=3, this is equivalent to x=a (mod 3).
Take the case where p = 1 (mod 3); as this implies p =1=2, p
is also = 1 (mod 2), hence of the form 6n + 1; we have
d= 3, P ~
1
=2n; the congruence x
3
=a (mod p) has a
solution if and only if a is congruent to one of the
numbers 1, r
3
, ... ,rP-
4
modulo p, and then, if x is one
solution, the solutions are given by xr
2
nz modulo p with
z = 0, 1, 2. If p = 2 (mod 3), in which case p is either 2 or of
the form 6n-l, the congruence x
3
=a (mod p) has one
and only one solution for every a prime top.
From now on, we consider only the case m = 2. Then
x
2
= 1 (mod p) has no other solution than 1 if p =2, and
has the two solutions 1 if p > 2.
Definition. If p is an odd prime, an integer a prime top is
called a quadratic residue or a quadratic non-residue
modulo p according as the congruence x
2
=a (mod p) has
a solution or not.
As no other case than m = 2 will occur, the word
"quadratic" will occasionally be omitted; otherwise one
speaks of "cubic residues" if m = 3, "biquadratic residues"
if m =4, etc.
Let p be an odd prime; put p =2n + 1, and let r be a
primitive root modulo p. Then theorem XI.l shows that
XI
53
there are n quadratic residues modulo p, viz., the classes
of l,r
2
, ,r
2
"-
2
, and the same number of non-residues,
viz., the classes of r,r3, ... ,r
2
"-
1
.1f xis a solution of x
2
=a
(mod p), this congruence has the two solutions x, and
no other, modulo p.
Theorem XI.2. Let p = 2n + 1 be an odd prime, and a an
integer prime top. Then an is congruent either to + 1 or to
- 1 modulo p; a is a quadratic residue or a non-residue
modulo p according as an=+ 1 (mod p) or an= -1
(modp).
Put b =an; by Fermat's theorem (i.e. the corollary of
theorem VIII.3), we have b
2
= 1 (mod p), hence b = 1
(modp). We can now apply theorem XI.l.
Corollary. -1 is a quadratic residue or a non-residue
modulo the odd prime p, according as p = 1 or p = - 1
(mod 4).
In fact, (- 1 )" is + 1 or - 1 according as n is even or
odd.
ExERCISES
XI. I. If p is an odd prime divisor of a
2
+ b
2
, where a, b are
integers, show that p must be congruent to 1 modulo 4
unless it divides both a and b.
XI.2. If p is an odd prime, and a is prime top, show that the
congruence ax
2
+ bx + c = 0 (mod p) has two solutions,
one or none according as b
2
- 4ac is a quadratic residue,
0 or a non-residue modulo p.
XI.3. If m, n are mutually prime integers > 0, and F is a
polynomial with integral coefficients, show that the con-
gruence F(x)=O (mod mn) has a solution if and only if
54
XI
F(x)=O (mod m) and F(x)=O (mod n) both have solu-
tions (Hint: use exercises V.6 and Vl.l).
XI.4. If p is an odd prime, n > 0, and a is prime top, prove by
induction on n that the congruence x
2
=a (mod p ") has a
solution if and only if a is a quadratic residue modulo p:
show that, if x is a solution, there are no other solutions
than X modulo p n.
XI.5. Show that, if a is an odd integer, and n > 2, the con-
gruence x
2
:=a (mod 2") has a solution if and only if a= 1
(mod 8) (Hint: use induction on n, observing that, if x is
a solution, either x or x +2"-
1
is a solution of y
2
=a
(mod 2"+
1
)). If xis a solution, find the other solutions.
Xl.6. Use exercises XI.3,4,5 to give a criterion for the con-
gruence x
2
=a (mod m) to have a solution when m is any
integer > 1, and a is prime to m.
Xl.7. If, for some m > 1 and some a prime tom, the congruence
x
2
:=a (mod m) has exactly n distinct solutions modulo m,
show that there are exactly <p(m) values of a, prime tom
n
modulo m, for which this is so.
XII
Let p be an odd prime; put p = 2n + 1. Write G for the
multiplicative group FPx of congruence classes prime top
modulo p; this has a subgroup H of order 2 consisting of
the classes ( 1 mod p); we apply to G and H the
definitions and lemma of VIII. If x is an element of G,
it belongs to one and only one coset xH; this consists of
the two elements ( x mod p); there are n such cosets,
viz., the cosets ( 1 mod p ), ( 2 mod p ), ... , ( n mod p ).
If, in each coset, we choose one element, and if we write
these elements, in any order, as u
1
, , un, this is known as
"a set of representatives" for the cosets of H in G; then
every integer prime top is congruent to one and only one
of the integers u
1
, , un modulo p. For the purposes
of the next lemma, which is due to Gauss and known as
Gauss' lemma, such a set { u
1
, , un} will be called a
"Gaussian set" modulo p. The simplest such set is
{ 1,2, ... ,n}.
55
56
XII
Lemma. Letp=2n+l be an odd prime, and {u
1
, ,un} a
Gaussian set modulo p. Let a be an integer prime top; for
1 <. i <. n, let e; = 1 and i' be such that au; =e;ur (mod p ).
Then a is a quadratic residue modulo p or not according as
the product e
1
e
2
en is + 1 or -1.
In the n congruences au; =e;ur (mod p), no two values
of i' can be the same, since otherwise this would give
au;= auk (mod p) for some i =l=k, hence u; = uk
(mod p), which contradicts the definition of a Gaussian
set. Therefore, if we take the product of all these con-
gruences, we get
an(u
1
u
2
un) = ( e
1
e
2
en) ( u
1
u
2
un) (mod P)
and therefore
since all the u; are prime top. Our conclusion follows now
from theorem Xl.2.
Theorem XII.l. Let p be an odd prime; then 2 is a
quadratic residue modulo p if p = 1 or 7 (mod 8), and a
non-residue if p = 3 or 5 (mod 8).
Put p = 2n + 1, and apply Gauss' lemma to a= 2 and
the Gaussian set {1,2, ... ,n}. If n=4m or 4m+l, e; has
the value + 1 for 1 <. i <. 2m, and - 1 otherwise; then the
product of thee; is (-l)n-
2
m=(-lt. If n=4m+2 or
4m +3 e. is + 1 for 1 <.i <.2m+ 1, and -1 otherwise, and
' I
the product of thee; is (-lt-
2
m-
1
=(- it-
1
. A straight-
forward application of the lemma gives now the result
stated above.
XII 57
Definition. If( is an odd prime, and a an integer prime to
p, we define ; ) to have the value + 1 or -1 according
as a is a quadratic residue or not modulo p; this is called
the Legendre symbol.
When p is given, the symbol ( ; ) depends only upon
the congruence class of a modulo p. Its definition implies
that (

= 1 for all a prime top. .

If r is again a primitive root modulo p, and if a =rx
(modp), i.e. x=ind,(a), we have (;)=(-lY; here one
should note that this does not depend upon the choice of
x, since x is well defined modulo the even integer p- 1.
From the fundamental property of the index (cf. the last
formula of X), it follows that the Legendre symbol has
the property
( ) = (; ) (; ) for all a, b prime top.
Theorems Xl.2, its corollary, and theorem XII.l, give
respectively:
a(p-1)/2=(;) (modp), ( )=(-l)(p-1)/2, /
-l)(,'-f
(as to the last formula, observe that
1
is alwJ an
integer, even if p= 1 or 7 (mod 8) and odd if p1i or 5
(mod 8)).
58 XII
The following theorem is known as "the quadratic
reciprocity law":
Theorem XII.2. If p and q are distinct odd primes, then
( ~ ) (;) = ( -l)[(p-l)/2][(q-l)/2]
Putp=2n+ 1, q=2m+ 1. Apply Gauss' lemma to a=q
and to the "Gaussian set" {1,2, ... ,n} modulo p. For
1 <x <n, we have to write qx=exu (modp) with ex= 1
and 1 <u <n; this can be written as qx=exu+py, where
ex, u,y are uniquely determined by these conditions when
x is given. In particular, ex has the value - 1 if and only if
we have qx = py- u, or equivalently py = qx + u, with
1,;;;; u <n. This implies y > 0, and also
1 q+ 1
y< p(q+l)n<-
2
-=m+l.
In other words, we have ex= -1 if and only if we can
find y such that the pair ( x,y) satisfies the conditions
1 ,;;;; x < n, 1 < y < m, 1 < py - qx < n.
Consequently, if N is the number of such pairs (x,y),
Gauss' lemma gives ( ; ) = (- 1 )N.
Similarly, ( has the value (- l)M, if M is the number
of pairs (x,y) satisfying
l<x<n, l<y<m, l<qx-py<m.
As qx-py cannot be 0 if xis prime top, and in particular
if 1 ,;;;; x ,;;;; n, this shows that the left-hand side of the
formula in our theorem has the value ( -l)M+N, where
M + N is the number of pairs (x,y) satisfying the condi-
XII
59
tions
l<x<n, l<y<m, -n<qx-py<m.
Now let S be the number of pairs (x,y) satisfying
1 <x <n, 1 <y <m, qx-py< -n,
and let T be the number of pairs (x',y') satisfyip.g
l<x'<n, l<y'<m, qx'-py'>m.
Between those last two sets, there is a one-to-one corre-
spondence defined by
x' = n + 1 - x, y' = m + 1 - y;
in fact, when that is so, we have
qx'-py'-m= -(qx-py+n).
Therefore S = T. On the other hand, M + N + S + T is the
total number of pairs (x,y) with 1 <x <n, 1 <y <m, and is
therefore equal to mn. Finally we have
( )(!)=< -l)M+N =( -l)M+N+S+T =( -l)mn,
as was to be proved.
EXERCISES
XII. I. Letp be an odd prime; letf(a) be a function, defined for
a prime top, taking no other values than t/ and such
that (
f(ab)=j(a)f(b); f(a)=f(b) if a=:=b ( odp).
Show that either f(a)= l for all a, or f(a)= ( ~ for all a.
60
XII
XII.2. If p is an odd divisor of a
2
+ 2b
2
, where a, b are integers,
show that p is congruent to 1 or to 3 modulo 8 unless it
divides both a and b.
XII.3. If p and q are primes such that p=2q+ 1 and q=l
(mod 4), show that 2 is a primitive root modulo p.
XII.4. Using only Gauss' lemma, find all the values of the
prime p > 3 for which 3 is a quadratic residue.
XII.5. Let a be a non-zero integer. Prove that, if p and q are
odd primes, not divisors of a, such thatp=q (mod 4jal),
then { = { ~ (Hint: write a= n
2
b, where b is
"square-free" (cf. exercise X.7); then apply the quadratic
reciprocity law to every odd prime divisor of b and top
and q; also, apply theorem XII.l if b is even, and the
corollary of theorem Xl.2 if a < 0).
XIII
We recall the concept of a complex number; this is a
number of the form x+ ry, where x,y are real numbers; i
satisfies i
2
=- 1, and the rules for addition and multi-
plication are the well-known ones. In particular, multi-
plication is given by
(x+ ry)(x' + ry') =(xx'-yy')+ i(yx' + xy').
For addition and multiplication, the set C of complex
numbers makes up a unitary ring, with the unit element
l=l+iO (cf. VI). If a=x+ry, one writes ii=x-ry,
and calls ii the imaginary conjugate of a; the imaginary
conjugate of ii is then a. The mapping a ~ i i is a one-to-
one mapping of C onto itself, preserving the operations of
addition and multiplica 'on;j!_is thus an "automorphism"
of C, i.e. an isom 1sm of C onto itself.
We w r i ~ a)= aii, and call this the norm of a. By the
multiplication rule, if a=x+ry, N(a)=x
2
+y
2
; by the
commutativity of multiplication, we have N(ab) =
N(a)N(b). The norm of a is 0 if and only if a is 0;
61
62
XIII
otherwise it is a real number > 0. Consequently, for any
a=x+ry*O, we may put
( )
-1- X Y
a'=Na a=N(a)-zN(a)'
and then aa'= 1, and, for every b, a(a'b)=b; conversely,
if az=b, we have a'(az)=a'b, hence, by associativity,
z =a' b. This shows that C is in fact a field. As usual, we
associate, with the complex number a= x + ry, the point
(x,y) in the plane; its Euclidean distance from the
"origin" 0 is then lal = N(a)
1
1
2
; this is also called the
"absolute value" of a.
For our purposes, we have to consider, rather than the
field C, the subset of C consisting of the complex numbers
x + ry where x,y are in Z, i.e. ordinary integers. It can .be
verified at once that this is a ring; it is called the Gausszan
ring, and its elements are called Gaussia.n integers. <;:!early
is an automorphism of that nng. If a 1s any
Gaussian integer, N(a) = aii is a positive integer in Z.
Occasionally we also consider the numbers x + ry where
x y are in Q, i.e. rational numbers; just as above one sees
that they make up a field (the "Gaussian field").. .
If a b x are Gaussian integers and b =ax, b 1s satd to
be a of a; a is said to divide b or to be a of
b; when that is so, N(a) divides N(b). Every Gausstan
integer divides its norm. . . . .
A divisor of 1 is called a unit; 1f a= x + zy 1s a urut,
N(a) must divide 1 and so has to be 1; as x,y are integers,
this implies that one of them is 1 and the other 0.
Therefore the Gaussian units are 1, i.
Two non-zero Gaussian integers a, b divide each other
if and only if they differ only by a factor which is a unit,
i.e. if b = ea with e = 1 or i; then they are called
associates. Among the four associates of a given integer
XIII
63
a*O, there is one and only one, say b=x+iy, satisfying
x > 0, y;;;,. 0; that one will be called normalized. For in-
stance, among the associates 1 i of 1 + i, 1 + i and no
other is normalized. Geometrically, the points in the
plane, corresponding to the associates of a, are
deduced from a by a rotation around 0 by an angle T
with n = 0, 1, 2, 3; the normalized one is the one which lies
either on the positive real axis or in the "first quadrant".
A Gaussian integer of norm > 1 is called a Gaussian
prime if it has no other divisor than the units and its own
associates. It amounts to the same to say that q is a
Gaussian prime if it is not 0 or a unit and has no divisor
whose norm is > 1 and <N(q). Ordinary integers which
are prime in the previously defined sense ( IV) will be
called rational primes (or "ordinary primes"). If q is a
Gaussian integer and N(q) is a rational prime, then q is a
Gaussian prime; as we shall see, the converse is not true.
The associates of a Gaussian prime are Gaussian primes;
as we have seen, there is one and only one of these which
is "normalized" in the above defined sense. If q is any
Gaussian prime, so is ij. If a is any Gaussian integer, not 0
nor a unit, then its divisor of smallest norm > 1 must be a
Gaussian prime.
Gauss, who introduced Gaussian integers into
number-theory, found that they can be (essentially
uniquely) factorized into Gaussian primes, in close anal-
ogy with ordinary integers. This will now be proved; the
method is the same as in II, III, IV (and as in IX).
We first prove lemma, similar to those in II and IX.
Lemma. Let a b be Gaussian integers, with b*O. Then
there is a multz le bq of b such that
\
N(a-bq)< tN(b).
64
XIII
For any real number t, there is 'a largest integer m <t,
and we have m.;;;;, t <m + 1; by the nearest integer m' to t,
we will understand either m or m + 1 according as t- m is
<m+l-t or not; then we have lt-m'l<t. Now let
z = x + iy be any complex number; call m the nearest
integer to x, n the nearest integer toy, and put q = m +in.
Then q is a Gaussian integer, and we have
Apply this to z = , where a, b are the integers in the
lemma. The Gaussian integer q defined by the above
construction has then the required property.
Theorem XIII.l. Let 9R be a non-empty set of Gaussian
integers, closed under addition and such that, if a is in [Q,
all multiples of a are in 9R. Then 9R consists of all the
multiples of some Gaussian integer d, uniquely determined
up to a unit factor.
If 9R= {0}, the theorem is true with d=O. If not, take in
9R an element d of smallest norm > 0. If a is in 9R, we can
apply the lemma and write a=dq+r with N(r)<tN(d).
Then r =a- dq is in 9R, which contradicts the definition
of d unless r = 0, a= dq. As to unicity, if d' has the same
property as d, d and d' must be multiples of each other, so
that d' is an associate of d.
Just as in II (and in IX), we can now apply theorem
XIII.l to the set of all linear combinations ax+ by
+ +cz, where a,b, ... ,c are given Gaussian integers
and x,y, ... ,z are arbitrary Gaussian integers, and so
define the g.c.d. (a,b, ... ,c); this will be uniquely de-
XIII 65
termined if we prescribe that it should be "normalized"
(in the sense defined above). If it is 1, we say that
a, b, ... , c are mutually relatively prime. We can now re-
peat the contents of III and IV, except that the proof
of theorem IV.2 was by induction on the integer a in that
now one has to use induction on N(a). The
conclusiOn 1s:
Theorem XIII.2. Every non-zero Gaussian integer can be
written "essentially uniquely" as a product of a. unit and of
Gaussian primes.
Here the words "essentially uniquely" have the follow-
ing meaning. Let
be two products of the required type for some a =t= 0
where e, e' are units and the q. and qlc are
'J
pnmes. Then the theorem should be understood to say
that r = s and that the qlc can be reordered so that is an
. f 'J
assoctate o qj for 1 <} <r; if a is a unit, r=O. If one
prescribes that the prime factors of a should be "normal-
ized", then the product is uniquely determined up to the
order of the factors.
Ordinary integers are also Gaussian integers; in order
to obtain their decomposition into Gaussian primes, it is
enough to do this for "ordinary" primes.
Theorem XIII.3. Let p be an odd rational prime. Then it is
a qaussian prime or the norm of a Gaussian prime q;
m the case p = qij, q and ij are not associates, and p
has n.o ther Gaussian prime divisor than q, ij and their
assoczate .
\
\
66
XIII
Put p=eq
1
q
2
... qr as in theorem XIII.2. Taking the
norm, we find thatp
2
is the product of the N(q_). If one of
the N( lJ.i) is p
2
, then r = 1, p = elJ.i, and p itself is a Gaussian
prime. Otherwise each N(q) is p, and we can write p =
N(q)=qq, with q a Gaussian prime; q is then also a
Gaussian prime. Put q = x + ry; if q was an associate of q,
it would be q or iq; this gives either y = 0, p = x
2
, or
x = O, p = y
2
, or y = x, p = 2x
2
; this cannot be, since p is
an odd prime.
As top= 2, its decomposition is given by
2= N(l + i) =(1 + i)(l- i) = i
3
(1 + i)
2
;
this has the only normalized prime factor 1 + i.
Theorem XIII.4. Let p be an odd rational prime. Then p is
a Gaussian prime or the norm of a Gaussian prime accord-
ing as it is congruent to 3 or to 1 modulo 4.
If it is the norm of q= x+ ry, we have p = x
2
+ y
2
,
where one of the integers x,y must be odd and the other
even. Then one of the squares x
2
,y
2
is congruent to 1 and
the other to 0 modulo 4, so that p = 1 (mod 4). Conversely,
if this is so, the corollary of theorem X1.2 shows that - 1
is a quadratic residue modulo p, so that there is x such
that x
2
+ 1 is a multiple ofp. As x
2
+ 1 =(x+ i)(x- i), this,
if p were a Gaussian prime, would imply that p divides
either x + i or x-i. Obviously this cannot be so.
Corollary 1. Every Gaussian prime is either 1 i, or an
associate of a rational prime congruent to 3 modulo 4, or
else its norm is a rational prime congruent to 1 modulo 4.
In fact, every Gaussian prime q must divide some
prime rational factor p of its norm qq; applying theorem
XIII
67
XIII.4 if p is odd, and the above remarks if p = 2, we get
our conclusion.
Corollary 2. A rational prime can be written as a sum of
two squares if and only if it is 2 or congruent to 1 modulo 4.
In fact, if p = x
2
+ y
2
, p cannot be a Gaussian prime,
since it has the divisors x ry.
It is worthwhile pointing out that this is a' statement
concerning rational integers which has been proved using
a larger ring, viz., the Gaussian integers.
EXERCISES
XIII. I. If a positive integer is written as n
2
a where a is > 1 and
square-free (cf. exercise X.7), show that it can be writ-
ten as a sum of two squares if and only if every odd
prime divisor of a is = 1 (mod 4). If that is so, and a
has r prime divisors, find the number of representations
of a as a sum of two squares.
XIII.2. If an integer is the sum of two relatively prime squares,
show that the same is true of every divisor of that
integer.
XIII.3. Using the representation of complex numbers by points
in the plane, show that, if z is any complex number,
there is a Gaussian integer q whose distance to z is
~ V2 show that among all Gaussian integers, there
2 , ,
is at least one whose distance to z is smallest, and that
there are no ore than four with that property (Hint:
cf. the proof f the lemma in XIII).
XIII.4. The congrue ce relation being defined for Gaussian
integers in t e same way as for ordinary integers (cf.
V), call f( ), for any Gaussian integer m ~ O the
number of dis inct Gaussian congruence classes modulo
68
XIII
m; show that f(mn)= f(m)f(n) for any two non-zero
Gaussian integers m, n (Hint: take representatives X;,
with 1 <,i <J(m), for the classes modulo m, representa-
tives y
1
, with 1 <,j <,f(n), for the classes modulo n, and
show that the X;+ my
1
are representatives of the classes
modulo mn).
XIII.5. Use exercise XIII.4 to show thatf(m)= miii for every m
(Hint: apply exercise XIII.4 to m and to n =iii).
XIII.6. Show that, if m is a Gaussian integer of norm > 1, the
Gaussian congruence classes modulo m make up a field
if and only if m is a Gaussian prime. Show that, if N(m)
is a rational prime, each Gaussian integer is congruent
to some rational integer modulo m.
XIII.7. If w=- + i v; , show that the complex numbers
x + yw, where x andy are ordinary integers, make up a
ring R, whose units are 1, w, w
2
. Prove that, if z is
any complex number, there is an element q of the ring
R such that N(z- q),;;;;;, t (Hint: cf. exercise XIII.3).
Hence prove the analogue of theorem XIII.l for the
ring R, and prove for that ring a unique factorization
theorem.
XIII.8. Use exercise XIII.7 to show that a rational prime >3
can be written as x
2
+ xy + y
2
, with integers x,y, if and
only if it is = 1 (mod 3).
Abelian group 17
Absolute value 62
Associate 63
Commutative group 17
Congruence class 19
Congruence modulo m 18
Coset 35
Cyclic 31
Equivalence relation 19
Euler function 25
Euler's theorem 36
Fermat's t eorem 36
Field 26
/
INDEX
Gauss' lemma 55
Gaussian field 62
Gaussian integer 62
Gaussian prime 63
Gaussian ring 62
Gaussian set 55
Generator 29
Greatest common divisor
7
Index 47
Irreducible (polynomial)
41
Isomorphism 30
Legendre symbol 57
69
70
Norm 61
Normalized (polynomial)
41
Order 31
Perfect square 11
Polynomial 39
Prime 13
Primitive root of unity 46
Primitive root 47
Principle of mathematical
induction 2
Quadratic reciprocity law
58
Rational prime 63
Relatively prime 9
Ring 23
Series of Fibonacci 7
Subgroup 18
Unitary (ring) 24
Zero-divisor 24
Other books by Andre Wei/
Basic Number Theory
Third Edition
" ... this book consists of the body of ideas usually associated with the name
of Class Field Theory, both local and global ... a coherent treatment of the
known "basic" results on which our knowledge of number h ~ r y today is
founded. It may well be regarded by latter historians as one of the "classics"
in this field, compared perhaps to Heeke's "Theorie der algebraischen
Zahlen" ... its emphasis lies on equipping the reader with the fundamental
tools and a general "analytical outlook ... "
Bulletin of the London Mathematical Society
1974/xviii, 325 pp./Cloth
(Grundlehren der mathematischen Wissenschaften, Volume 144)
ISBN 0-387-06935-6
Elliptic Functions According to Eisenstein and Kronecker
This book presents in two parts a modern, never-before-published treatment
of Eisenstein's elementary but far-reaching methods in the theory of elliptic
functions and its further development by Kronecker. Eisenstein's method,
detailed here for the first time since his original paper of 1847, leads quickly
and elegantly to all the classical theorems in the theory, as well as to results
of considerable importance in modern number theory.
A systematic explanation ofthe topics connected with Kronecker's cele-
brated "limit formula" and its application is then presented in Part II. It also
provides an introduction to the fundamental importance of much of Heeke's
work whose contributions have also become an integral part of twentieth
century mathematicians.
1976/xii, 92 pp./Cioth
(Ergebnisse der Mathematik und ihrer Grenzgebiete, Volume 88)
ISBN 0-387-07422-8