lOMoARcPSD|56020158

Algebra and Number Theory. Lecture Notes v6

computer science engg (Anna University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Priya Palraj (priya77palraj@gmail.com)
 lOMoARcPSD|56020158

∗
Algebra and Number Theory
Lecture Notes

Szymon Brzostowski

November 1, 2020

General remarks on method and criteria of assessment (2020-2021):

1. The discussion class mark is the average of the marks from two or more tests.
The mark may be increased in special cases (to students taking active part in
the classes) up to one level up.

2. There will be one regular retake (scheduled just before or during the final exam-
ination period) for those students who fail any of the aforementioned tests.

3. The lecture mark is the final exam mark (checking students’ theory knowledge),
scheduled during the end-of-term examinations.

4. The final mark is comprised of the discussion class mark (50%) and the lecture
mark (50%), provided that both are passing marks.

5. „Second sit” test/examination will take place during the resit examination period.

Dates:

end-of-term examinations (final examination period): 8–21 February 2021,

resit (second sit) examination period: 1–7 March 2021 .

. This document has been written using the GNU TEXMAC S text editor (see www.texmacs.org).

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

2 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

This text is intended to be a more detailed and formal version of the lecture itself.
In order to get the most of it, I recommend reading it with your discussion-class notes
at hand. Hopefully, this should allow for full comprehension of the material given.
Szymon Brzostowski
Notation. The symbol „ :=” will denote an assignment, for example :=2 means a
a
that the name carries the value 2. More generally, „ :=” can be treated as a defi-
nition of a new concept (on its left side) using already known concepts (appearing
on its right side). The phrase „if and only if” will be abbreviated as „iff”.

Table of contents
1 Numbers and operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Which numbers are „best”? . .. . . . .. . . .. . . . .. . . .. . . . .. . . .. . 5
3 The first abstraction – the concept of a group . . . . . . . . . . . . . . . . . . 7
4 ...Divisibility in Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5 ...Second abstraction – the concept of a ring . . . . . . . . . . . . . . . . . . 11
6 The concept of an isomorphism . . . .. . . .. . . . .. . . .. . . . .. . . .. 12
7 The direct sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
8 The third abstraction – the concept of a field . . . . . . . . . . . . . . . . . 17
9 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
10 GCD . . . .. . . .. . . . .. . . .. . . . .. . . .. . . . .. . . .. . . . .. . . .. 20
11 Solving a · x ≡n b and a ·n x = b . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12 The group Gn and the ϕ function . . . . . . . . . . . . . . . . . . . . . . . . . 26
13 Fermat’s little theorem and its generalizations . . . . . . . . . . . . . . . . 30
14 Chinese remainder theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
15 The prime numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
16 Systems of linear equations . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 42
16.1 From one to several equations . . . . . . . .. . . . . . . . . . . . . . . . . . . 42
16.2 Triangular systems and back substitution . . . . . . . . . . . . . . . . . . . 45
16.3 Matrix notation for a linear system . . . .. . . . . . . . . . . . . . . . . . . 46
16.4 Row echelon form of a matrix . . . . . . . .. . . . . . . . . . . . . . . . . . . 50
17 The algebra of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
18 Which matrices are invertible? . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
19 Invertibility and determinants . . . .. . . .. . . . .. . . .. . . . .. . . .. 62
20 Linear systems revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

1. Numbers and operations 3

1 Numbers and operations

We begin by setting the terminology for the basic number sets:
! the naturals (=positive integers): N :=f1; 2; 3;:::g,
! the integers: Z :=f0; 1; 2; 3;:::g,
n o
! the rationals: Q := pq : p 2Z;q 2N ,
! the p2; p
;
q reals:
p R; it is a set larger than Q; it contains
p e.g. the radicals ( p3

4+ 7;:::) and also other numbers, like π; e; π +1;:::.

10
10
3 5

Note that by convention 0 2/ N. The symbol N will denote the set N [f0g. 0

There is one more set of numbers, easily constructed from R:

! the complex numbers: C := + i: fa b
a;b 2 g
R . Here two complex numbers are
added and multiplied similarly as polynomials, but further simplification of the


result is possible because the new number „i” satisfies i2 =i i= 1 .

Clearly, we have the following chain of inclusions: N $Z $Q $R $C.

Example.
1. Here’s how you add two complex numbers:
= terms3+(1 1)
i=3+0
i=3.
(2+i)+(1 i)skip the=brackets2+i+1 icollect similar
2. And here is multiplication:

(2+i)
(1 i) = 2
(1 i)+i
(1 i)=

2 2
i+i
1 i
i=
use the distributive law
=
2+( 2+1)
i ( 1)collect similar
distributive law again
=
use the relation fori
2
= terms3 i.

Analyzing the first example above, it is not hard to produce a general rule for the

8
addition of complex numbers:
Addition Rule in C.

a;b;c;d 2R
(a +b i)+(c +d i):=(a +c)+(b +d)i.
8
(The universal quantifier is read „for all”.)
A similar formula for the product of two complex numbers holds (try to find it yourself!):

8
Multiplication Rule in C.

a;b;c;d 2R
(a +b i)
(c +d i):=(a
c b
d)+(a
d +b
c)
i.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

4 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Observe that thanks to using symbols instead of specific numbers, above there are
How
formulas that work for every choice of (real) values of . So although it is enough a;b;c;d
for you to know how to calculate with complex numbers to arrive at the correct result,
Algebra
these formulas give you the result almost automatically once you remember them. In
works
algebra you generally work with symbols and you calculate using a certain set of rules
for manipulating the symbols. Some of these rules you should already be familiar with.
The basic rules for computations with numbers are

! 2+1=1+2; + = + , and – in symbols –

1 1 1 1

a +b =b +a (commutativity)
2 3 3 2

(This law allows you to change the order of the summands.)

! ( 1+2)+ =1+ = = 1+ = 1+ 2+
3 3 5 7 3

, and – in symbols –
2 2 2 2 2

a +(b +c)=(a +b)+c (associativity )

(This law allows you to skip all brackets when adding – the result is always the
same regardless of which numbers you add first.)

! (2+1)
=3
=1= + = 2
+1

1

3
1

3
2

3
1

3
1

3
1

3
, and – in symbols –
(a +b)
c =a
c +b
c (distributivity)
(This law allows you to distribute multiplication over addition.)

Note that the first two rules above are also true when multiplying numbers (i.e. with


+ replaced by ). This suggests that perhaps such rules could be interpreted more


abstractly. Namely, the symbol + (or ) might denote an unspecified binary operation.
Of course, in such generality it might be appropriate to use some new symbols (like , 


, , or ) for the binary operations and sometimes it is done so, especially when
there is a danger of some confusion. Observe however, that in the case of complex
numbers that we have considered, we used the ordinary symbols + and , rather than

some new ones, and we called them „addition” and „multiplication”, respectively. This
is natural, because those operations are in fact extensions of the usual operations of
addition and multiplication from the real numbers to a wider domain (this means that
the „new” binary operations work in the „old” way for those complex numbers which
are real, e.g. (2+0i)+(3+0i)=5+0i and similarly (2+0i) (3+0i)=6+0i). Also

in computer science, a common practice is to implement some new binary operations


and still denote them by + and although in fact they overload or even totally redefine
the standard operations of addition and multiplication.

Example. One can define a truncated subtraction in N0 by the formula

 0,
a +b := a b, ifif a<b
a >b .
There is everything in order with such definition, but you should feel that the usage
of + is a little cumbersome here (after all, we are rather subtracting than adding). In
elementary arithmetic this truncated subtraction is usually denoted by „ . ”.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

2. Which numbers are „best”? 5

2 Which numbers are „best”?

There is no unique answer to such question, because it depends on the properties
you are interested in. For example, testing associativity and commutativity gives
N Z Q R C
Ass. YES YES YES YES YES
+
Com. YES YES YES YES YES ,
Ass. YES YES YES YES YES
·
Com. YES YES YES YES YES
so in these respects there is no apparent difference between N, Z, Q, R and C. Actually,
in principle, in order to verify that the entries in the above table are correct, it would
be enough to check these properties for C because then they are automatically valid for
the smaller sets N, Z, Q and R. In practice, this is done the other way around because
of the order in which the number sets are actually constructed (N Z Q R C). ! ! ! !
As an example of such verification, try:
Exercise 1. Check that + and
are associative and commutative in C (assuming you know this
for R!) using the formal definitions of + and
given on page 3.

Commentary. Proving the usual empirical properties of the operations + and is not

totally trivial, even for N. First, one needs to properly define the set N (this can be done


using Set Theory) and the operations + and . Only then is it possible to actually prove
their properties (this is done in a branch of mathematics called Theoretical Arithmetic).
Fortunately, you have so much empirical evidence for their validity from everyday life,
you should not feel uncomfortably using those properties.
Going back to our question again: are the various sets of numbers essentially
different? Yes, they are... But only when you start thinking about solving equations
in them. Suppose we want to solve the equation 2+ =1 in the naturals. Clearly, this x
is impossible because we have
N 1 2 3x2 ::: !
a result always greater than 1!
2+x 3 4 5 :::
But the same equation has a (unique!) solution = 1 in Z. A difference! x
The following table shows which equations can be solved in the various number sets:
Equation to solve N Z Q R C
a +x = b NO YES YES YES YES
a
x=b; a =/0 NO NO YES YES YES . (1)
x =2 2
NO NO NO YES YES
x= 1
2
NO NO NO NO YES
As we can see, Q is different than Z if considered with multiplication (e.g. 2 =1
x
has no solutions in Z; on the other hand the equation 3 = 5 does have the solution
2 3

x
x = 109 in Q). Also, C is „better” than the other sets with respect to . But what is

the difference between Q and R? Part of the answer is shown in the above table. The
full answer is beyond the scope of Algebra: the real difference is that in R there exist
„limits” for all the sequences that „should have” a limit. The same property is true for
C. Hence, R and C have different analytic features than Q.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

6 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Example. The sequence ; + ; + + ;::: has no limit in Q but it does have a

1

12
1

12 22
1 1

12
1

22
1

32

limit (or converges) in R to the number . This can be written as + + +::: = .

π2 1 1 1 π2
6 12 22 32 6

Table (1) may seem to suggest that the complex numbers are „the best”. This is,
indeed, true in many respects but not in all of them. For example, the numbers N, Z,
Q, R are linearly ordered, thus are comparable and can be drawn on a line:

/ 1 p2 2 3 π +1

8 8
1
2

More importantly, this ordering 6 is compatible with the +,
operations: a 6 b ,

a c 6b c a;b;c2
+ + and
R
a6b,a
c 6b
c a;b;c2 ^c> . Such ordering is not possible forR 0

C. Still, there exists a nice way to visualize complex numbers – they can be drawn on
a plane.

2 3+2
i The complex number 3 + 2 i is plotted

;
as the point (vector) (3 2) on the plane
R2. Similarly, the real number 1 + 0 i

is plotted as the point (vector) (1 0) in ;
R2. Such visualization is called Argand
1 3 Diagram.
Argand Diagram.
Under this visualization, the operations + and on complex numbers can also be inter-

preted graphically. For now, we content ourselves with the interpretation of addition,
multiplication being more involved.
z1 z +z
1 2
The sum of two complex numbers 1 = z
a b z c d
+ i and 2 = + i is the complex
z z a c b d
number 1 + 2 =( + )+( + )i. Hence,
the addition of complex numbers is just
z 2
the addition of vectors in the plane R2
according to the „parallelogram law ”.
Addition of complex numbers.
On the other hand, are the natural numbers N „worst”? No, because they have
another advantage: besides being ordered they are well-ordered , which means that
A ?
every subset = / of N has a unique minimal element. This allows one to prove the-
orems concerning N using a technique called mathematical induction. Moreover, the
naturals (more generally: the integers) have fascinating arithmetic properties connected
with the notion of divisibility.

Example (the well-ordering principle of N). The set := the natural numbers A f
g f ; ; ;:::g
that are divisible by 2 and 5 = 10 20 30 has its minimum equal to min =10. A
We can sum up the above discussion by agreeing that there are various possible
viewpoints on the properties of numbers; hence there is no obvious choice of „the best
numbers”. The various viewpoints are developed in different branches of mathematics:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

3. The first abstraction – the concept of a group 7

Number Theory
.% Algebra
(properties of binary
operations)
& Linear Algebra
(divisibility and prime (vectors, matrices and
numbers) operations on them)
The lectures will cover the very basics of these three branches of mathematics.

3 The first abstraction – the concept of a group

As we saw, the sets of numbers have different properties with respect to solving
equations of the form a  x = b, where  is a binary operation (+ or
). Moreover, the

operation itself often has some „nice” features (associativity, commutativity). Such
observations have led to an abstract notion of a group which allows one to describe this
type of phenomena in a unified way.
G
Definition 1. (Group) Let be a set together with a binary operation
: GG!
G G G;
)) if the
8
. We call a group (more formally: a group is the ordered pair (
following axioms are satisfied:

98 98
G1 ◦.
a;b;c 2G
(a
b)
c =a
(b
c) (associativity)

G2 ◦. !
e 2G a 2G
a
e =e
a =a (existence of identity element)

G3 . ◦
a 2 G b 2G
a
b = b
a =e (existence of inverse element).

The element e 2G involved in G2  and G3  is one and the same and is called the
identity, while the element b 2G satisfying G3  is called the inverse element of a 2
G and denoted by a . Hence, G3  can be written in the form a
a =a
a=e.
8
1 1 1

If moreover
G4 ◦. a
b =b
a
a;b 2 G
(commutativity)

then the group (G;
) is called commutative or abelian.

98
(The existential quantifier 9 is read „there exists”. The symbol 9! means „there exists
exactly one”.)
Exercise 2. Show that the condition G2◦ is equivalent to the condition G2 0 a
e=
e 2G a 2G
e
a = a; in another words, an element e 2 G satisfying G2 0 is the element.
Exercise 3. Show that in a group G the element a 2 G inverse to an element a 2 G is indeed
1

the element, that is show that a 1 is unique.

We want to emphasize that the symbol in the definition of a group denotes an
abstract binary operation. Since, however, it resembles the ordinary multiplication,
G
sometimes one says that the group is in multiplicative notation. In this case, the dot

is usually omitted so that ab
means a
b
and the identity is denoted by 1. Similarly, e2G
G;
for a group ( +) one may say that it is in additive notation. In this case, one uses
the symbol a
for the inverse element to a 2G
, and the identity is often denoted by 0.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

8 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

At first sight, the definition of a group does not seem to be connected with the
equations ax b a;b 2G
=, . But it turns out that in a group such equations are always

8
solvable. We list this together with some other basic properties of groups:
Property 1. Let (G;
) be a group. Then

8
1.
a;b 2G
(a ) =a ^(ab) =b a
1 1 1 1 1

89 89
2.
a;b;c2 G
((ac =bc) )a =b) ^((ca =cb) )a =b) (cancellation laws)

3.
a;b 2G c 2G
!ac =b and a;b 2G d2G!da =b (solvability of ax=b and xa =b).
Commentary. Property 1 works for all groups; in particular it is valid for the example
groups given below. This is a manifestation of the power of abstract thinking.

8
So far, we have not spoken explicitly about the division „/” and subtraction „ ”

8
operators. The reason for that is that in a group they can be defined using the group


operation (or +). Namely, in the additive case we put a;b 2G
a b :=a +( b) and in
a/b = a :=a
b 1
the multiplicative case —
a;b 2G b .

Examples of groups. (Some of these will be discussed in greater detail at the classes.)
; ; ; ; ; +); (Z; +); (f0g; +) are abelian groups with respect to the
I. (C +) (R +) (Q
usual addition.
;
; ;
; ;
; f g;

II. (C ) (R ) (Q ) ( 1 ), where the asterisk means we exclude the number 
0, are abelian groups with respect to the usual multiplication (check this for C!).
III. (R+;
); (Q ;
), where R :=(0; +1), Q :=Q \R , are also abelian groups.
+ + + +

/ ?. The set of functions f: X !X that are bijections (that is functions

8
IV. Let X =
which are one-to-one and onto) with the operation  of composition of func-
tions is a group. Explicitly: f  g: X !X is a function defined as (f  g)(x):=
x2
f(g(x)). We will denote this (usually non-abelian!) group by (Bij(X); ).
X

V. If X = f1;:::;ng, where n 2 N, then the elements of Bij(X) are called permuta-

tions. The set of such permutations is denoted by Sn. By example IV, (Sn; )
is a group with respect to composition of functions. This group is called the
symmetric group of degree n.
 k
VI. The set n := cos n +i sin n : k =0;:::;n 1 , where n 2 N, consists of n-th
2 k
π 2 π

roots of unity that is for every  2 n we have 
:::
 = n =1. With respect to
||{z}
|n|| }}
}}}
(complex) multiplication, ( n;
) is an abelian group.
factors

VII. The circle S C with center 0 and radius 1 consists of the complex numbers of
1

the form z =cos '+i sin ', where '2[0; 2 π). S is an abelian group with respect 1

to the complex multiplication. (This, as well as example VI, follows from the
formula for the product of two complex numbers written in their trigonometric
' '
form : (cos +i sin )(cos +i sin )=cos ( + )+i sin ( + )). ' '

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

4. ...Divisibility in Z 9

;M
VIII. Let X be any set. The pair (2X ), where 2X is the set of all the subsets of
the set X and
denotes the symmetric difference of sets that is := AMB
( A[ B n A \ B
) ( ), constitutes an abelian group.
IX. Consider the set Bn of binary strings of length . We may define a bitwise oper- n
ation on such strings using the exclusive or (xor) operation. Namely, for bits
we put:
Input xor
0 0 0
0 1 1 ;
1 0 1
1 1 0
so that e.g. 0 xor 0=0 and so on, and for two binary strings = 1 n, = 1 n s s :::s t t :::t 2
s t s t ::: s
Bn we put: xor :=( 1 xor 1) ( n xor n) (e.g. 01 xor 11 =(0 xor 1)(1 xor 1)=t
;
10). The ordered pair (Bn xor) is a group (check it!).

The last example turns out to be a very special case of a more general phenomenon,
having its source in Number Theory. Namely, this is an instance of modular arith-
metic... (see Section 7 for an explanation of this connection)

4 ...Divisibility in Z
The basic definition is:
Definition 2. Let k;l 2 l
Z. We say that divides , and we write or 0(mod ) k l j k k l
k l
(read: „ is congruent to 0 modulo ”), if there exists an integer Z such that m2
l
m k l
= . We may also say that is a divisor of and that is a multiple of . k k l
Example. 3 j 6 because 3
2=6.
What happens if an integer k is not divisible by an integer l? We may perform a
„partial division”:
Theorem 1. (Division with remainder) Let k; l 2 Z; l =/ 0. Then there exist
(unique!) integers q;r
such that
k = ql +r and 0 6r<jlj (2)
q is called the partial quotient and r – the remainder ( on division of k by l).
(In the above theorem j
j denotes the modulus (or the absolute value) of a real number
which is equal to its distance from 0.)

Example. Clearly, 5 - 7 (= „ 5 does not divide 7”). But we have

7=2
( 5)+3
q r
and 0 6 3 < j 5j =5. Similarly, if we want to divide 5 by 7 we get 5 =0
7 +5 with
q r
0 65 <7.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

10 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Notation. If r is the remainder as in ( 2) we will write r =k (mod l).

Note that by the definition of remainder we always have k (mod l) 2f0;:::; jlj 1g.
Hence, for a natural l > 2 we define the set Zl :=f0;:::;l 1g and we may think of
it as the set of remainders modulo l. The amazing thing about Zl is that there exist
natural operations in it. Suppose we want to add two numbers m;n 2 Zl . What should
the result be like? Well, it should be a number, but it should also belong to the set Zl.
There is no problem with it if m+n<l — we can safely take this as the correct result
in Zl. But what if m+ n > l? Recall that Zl is the set of remainders, so perhaps we
should compute the remainder (m+n)(mod l)... This turns out to be the correct guess.
We pose the following:

8
Definition 3. (Modular addition and multiplication)

m+l n:=(m+n)(mod l) .
m
l n:=(m
n)(mod l)
m;n 2Zl
Clearly, we defined two operations +l;
l: Zl !Zl. What are their properties?
Theorem 2. (The algebraic structure of Zl)
1. (Zl ; +l) is an abelian group with the number 0 2Zl as the identity.
2.
l is associative and commutative and has 1 2 Zl as the identity.
3.
l is distributive over +l that is
a;b;c2 l
8
(a +l b)
l c =(a
l c)+l (b
l c).
Let us illustrate these properties with some specific examples.
Z

Example.
! 2+ 3=(2+3) mod 5=5 mod 5=0; hence 3 is the + -inverse element to 2 and
5 5

this fact can be written as (cf. the comments on page 7 following Definition 1)
2=3 (in Z5); more generally, for Zl it holds =( )(mod ) . a2 a l a l
! (1+ 2)+ 3 =(3 mod 7)+ 3=3+ 3=6 mod 7=6 and
7 7 7 7

1+ (2+ 3) =1+ (5 mod 7)=1+ 5=6 (an example of associativity of +l)

7 7 7 7

! (4
5)
6 =(20 mod 9)
6=2
6=12 mod 9=3 and

4
(5
6) =4
(30 mod 9)=4
3=12 mod 9=3 (an example of associativity of
l)
9 9 9 9

9 9 9 9

! (2+ 3)
4 =(5 mod 5)
4=0
4=0 mod 4=0 and

(2
4)+ (3
4) =(8mod 5)+ (12 mod 5)=3+ 7=10 mod 5=0 (an example of
5 5 5 5

5 5 5 5 5

the distributive property)

Convention. To simplify the notation, we may write just + and in place of
+l and


l (respectively) upon remarking that the calculations are performed in Zl.
Theorem 2 shows that the triple (Zl; +l;
l) constitutes a quite nice algebraic struc-
ture. Note also that those nice properties seem to be inherited from (Z; +;
), where they
also hold. More generally, every triple (Q; +;
), (R; +;
), (C; +;
) has such properties,
too (check this for C!). Thus we have come to our...

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

5. ...Second abstraction – the concept of a ring 11

5 ...Second abstraction – the concept of a ring

R
Definition 4. (Ring) Let be a set with two operations + : . We say ;
RR!R
that R R; ;

(or more precisely: the triple ( + )) is a ring (with unity) if
1. (R; +) is an abelian group (see Definition 1) with identity denoted by 0
2.
is associative
1 2R for

8
3. there exists an identity element
4.
is left and right distributive over +, that is
r
(s +t)=(r
s)+(r
t) :
r;s;t 2R (s +t)
r =(s
r)+(t
r)
If, moreover,
is commutative we say that R is a commutative ring (with unity).
Convention. It is customary to agree that
has greater priority than +. This allows
one to skip some brackets. For example, we can simply write (a + b)
c = a
c + b
c
because we understand that the products ac, bc should be computed first, and only
after that may we compute the value of a
c +b
c by performing the addition.

Equipped with this new notion, we can restate Theorem 2 as:

Theorem 2’. (The algebraic structure of Zl) For every l 2 N, l > 2, the triple
; ;

(Zl +l l) is a commutative ring with unity.
We have already mentioned (implicitly) some examples of rings at the end of the
previous section. Explicitly:

Example.
I. (Z ; +;
), (Q; +;
), (R; +;
), (C; +;
) are commutative rings with unity.
II. By Example VIII page 9, (2 ; M) is an abelian group. One can check that (2 ; M;
X X

\) constitutes a commutative ring with unity (what are its identity elements?).
III. If R is a ring then the set R[X] of polynomials with coefficients in R (that
is „formal sums” of the form r + r X + ::: + rn Xn where r ; :::; rn 2 R,
n 2 N ), together with the natural operations of addition and multiplication of
0 1 0

polynomials, is a ring (commutative if R is commutative) (R[X]; +;
).

0

IV. Let X = / ? and let R be a ring. The set R of functions f: X !R is itself a ring

8 8
X

if considered with the following (natural) operations:

f + g is a function defined as x2 (f + g)(x):= f(x) + g(x) ,

8 8
1.
f ;g 2RX X
addition in R

2.
f ;g 2RX
f
g is a function defined as x2 (f
g)(x):= f(x)
g(x) .
X
multiplication in R
Moreover, if R is commutative then also (R ; +;
) is a commutative ring.
X

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

12 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

6 The concept of an isomorphism

Looking at the last example on page 11, let us notice that the ring X embeds R
R R
the ring in a natural way. Namely, in X there are constant functions X 3x 7!r 2
R and one can identify the elements of R
with such functions in X. This type of R
identifications are made throughout algebra. Upon such identification, one can just
write R R X
R R
as if were indeed a subset of X (although, strictly speaking, it is not).

8
The reason why this does not lead to a confusion is that the set of constant functions
R R
in X is an isomorphic copy of the ring (see definition below), so one can calculate
with these constant functions in the same way as in R. If, for example, = Z then R
we have: 1+2=3 ,x2 x x x x
1( )+2( )=3( ), where 1( ) is the constant function sending
every x 2 X to 1 2 Z and similarly for 2(x), 3(x).
X

Let us give an intuitive definition of the concept of an isomorphism, which is central

in the whole of algebra.
Definition 5. (Isomorphism) Let (A ), (B; ; ; :::
) be two algebraic;
; ; :::
structures with the same number of binary operations and some distinguished
; ;::: 2
; ;::: 2
8
elements 0 1 A, 0 1 B. We say that the structures A and B are isomorphic
' !
if there exists a bijection : A B such that
1.
a;b 2
'(a b)= '(a)
'(b) ^ '(a b)= '(a)  '(b) ^:::,
A

2. '(0)=0;'(1)=1;::: .
The bijection ' is then called an isomorphism ( of the structures A and B). The
notation A  =B or A 
'
=B will indicate that A and B are isomorphic (by means of
the isomorphism ').
If we do not require ' to be a bijection (so it is just a function from A to B)
but the conditions 1 and 2 are satisfied for ', we call such a ' a homomorphism
of the structures A and B.

How does this general definition specialize to groups? We give

Definition 6. (Isomorphism of groups) Let (G;
), (H; ) be two groups. We say

8
that G is homomorphic to H if there exists ': G!H such that

a;b 2G
'(a
b)= '(a)'(b);
'
this is called a (group) homomorphism.
'
If, moreover, is a bijection, it is called an isomorphism ( of groups) and the
groups G
and H G H G H
are said to be isomorphic. In symbols: = or = .
'

The question is: why in this definition do we not require ' to satisfy condition 2
of the general Definition 5? The answer is simple: in case of groups this condition is
automatically satisfied for a group homomorphism '. Namely, if e 2 G and e0 2 H
are the identities (=„the distinguished elements”) of the respective groups, we have:
'(e)e0 ='(e)='(e
e)='(e)'(e) and by Property 1 item 2 applied to the group H
this implies that '(e)=e0 , which is the missing condition.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

6. The concept of an isomorphism 13

In general however, such good behaviour cannot be taken for granted. For example,
' ; ;
! ; ;

we may define :(Z + ) (Z + ) by the formula ( ):=0 for 'k k2
Z. It is immediate to
'k l 'k 'l ' k
l
notice that ( + )=0= ( )+ ( ) and ( )=0= ( ) ( ) for all integers ' k
' l , so k;l
'
one might be tempted to treat as a homomorphism of rings. This is ok if one considers
rings without unity (sometimes it is done so), but according to our definition (Definition
4) a ring has got the distinguished element 1 so its homomorphism should carry 1 to 1.
Thus, in case of rings (with unity) we must explicitly demand this condition:
R; +;
), (S; 6; ) be two rings. We
8
Definition 7. (Isomorphism of rings) Let (
R S
say that is homomorphic to if there exists ': R!S such that
1.
a;b 2R
'(a +b)= '(a) 6 '(b) ^ '(a
b)= '(a)'(b),
2. '(1)=1;
this ' is called a (ring) homomorphism.
If, moreover, ' is a bijection, it is called an isomorphism ( of rings) and the
rings R and S are said to be isomorphic. In symbols: R  =S or R =S.
'

Again, here the condition '(0)=0 is automatic since Definition 7 implies that this ring
homomorphism ' is also a homomorphism of the additive groups (R; +) and (S; 6) in
the sense of Definition 6.

Examples (check!).
1. For a group G R
(or a ring ) the identity function Id defined by Id( x) := x, for
x 2 G x 2R
( ), is always an isomorphism of groups (rings).
2. The group (Z; +) is isomorphic to the group (2 Z; +), where 2 Z :=f2
k: k 2 Zg
is the set of even numbers. The isomorphism can be specified as '(x):=2 x, x2Z.
3. For the group (R; +) one can define an automorphism (i.e. an isomorphism of
a group (a ring,...) with itself ) by the formula '(x):= x, for x 2 R.
4. Similarly, the function ' given by '(z):=z, z 2C, (here the bar denotes complex
conjugation) is an automorphism of the ring (C; +;
).
5. For the group (Q;
) one can define its homomorphism into the group (Q> ;
) as
'(x):=jxj, x2Q (here Q> :=fq 2Q: q>0g). Another possible homomorphism
0

of this type is (x):=x , x 2 Q .

0
2

6. Let l 2 N, l > 2. The function ' given by '(x) := x (mod l), x 2 Z, is
a homomorphism of the rings (Z; +;
) and (Zl; +l;
l).
7. The function ':(R;+)!(R> ;
) given by '(x) :=2x, x 2 R, is a group isomor-
0

phism.
R X ; ;

8. For a polynomial ring ( [ ] + ) (see Example III on page 11) and a chosen ele-
mentr 2R ' ' w wr
one can define the evaluation homomorphism r by r( ):= ( ),
w 2R X R; ;

[ ], into the ring ( + ).
9. The group ( n;
) of n-th roots of unity is isomorphic to the group (Zn; +n).
k

The isomorphism can be given by the formula ' cos n +i sin n
k

:=k, for
2 π 2 π

k 2f0;:::;n 1g.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

14 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Let us use the last example as an illustration of the concept of an isomorphism.

f;; ; g
Consider 4 = 1 i 1 i . In this case, the isomorphism of example 9 above works as
follows:
Z4 '
1 !
4

0
i ! 1
1 ! 2
i ! 3
Under this identification, let as compare the multiplication (addition) tables of the
respective groups:

1 i 1 i +
4 0 1 2 3
1 1 i 1 i 0 0 1 2 3
i i 1 i 1 1 1 2 3 0
1 1 i 1 i 2 2 3 0 1
i i 1 i 1 3 3 0 1 2

This direct inspection shows that the above tables are essentially identical. Namely,
let us try to forget about the actual values represented by the various numbers (1 i ; ;:::;
; ;::: ; ;:::; ; ;:::
0 1 ) and try to think of them as names (810 8i0 800 810 ) and similarly we may


think about an abstract operation instead of and +4. Better yet, let us introduce
new names, e.g. a;b;c;d
. Then the above two tables can be written in a unified way:

 a b c d
a a b c d
b b c d a
c c d a b
d d a b c
This table represents a group ( fa; b; c; dg; 
) much in a way Algebra actually
treats the groups it studies – this representation is more abstract than the two specific
representations above. Seeing this amounts to noting that the substitutions :=1 :=i a ;b ;
c ;d 

:= 1 := i and := lead to the table of the group ( 4 ) while the substitutions ;

a ;b ;c ;d 
:= 0 ; =1 := 2 := 3 and :=+4 lead to the table of the group (Z4 +4) (see ;
above). Thus, the concept of an isomorphism gives us a way to say that two given
groups (rings,...) are just instances of one and the same abstract group (ring,...). This
„abstract structure” is what Algebra is actually interested in, because it can be studied
without contemplating „the nature of its elements” and the real interest, which lies in
the properties of the binary operation itself, is more transparently exposed.
There is a close analogy between this point of view on groups and object-ori-
ented programming – specific groups are instances of an „abstract group” just the
way specific objects are instances of the class they instantiate. Keeping this analogy,
one might also say that Algebra is concerned only with the properties of the classes,
not the objects themselves.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

7. The direct sum 15

To illustrate with what sort of properties Algebra is interested in, let as define the
r R
notion o a zero-divisor in a ring: an element of a ring is called a (left) zero-divisor
s2R s , = r
s
/ 0, such that =0. Let r 2R R

if there exists be a zero-divisor in a ring and
R; ;
R; ;

' ^
^
let ( + ) =( + ^). We have r
s =0 for some element . Hence, (0)= ( )= s2R ' ' r
s
'r
's
( )^ ( ). By the comments after Definition 7 we know that (0)=0 which means that '
'r
's '
we get the relation 0= ( )^ ( ). Since is one-to-one and = / 0, also ( )= / 0. Bys 's
the above definition this means that the element ( ) (identified with 'r
by means r 2R
' ^ R
of the isomorphism ) is also a zero-divisor in the ring . Thus the property of „being
a zero-divisor in a ring” is an invariant of isomorphisms. Of course, one may similarly
define and analyze the notion of a right zero-divisor . In the following „a zero-divisor”
will stand for a left or right (or maybe simultaneously left and right) zero-divisor.
We summarize some basic properties of morphisms, often used in practice:
Property 2. Let ': G!H, : H!K be homomorphisms of groups (rings). Then:
1.  ' is also a homomorphism,
2.  ' is an isomorphism if ' and are isomorphisms,
3. if ' is an isomorphism then also ' is an isomorphism, 1

4. the set Aut (G) of automorphisms G!G is a group with respect to com-
position of maps ,
5. if G is a group then
x 2G
8
'(x )=('(x)) .
1 1

7 The direct sum

Let us go back to example IX on page 9. The table for the xor operation on bits
can be compared against the following table:

Input +
2

0 0 0
0 1 1 :
1 0 1
1 1 0
;
The immediate conclusion is that we have (Z2 xor) =(Z2 +2) i.e. the operations xor ;
and +2 are the same in Z2. Moreover, we extended this xor =+2 to binary strings of
n
length , bitwise. Whatever „a string” means to you, you should agree that working
with binary strings in a bitwise way is the same (=the resulting algebraic structures are
n
isomorphic) as working with -tuples ( 1 k ;:::;k 2 |||||
n) Z2 :::}}}}}}}}
|n|||{z}
Z2 componentwise, e.g.
factors

(1; 0)+ (1; 1)=(1+ 1; 0+ 1)=(0; 1):

2 2 2

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

There is a concept generalizing this idea.

Definition 8. (Direct sum of groups) Let ( +) and ( + G;
^) be two groups. H;
Consider the set GHof ordered pairs of the form ( ), where , . In a;b a 2G b 2 H
G H we define a new operation 
by the formula
(a;b) (c;d):=(a +c;b +
^ d):
Then ( G  H;  ) is a group called the direct sum of the groups and . This G H
G H
group is denoted by the symbol .
If e 2 G; e 2 H
0 are the identity elements of the respective groups then the
identity of the groupG H e;e
is equal to ( 0). Also, we have ( )=( ), a;b a; b
where a (resp. b a 2G
) is the inverse element to (resp. ) in the group b 2H G
H
(resp. ).
Commentary. The above definition can be extended to rings and other algebraic struc-
tures in an obvious way, and also to an arbitrary number of such structures by consid-n
n
ering -tuples instead of pairs.

;

If the operations are denoted multiplicatively (e.g. ^) then sometimes one speaks
about direct product of groups instead. The direct product is denoted by . In G H
fact, for our applications those notions are one and the same, and we may use either
terminology, whichever seems to be more convenient.
Example.
! We can construct the direct sum Zn R of (Zn; +n) and (R;
): its elements are
k;r 2 
the pairs ( ) Zn R and
(k;r) (l;s):=(k +n l;r
s):


Here, the identity is equal to e:=(0;1) and (k;r)= ( k)mod n; r because (k;
r)  ( k) mod n; r
= k +n (( k) mod n);r
r
=(0; 1)=e.
1

1 1

! Another example of a direct sum is just the n-dimensional space Rn with coordi-
natewise addition of real numbers (here  becomes the usual addition of vectors).
Is there any relation between the groups G, H and their direct sum G H? Well,
note that usually when we think e.g. about the plane R2, we think of it as embedding
the line R, as in the following picture:
R
R2

Hence, the real numbers are identified with the subset R 0 of R2. A similar idea f g
G;
works in the general case. If ( +) and ( + H;
^) are groups with identities equal to 0, 0^
(respectively), we may define the following maps:
G: G3x7!(x; ^0) 2GH and H: H 3 y 7!(0;y) 2GH:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

8. The third abstraction – the concept of a field 17

 
It is straightforward to check that G, H are injective (=one-to-one) homomorphisms;
GH
hence in there are isomorphic copies G( )=  G Gf g
0 and H ( )= 0  H f gH
of the
GH
groups , , respectively. As explained earlier, from the point of view of Algebra we
may thus think that GGHand H GH
. It is worth to note that similar identi-
fications are made in other branches of mathematics, for example in Analysis one also
often treats R as a subset of Rn.

8 The third abstraction – the concept of a field

A careful reader might have noticed that so far we have not spoken anything about
R; ;

the situation when in a ring ( + ) not only is the equation + = , a x b a;b 2R
, solvable
but also the other equation =, a
x b a;b 2R a
, = / 0, has a solution in (this is the case R
for the rings Q, R, C – see table (1)). To set the terminology, we give now the missing
definition.
R; ;

Definition 9. (Field) Let ( + ) be a ring with unity such that 0= / 1.
1. An element , = a 2R a
/ 0, is called invertible if there exists such that b 2R
a
b
=1 and b
a
=1. In this situation the element1 is called the inverse b
a
element of the element and is denoted by 1
or a . a
2. If every non-zero element a2R is invertible then the ring R is called a skew
field or a division ring.
3. If a skew field R is also a commutative ring then R is called a field.
Examples.
! The ring (Z ; +;
) is not a field because the only
-invertible elements are 1 and
1.
! As remarked above, Q, R, C are fields with the usual addition and multiplication.
! In R4 one can introduce the structure of a skew field obtaining the set H of
quaternions which contains C as a subset.
! In Z2 = f0; 1g we have 1
1=1 so 1 is invertible (this holds in any ring). Hence
; ;
) is a (finite) field.
2

(Z2 +2
! In Z = f0; 1; 2g we have of course 1
1=1 and moreover 2
2=1. Hence also
2

(Z ; + ;
) is a field.
3 3 3

! In Z =f0; 1; 2; 3g we have 1
1=1, 3
3=1 but the element 2 is not invertible

3 3 3

(check!). Hence (Z ; + ;
) is not a field!

4 4 4

4 4 4

In the last example a direct inspection showed that 2 does not have a multiplicative
inverse in Z . Even worse, 2 is in fact a zero-divisor in this ring because 2
2=0. For
n2
4 4

larger rings Zn (i.e. for big N) such verification could be very tedious (or even com-
putationally infeasible) without some additional knowledge. For instance, checking if an
element a2 Z1000 is invertible requires (potentially) the computation of 999 products.
Hence, our next medium-term objective is to characterize the invertible elements in
Zn and learn how to compute the inverses. This will be done in Section 11, because to
accomplish this we need some new tools. But first, let us note a necessary condition
for invertibility, suggested by the last example above.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

18 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Property 3. If a2
Zn is an integer such that then is a zero-divisor in Zn aj n a
and has no multiplicative inverse. More generally, in any ring a zero-divisor is
not invertible.

The notion of an isomorphism in case of fields is essentially the same as the one for
rings. Since, however, fields have „better” multiplicative structure than rings, one can
state a seemingly weaker definition:
Definition 10. (Isomorphism of fields) Let (K + ; ;
), (L; 6; ) be two fields. We
say that K is homomorphic to L if there exists : K ' !L such that '=/0 (i.e. ' is
8
not identically equal to 0) and

a;b 2K
'(a +b)= '(a) 6 '(b) ^ '(a
b)= '(a)'(b);
'
this is called a (field) homomorphism (or an embedding).
'
If, moreover, is a bijection, it is called an isomorphism ( of fields) and the
fields K and L are said to be isomorphic. In symbols: K =L or K =L.
'  
In order to explain why this definition gives an isomorphism in the sense of the general
'
Definition 5 we note the following: since of Definition 10 satisfies =
/ 0, we can choose '
x2 K such that ( )= 'x
/ 0 ' x ' x

and then we get ( )= ( 1)= ( ) (1) which multiplied ' x
'
'
by '(x) gives (1)=1. This is all that we need, because the relation (0)=0 holds for
1
'
the same reasons as in the case of ring homomorphisms. But there is more to the story:
Property 4.
! A field has got no zero-divisors other than 0 (=it is an integral domain).
! Every field homomorphism is injective (hence the name emb edding ) .
Note that the latter property means that in order to check if a field homomorphism is
in fact field isomorphism, it is enough to check if it is „onto”.
Property 3 explained that an invertible element of Zn cannot divide the number
n

. But this is not enough, as it turns out (e.g. 6 9 6=0 in Z9 and 6 9). The invertible -
elements of Zn turn out to be exactly the non-zero-divisors. We will see this shortly,
but first let us change our language a little...

9 Congruences
n
The concept of „calculating modulo ” can be extended to the whole set of integers,
which has proved to be quite useful in applications. First we give the basic definition.
Definition 11. (Congruent numbers) Two integers , are said to be congruent kl
n
modulo , where n2
N, if k l n
0(mod ) (see Definition 2) that is if ( ). nj k l
k l n
For and congruent modulo we will write k l n k  l
(mod ) or n .
Note that in particular k  0(mod n) (in the new sense) iff n j (k 0)= k, so the new
notation is consistent with the notation introduced in Definition 2.

Example. 10 26 (mod 4) because 4 j (26 10)=16.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

9. Congruences 19

The above definition is in fact a definition of a relation n in Z. Although  n is

not an ordinary equality, it shares with it many nice properties:
n2N, n is an equivalence relation
8 8 8
Theorem 3. (On the relation ≡n) For every
in Z that is
1
k 2Z
(k n k); 2
k;l 2Z
(k n l ,l n k); 3
k;l;m 2Z
(k n l ^l n m) )(k n m):
Even more importantly, this equivalence relation is compatible with the usual oper-

8
ations in Z:
Theorem 4. (Arithmetic properties of congruences) Let N. Then n2

8
1.
a;b;c;d 2Z
(an b^cn d))(a+cnb+d) (sidewise addition of congruences)

2.
a;b;c;d 2Z
(an b^cn d))(a
cn b
d) (sidewise multiplication of congruences)


Example. 10 26 (mod 4) and 1  11 (mod 4) so 9 = 10 1  26 + 11 = 37. Also



10 ( 1) 4 26 11.
4

remainder on division by n. In particular,

k;l 2Z
8
Note also that for any integer k it is kn (kmod n) so k is congruent modulo n to its
k +l n (k +n l) and k;l2Z k
l n (k
n l)
n
(cf. Definition 3). One way to think about congruences is that we allow ourselves to go
8
n

out of the ring Zn and calculate more „freely” with integers at the cost of not having
strict equalities (which we had in Zn) but only relations ( n in Z). But note that at 
the end of such calculations we can always produce a result that lies in Zn (by the
distinguished formulas above) and this, in fact, will be the correct result in this ring (if
the arguments to the calculations also came from Zn).
Example. In Z15 we have
(10 +15 ( 3))
15 13 =(10 +15 12)
15 13 =7
15 13 =1.
On the other hand, we can perform the ordinary addition and multiplication and only
reduce the final result to its remainder:
(10 +( 3))
13 7
13 91 1(mod 15).
As we can see, the result is the same.
Illustrative
as it is, the above example is somewhat misleading because the real
power of calculating with congruences comes from the exact opposite application of
Theorem 4: namely, one can always reduce any term of the expression to compute to
its remainder and still have a valid congruence.
Example. Let’s say we want to compute the remainder (134 ( 21)+16)(mod 6). We

 
know that 16 4(mod 6), 134 2(mod 6), 21 3(mod 6). Hence, by Theorem 4 item 2 



we have 134 ( 21) 6 2 3 and then by item 1 — 134 ( 21)+16 6 2 3+4. Now it is



 
easy to finish: 2 3+4 10 4(mod 6). And this is the answer to our problem.
If you think of what has just happened, you may feel a little amazed because in
order to find the result we didn’t need to compute the product 134 ( 21) at all!

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

20 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Actually, such calculations can be performed in a much more flexible way than done
above (again, this follows from Theorem 4). For instance, we can also do something like


this: 134 ( 21)+16 2 ( 21)+34
~

~

42 +34  
8 4(mod 6), where the decorated
numbers are (respectively) congruent modulo 6.

At the level of congruences one can study „equations” similar to those considered
in Zn, too:
a +xn b and a
xn b.
The first congruence is easy to solve. For given a;b 2Z all the solutions of a +xn b
are the integers x 2fb a +kn: k 2Zg. Of course, among such numbers there is a solu-
tion equal to (b a)(mod n) 2Zn (for k =
 b a  where b
c denotes the floor function).
n
If, moreover, a;b 2Zn then solving a +xn b in integers amounts to solving a +n x=b in
Zn and then using the (unique!) solution x =b n a (see page 8 for the definition of n)
to produce all the integer solutions f(b n a)+kn: k 2 Zg to the congruence a +x n b.
These observations indicate that there is no essential difference between the ability to
solve a +n x = b and a + x  b (mod n) but the latter is „more general” than the former
in that that we allow here a;b to be arbitrary integers (not just the elements of Zn).
Similarly, we will be able to solve the equation a
n x =b in Zn once we can solve the
congruence a
x n b in integers. The tool that is needed to solve such congruences will
be developed in the next section.

10 GCD
The basic definitions that we now give should be more or less familiar to you:
k ;:::;k 2 d is called the greatest
8
Definition 12. (GCD) Let 1 r Z. A natural number
common divisor (gcd) of the numbers 1 r if k ;:::;k
1.
1
d j kj
6 j 6r
2. if  2 Z is such that
6 j 6r
8
 j kj then  j d.
1

The above number d is denoted by gcd (k ;:::;kr) or – if no confusion is likely –

simply by (k ;:::;kr).
1

Definition 13. (Coprime numbers) Two integers k;l are called coprime if (k;l)=
1. Coprime numbers are sometimes denoted by k ?l.
The next theorem should not be a surprise to you:
Theorem 5. (On GCD) For any 1 r k ; :::; k 2 Z not all equal to zero their gcd
always exists and is uniquely determined.
In principle, Theorem 5 is a consequence of the following method of finding gcd:
k k
find the sets D ( j ) of all the positive divisors of the numbers j , compute 1 6 j 6 r D ( j )
T k
k
and take the maximum of this (finite! if not all j are 0) set. This number will be the
k ;:::;k
gcd ( 1 r).

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

10. GCD 21

Examples.
! For any k 2Z we have gcd (k)=jkj because jkj is the greatest divisor of k.
! (4; 6)=2 because D(4)=f1; 2; 4g, D(6)=f1; 2; 3; 6g so that max (D(4) \D(6))=
max (f1; 2g)=2.

The method for computing gcd indicated above is not very practical, because it
involves factorization of integers (to find the divisors) and the problem of factorizing
integers is widely considered to be quite difficult computationally (and supposedly infea-
sible for large numbers). The popular public-key cryptosystem RSA is based on the
problem of factorization and so-called Euler’s theorem (see Section 13). Fortunately,
there is another, very old, method to compute gcd without factoring integers:
Theorem 6. (Euclidean algorithm) The gcd of two numbers Z, of which k;l 2
at least one is different from zero, can be computed in the following way:
1. Put r :=max (jkj; jlj), r :=min (jkj; jlj).
0 1

2. If r ;:::;ri are already defined for some number i >1 and ri =

0 / 0 then put
ri :=ri (mod ri).
+1 1

With such definitions, there exists a >1 such that ra =0 (so the above process
ends). Moreover, then ra =gcd (k;l).
1

Commentary. The sequence (r ;:::;ra) in the above theorem is defined using mathe-
0

matical induction. This, in turn, can be implemented recursively e.g. as follows (using
Maple language):

GCD:=proc(k,l); # the hash mark "#" is a comment sign

if k<0 or l<0 then return GCD(abs(k),abs(l)) fi;
if l<>0 then return GCD(l,k mod l) fi; # "<>" means " /
="
if l=0 and k<>0 then return k fi;
ERROR(‘At least one of the numbers has to be different from 0‘)
end proc;

; r r r r
Example. gcd ( 224 128)=? We have 0 =224, 1 =128, 2 = 0 (mod 1)=224 (mod128)= r
r r r r r r
96, 3 = 1 (mod 2)=128 (mod 96)=32, 4 = 2 (mod 3)=96 (mod 32)=0. By Theorem 6,
; r
( 224 128)= 3 =32
The above calculations can be represented in a both more compact and more detailed
way:
ri ri qi +1

224 128 1
128 96 1.
96 32
0 3
j ri k
32

q
Here i = r
i +1
. This representation will be useful in what follows.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

22 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

The Euclidean algorithm is a much more effective way of computation of gcd than
the naïve method based on factorization of numbers indicated above. Specifically, one
can show that the number of steps required to perform in order to compute gcd ( ) k;l
for two integers k;l
such that l 6k l
is O(log( )) (read: „...is big-O of log ”; this notation l
means that the number of steps is bounded by log for some positive constant C l R). C2
From this it also follows that the running time of Euclidean algorithm is O(len len ), k l
where len denotes the binary length (that is the number of bits) of an integer. It is
worth noting that the time needed to compute the product is also O(len len ) sokl k l
finding gcd is essentially as fast as multiplying integers.

Exercise 4. Show that the binary length len k of an integer k is equal to len k = b1log
,
2 jkjc, if k =
/ 0
if k = 0
.

Theorem 6 gives us a method of finding the gcd of two integers without knowing
their factorizations. And what about the case of several numbers? We have:
Theorem 7. (GCD of several integers) Let 1 k ;:::;k 2
r Z be integers not all equal
to 0. Then ( 1 k ;:::;k
r ) does not depend on the order of the arguments 1 r. k ; :::; k
More precisely, ( 1 k ;:::;kr) depends only on the set 1 r . If fk ;:::;k g
2 and also r>
k ;:::;k
1 r 1 are not all equal to 0 then
(k ;:::;kr)=((k ;:::;kr );kr).
1 1 1

Remark. Note that the properties of gcd given in Theorem 7 resemble the properties of
binary operations in groups (commutativity and associativity) but, generally speaking,
n n>
gcd is an -ary operation on integers ( 1) and such terminology is not used in this
n k ;k k ;k
case. However, for =2 we have ( 1 2)=( 2 1) and ( 1 ( 2 3))=(( 2 3) 1)=( 2 k ; k ;k k ;k ;k k ;
k ;k 1)=( 1 k ;k ;k k ;k ;k
3)=(( 1 2) 3) so one can say that the binary gcd, gcd2: Z
 Z Z,  !
;
3 2

is commutative and associative. Question: is (Z gcd2 ) a group?

Example. Using Theorem 7 and the example on page 21 we compute:

(128; 224 ; 40 ; 224)=( 224 128 ; ; 40)=(( 224 128) ; ; 40)=(32 ; 40)=8
(note that in the first equality we used the fact that 128 f ; 224 ; 40 ; 224 g =f 224 ;
;
128 40 ). g
Commentary. The Maple code of Commentary on page 21 can be modified to a func-
>
tion gcd accepting an arbitrary number ( 1) of arguments. A simple (although not very
elegant) such modification is the following:

GCD:=proc() local A,k,l;

if nargs=0 then ERROR(‘You must specify at least one argument‘) fi;
#"nargs" is the number of arguments actually passed to the
procedure
if nargs=1 then return GCD(abs(args[1]),0) fi;#"args[i]" is the i-
th argument passed
if nargs>=3 then
A:={args} minus {0};#we remove 0 from the set of arguments
passed
if A={} then ERROR(‘At least one of the numbers has to be
different from 0‘) fi; #A has to be a non-empty set

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

11. Solving a
xn b and a
n x=b 23

return GCD(GCD(op(1..-2,A)),A[-1]); #"op(1..-2,A)" is the (comma

separeted) sequence of all the elements of the set A except for the
last one; A[-1] is the last element
fi;
#now nargs=2 and we proceed as before:
k:=args[1]; l:=args[2];
if k<0 or l<0 then return GCD(abs(k),abs(l)) fi;
if l<>0 then return GCD(l,k mod l) fi;
if l=0 and k<>0 then return k fi;
ERROR(‘At least one of the numbers has to be different from 0‘)
end proc;
Exercise 5. Implement and test the above procedure in Maple. Example invocation: GCD(8,0,
14).

11 Solving a · x ≡n b and a ·n x = b
What is the connection between the gcd and the equation a
xn b? The following
theorem provides a characterization of gcd which turns out to be the link that we search
for.
a x ::: a x b
Theorem 8. (Bezout’s identity) The equation 1 1 + + r r = , where 1 a ;:::;
a2r Z are not all equal to 0 and b2 a ;:::;a j b
Z, has a solution in integers iff ( 1 r) .
r ; 2 a x a x b 
If =2 and ( 1 2) Z is a solution of 1 1 + 2 2 = then all solutions of this
2

equation are exactly of the form (x ;x )= 1 +k a ; a ; k a ; a , where k 2Z

2
a a
1
( 1
2
2)
2
( 1
1
2)
is an arbitrary integer.
Remark. In Number Theory equations that are to be solved in integers are called

9
Diophantine equations.

How does the above theorem help to deal with the congruence axn b? Well, recall
first what such congruence actually means: ax n b ,(n j (ax b)) , ax+ny =b.
y 2Z
Hence, in order to solve axn b it is enough to solve ax+ny =b in Z , and by Theorem 2

8 we know when this is possible – exactly when (a;n) j b. Before actually showing how to
solve the latter equation, let us finally answer the question touched upon in Property 3.
Corollary 1.
1. The congruence axnb, where a;b2Z, n2N, has a solution in Z iff (a;n)jb.
In particular,
2. The congruence ax
n 1, where Z, a2 n2
N, has a solution in Z iff (a;n)=1,
a
or in words: iff the numbers and are coprime.n
3. An element a 2Zn has a multiplicative inverse in (Zn; +n;
n) iff (a;n)=1.
Commentary. Note that if for some a 2 Zn it is (a;n) > 1 then a; n 2 Zn nf0g and
n
a
n a;nn n a;an
nn 0 which means that a is a zero-divisor in Zn. In another words, an
( )

element a 2Zn is
n-invertible iff it is a non-zero-divisor (by item 3 of the above corollary
( ) ( )

and Property 3).

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

24 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Using Corollary 1 we can characterize those Zn that bear a field structure. For this,
we recall the following definition:

Definition 14. (Primes) A natural number is called prime if it has exactly n

two positive divisors. The set of all prime numbers will be denoted by P. Hence,
f ; ; ; ; ; ;:::g
P = 2 3 5 7 11 13 . A natural number greater than 1 which is not prime is
called a composite number.

Now we can state:

Corollary 2. (Zn ; +n;
n) is a field iff n is a prime number.

The above corollary validates our empirical discovery that Z2, Z3 are fields (see examples
on page 17). Now we know that also Z5, Z7, Z11,... are fields and that for a composite
n
number , Zn is not a field.
Let us indicate a method of solving the equation + = in integers. We will ax by c
do this by example.

Example. (Extended Euclidean Algorithm)

x y
Consider the equation 224 +128 =64. By the example on page 21 we know
; j
that ( 224 128)=32 and 32 64. Hence, Theorem 8 asserts that our equation does have
some solutions in Z2. Let us recall the table from the mentioned example:

ri ri qi +1

224 128 1
1,
!

128 96
96 32
0 3
jr k
32

q
where i = r i is the partial quotient on division of i by i +1. Using this relation
i +1
r r
and recalling the Division with Remainder Theorem (Theorem 1), we see that 128 =


1 96 +32 (look at the second and third rows from the bottom) which can be rewritten


as 32 =128 1 96. Similarly, looking at the third and fourth rows from the bottom we


get 96 =224 1 128. Substituting the latter relation into the former gives

32 =128 1
96=128 1
(224 1
128)=128 224 +128 =( 1)
224+2
128: (3)

u0 v0
Note that we have reached the top of the table and thus we have expressed 32 =(224 ;
128) in terms of the numbers 224 and 128. Specifically, (3) means that ( 0 0):=( 1 2) u ;v ;
is one of the possible solutions to the auxiliary equation 224 +128 =32. Multiplying u v
equality (3) sidewise by 32 =2 we get 64 =( 2) 224 +4 128 which can be written as
64





: x ;y
224 2+128 4=64 This means that ( 0 0)=(2 4) is one of the integer solutions to ;
x y
the equation 224 + 128 = 64 that we wanted to solve. Now we can use Theorem
 
8 to conclude that all the integer solutions of this equation are exactly of the form
2+k (
128
;
224 128 )
;4 k (
224
;
224 128)
=(2+k
4; 4+k
7), where k2Z is an arbitrary integer.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

11. Solving a
xn b and a
n x=b 25

Commentary. The procedure of solving equations ax by c

+ = in integers outlined in
the above example can be improved in such a way that apart from the sequence ( i) of r
the successive remainders, one computes also two integer sequences ( i) and ( i) such s t
that as bt r i
i + i = i, for all . Hence, upon reaching n =( ) one automatically gets r
a; b
s ;t
the integer solution ( n n) to the equation ax by a;b
+ =( ) without the need to trace
r q
back through the values of ( i) and ( i) to produce the solution (as we did in the above
example). This improved version of the procedure is what is usually called the Extended
Euclidean Algorithm. One can show that its running time is O(len len ), so (again) a
b
this algorithm is essentially as fast as the gcd algorithm itself, or simply as finding
the product a
b
. Our method is less effective, but it is conceptually simpler, easier to
remember and is what actually lies at the core of the improved version of the algorithm.

Now we can finally show how to solve the congruences a x n b and the related
equations a
n x =b.

Example. (Solving a x ≡n b and a ·n x = b)

I. Consider the congruence 224 x

128 64. By the remarks on page 23 preceding
Corollary 1 we know that the solutions to this congruence are just the values
x x
of as a solution of the equation 224 + 128 = 64, considered in the above y
example. Hence, every x 2f
k k2 g
2+4 : Z is a solution to 224 128 64 (and x
there are no other integer solutions to this equation).

Using the fact that 224 128 32 we can transform the congruence 224 x
x
x
128
64 into an equivalent one: 32 64, which gives rise to the equation 32 128 =
f
k k 2 g\
128
64 in Z128. Its solutions are exactly all the elements of the set 2+4 : Z
Z128 that isx 2f ; ; ;:::; g
2 6 10 126 .
II. Consider the equation 37 x =1 in Z . Since (37; 44)=1, by Corollary 1 item 3
44
we know that it is possible to solve this equation in Z . In order to do that, we
consider the auxiliary equation 37 x +44 y =(37; 44)=1 in Z. We have
44

ri ri qi +1

44 37 1
37 7 5.
!

7 2 3
2 1 2
1 0
Working from the bottom upwards, we get

1=7 3
2=7 3
(37 5
7)= 3
37 +16
7= 3
37 +16
(44 1
37)=

16
44 +( 19)
37.
y0 x0

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

26 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Hence, one of the possible solutions to the equation 37 + 44 = 1 is ( 0 x y x;

y ;  k
k2
0) := ( 19 16). By Theorem 8, all the integer solutions of this equation are
exactly the elements of the set 19 + 1 16
44 37
: Z = ( 19 +44 k ; f k;
16 37 ):k k2 g 1

Z . This means that the solutions to the congruence 37 44 1 x

x
are the numbers = 19 +44 , where k k2
Z, and the solutions to the equation
x
37 =1 in Z44 are the numbers 19 +44 : f k k 2 g\
Z Z44 = 25 (so there is only f g
one solution to this equation!). Check that indeed 37 44 25 =1.

x
III. Consider the equation 2 =3 in Z256. Since (2 256)=2 and 2 3, Corollary 1 item ; -
1 asserts that the congruence 2 x
256 3 does not have any integer solutions.
x
This means that also the equation 2 =3 does not have any integer solutions in
Z256.

We can sum up the above considerations by giving the following schematized pro-
cedure of dealing with the various problems to solve:

Congruence: Modular equation:

To solve: axn b a
n x=b
Restrictions: a;b 2Z;n2N a;b 2Zn;n2N

& .
Solutions exist iff: (a;n) j b (a;n) j b
Solution domain: x 2Z x 2Zn
Auxiliary:

#
Auxiliary equation: ax+ny =b
Solution domain: x;y 2Z

#
Extended Euclid to
A solution to aux.: (x ;y ) 2Z 0 0
2
ax+ny=(a;n)
Solution set for the (x;y) 2Sol ,
x=x +k a;nn and
.o &n
auxiliary equation 0

Z ): y=y k a;na ,k 2Z
( )

2
(Sol 0
( )

n o
Solution: x +k
0
(
n
a; n )
: k 2Z x +k a;nn :k2Z \Zn
0
( )

Problem 1. Try to solve the equation 2 x + 3 y 4 z = 2 in integers.

Hint: First solve the equation 2 x +3 y = 1.

12 The group Gn and the ϕ function

In Example II on page 25 we found that the equation 37 44 x=1 has only one solution
in Z44, namely x =25. This is not accidental, as we shall note shortly. First, recall that
for a prime number p, (Zp; +p;
p) is a field with exactly p elements (Corollary 2). But
we also know that even for composite number there are numbers in Zn which are n


invertible with respect to n (Corollary 1 item 3). Hence, it is natural to consider the
set of the invertible elements of Zn:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

12. The group Gn and the ' function 27

Notation. For n 2N, n>2, we put Gn :=fk 2Zn:(k;n)=1g.

The basic theorem on Gn is the following:
Theorem 9. (The structure of G ) For every n 2 N, n > 2, (Gn;
n) is a group.
This group is called the group of multiplicative inverses modulo n.
n

This theorem explains that the solution x = 25 to the equation 37 x =1 is just the
inverse element 37 in the group Gn. By Exercise 3 we know that an inverse element
44
1

in a group is always unique; that is why x = 25 is the only solution to this equation.
More generally, by Property 1 item 3 every equation an x = b has a unique solution if
a;b 2Gn, that is if (a;n)=(b;n)=1. Actually, the condition (b;n)=1 is unnecessary
for the uniqueness of the solutions; (a;n)=1 is enough. This is a simple generalization
of Exercise 3 and Property 1 item 3 (you will see this in practice on the classes).

How many elements do the groups Gn have?

p
Example. If is a prime number then p = 1 2 G f ; ;:::;p g
1 . Hence, card p = G p 1 („card”
is just the number of elements in case of a finite set).

We pose the definition of the counting function for the groups Gn:
Definition 15. (Euler totient function) The Euler totient (or ) function is '
defined on the set of natural numbers as ( ):= card
1,
'n
Gn, if n > 1 . Hence, : N N.
if n = 1
' !
'p p p2
By the above example, ( )= 1 if P. Is there a closed-form formula for
ϕ in general? The answer is „none is known”, but there is a method of computation
'
of the values of which, in principle, is as fast (or rather: as slow) as factorizing integers
(see Theorem 12). Below we provide a picture of the graph of the function in the set '
f ;:::; g
1 10000 which shows why a direct formula for is unlikely. '

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

28 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

To explain how to compute the values of the ' function, we introduce the following:
Definition 16. (Multiplicative function) We say that a function : N f ! C is
f
multiplicative if (1)=1 and for every coprime k;l 2
N it is ( )= ( )f k
l f k
f(l).
There is a related notion of an additive function which satisfies g(0)=0 and g(k
l)=
g(k)+ g(l) for all naturals k ?l.
Exercise 6. Show that if f : N ! R is additive then N 3 x 7! 2f x 2 R is multiplicative.
( )

Multiplicative (additive) functions are very common in Number Theory. Here is

the first example of such a function.

Property 5. If k;l;n 2 Z and k ? l then (kl;n)=(k;n)
(l;n). In particular, the

;n 3x7!(x;n) 2N is multiplicative.
function ( ): N

Another example of a multiplicative function you might already guess:

Theorem 10. (On the totient function) The Euler function ' is multiplicative.
How does the above theorem help with calculating '(n)? In order to understand
this, we recall the following fact which should be more or less familiar to you.

Theorem 11. (Fundamental theorem of arithmetic) Every natural number n>1

can be expressed in the form
n= p
:::
pr r,
1
1
(5)
where r > p ;:::;p 2
1, 1 r P are pairwise different prime numbers and 1 r N. ;:::; 2
Moreover, representation (5) is unique up to the order of the factors 1 r. p ; :::; p
In particular, if we assume that 1 p <:::<p
r then (5) is unique and is called the
canonical representation of the number . n
(The phrase „pairwise different” is to be understood as „all of them different from each
other”.)

Example. 4356000 =25 32 53 112. This is the canonical representation o 4356000.

Using Theorem 11 we may recast the definition of being coprime as follows:

>
Property 6. Two natural numbers 2 are coprime iff the primes appearing in
their canonical representations are all different. In particular, powers of different
prime numbers are always coprime.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

12. The group Gn and the ' function 29

Example. By the above property we have e.g. 25 32 53 112, ? 3?2 5 11 , 13 ?2 3 5 11 .

5 3 2 5 2 3 2

Similarly, Theorem 10 justifies the following calculations:

'(4356000)= '(2 3 5 11 )= '(2 ) '(3 ) '(5 ) '(11 ).

5 2 3 2 5 2 3 2

It should be clear to you that the above calculations are not accidental. Namely we have:

f
Corollary 3. If is a multiplicative function and = 1 1 r
r is a decomposition n p
:::
p
n
of a natural number into pairwise different prime factors then

f(n)= f(p )
:::
f(pr r).1

1

Once we have Corollary 3, the only missing information to be able to compute (at
least in principle) the values of the ' function is how to compute '(p ), where p 2 P
and 2N. Right after stating Definition 15 we noticed that '(p )=p 1 and the reason 1

for that is just the fact that all the element of the set Zp nf0g are coprime to p. This in
turn is a consequence of Property 6: clearly in the canonical representation of a natural
n p
number less than a given prime there is no this prime , so these numbers and p n
p are coprime. Similarly, in order to compute ( ) for a prime and N, we must 'p p 2
count the number of numbers from the set Zp that are coprime to . But by Property p
6 again, this reduces to counting those numbers from Zp that do not contain in p
their canonical representations or, what amounts to the same thing, those that are not
p
divisible by the prime . Now, it is easy to see that all the numbers of the set Zp that
are divisible by p are those of the form 0 2 ( 1 1) , so there are exactly ;p; p;:::; p p
p 1
such numbers. All the other elements of the set Zp are not divisible by , hence p
p
they are coprime to , hence they belong to p , hence there are exactly 1
such G p p
numbers. We can sum up these observations:

Corollary 4. If p 2P and 2N then Gp =Zp nfk
p:k2Zp g and '(p )=p p 1

1
.

Combining Corollaries 3 and 4 we finally get:

Theorem 12. (A formula for ϕ) Let 2 be a natural number and let = n> n
p
:::
p
1
1
r
r be a decomposition of n
into pairwise different prime factors. Then

'(n)=(p 1
1
p )
:::
(pr r pr r )=n
p p
:::
prpr :
1
1 1 1 1
1
1 1

Example.

1. We have '(4356000) = '(2 3 5 11 ) = 4356000



= 4356000
=

5 2 3 2 1

2
2

3
4

5
10
11 33
8

2 3 5 11 3 5 11 =1056000.

11 =2
3
5 2 3 2 2 8 1 3 1
3

We have 10000 =2
5 so '(10000)=10000

=4000 (cf. figure (4)).

4 4 1 4
2. 2 5

3. We have 8687 =7 17 73 so

'(8687)=7
17
73


=6
16
72 =6912. 6

7
16
17
72
73

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

30 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

'n
Commentary. The formula for ( ) given in Theorem 12 depends heavily on the
n
possibility of factorization of the number into its prime factors. Up to now, there is no
known algorithm that can do this efficiently. The best proven complexity bound is for
so-called quadratic sieve algorithm and is O(eCn
(ln n
lnln n) ), where n tends to 1
1/2
C
with n!1 . This is really slow. Since most of modern cryptographic methods depend
in essential way on the practical infeasibility of factoring numbers, there was a contest
called RSA Factoring Challenge, active from 1991 to 2007, in which the RSA
Laboratories founded money prizes for factoring large numbers. This acted as a
method of verifying what key lengths should be considered as being safe given current
state of knowledge of factorizing algorithms and available computing power. Before the
project was canceled, the largest challenge that had been solved was RSA-640, i.e. the
number to be factored consisted of 640 bits. It was done in 2005 and it was awarded
with $ 20 000. After 2007 some bigger challenges were also factored (for free), the biggest
one being RSA-704 (a number having 212 decimal digits). For the remaining challenges
see http://en.wikipedia.org/wiki/RSA_Factoring_Challenge. It is interesting to note
that there is a quantum computer factoring algorithm by P. Shor which works in
polynomial time i.e. fast enough to compromise all cryptographic systems based on
the problem of factorization. However, it is uncertain if powerful enough quantum
computers will soon be built, so this algorithm provides no real danger for world’s safety
;-) in the near future. Still, there is the possibility that an efficient real-world-computer
factoring algorithm might exist. Finding such an algorithm means fame.

13 Fermat’s little theorem and its generalizations

As you have probably already noticed, calculations involving congruences are much
simpler to perform than the „usual ones”, especially when we are interested in a remainder
of some (possibly quite complex) expression modulo an integer which itself is not too
big. For instance, it turns out that raising an integer to a (large) power in Zn can
be realized rapidly by so-called repeated-squaring algorithm (see [Sho08, p. 65]).
Moreover, there are some special exponents for which the computation of the power
is trivial. To describe such a situation, we first note the following, somewhat unexpected:

Property 7. If p is a prime number, then for every a;b 2Z it holds

(a +b)p ap +bp (mod p). (6)

In particular, if a;b 2 Zp then

(a +b)p =ap +p bp in Zp
(in the ring Zp the symbol xp means x
p :::
p x).
||||||{z}}}}}}
p factors

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

13. Fermat’s little theorem and its generalizations 31

The reason behind the above formulas is quite simple. As you may already know (at

a b P
least in the special cases of second and third powers) there is something called Binomial
theorem: ( + )n = i =0 ni
n   i n i, where  n := n! is the binomial coefficient.
ab i! (n i)!
 n  (n i + 1)
:::
i(n 1)
n
Now, for / 0 i 2f ;ngthe integer i = 1
2
:::
i
has its numerator divisible by n
n
and the factors in its denominator are less than . This means that if is a prime, the n
n
factor in the numerator does not cancel  out
 with any of the factors in then denominator
  P
(in fact is co-prime to them) and hence ni 
0(mod ). But this gives i=0 ni i n i n ab
an +bn (mod n) if n is a prime number, so (6) holds.
Examples.
1. We have (a +b) =a +2 ab +b  a +b for any a;b 2Z.
2 2 2
2
2 2

2. More specifically, on one hand (10 6) = 4 = 64 and on the other — 10 + 3 3 3

( 6) =1000 216 =784. Clearly, 64  1  784.

3
3 3

The above observation can be exploited even more. Fix a prime number p. Obvi-
ously, we have 0p p 0, 1p p 1 but thanks to Property 7 we also have 2p =(1+1)p p 1p +
1p =1+1=2, hence 3p =(2+1)p p 2p +1p p 2+1=3 and „so on”. This „so on” means
that we notice a rule which allows as to use symbols instead of specific numbers and
essentially repeat the above calculations, but in a more abstract way. Namely, let’s say
we know that n p ≡p n for some number n2
N0. Then we also have
(n+1)p p np +1p p n+1,
by (6)

where the second congruence follows from the bolded assumption. Thus, we have found
nn) n  n
that ( p p ) (( +1)p p ( +1)) for any n2
N0. This means we justified the fol-
lowing chain of implications:
(0p p 0) )(1p p 1) )::: )(np p n) )((n+1)p p (n+1)) ):::
Since the very first antecedent in this chain is true, we may infer that all its consequents
are also true. In another words, we have used mathematical induction and we have
proved the essential part of the following:
Theorem 13. (Fermat’s little theorem) Let p be a prime number.
1. If k 2Z then kp k (mod p).
2. If k ? p then kp 1(mod p).
1

3. If k 2 Zp then kp =k in Zp.
4. If k 2 Gp then kp =1 in Gp.1

Items 2 and 4 of the above theorem are direct consequences of Corollary 1 items 1 and
3, respectively: e.g. the congruence p k k
(mod ) can be multiplied sidewise by an p
element l2
Z such that k
l 
p 1 (which exists since ) and this gives the item 2. k ?p
Examples.
1. ( 234)28 29 1 since 29 is a prime and (234; 29)=1.
2. (12)17 =12 in Z17 since 17 is a prime.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

32 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Fermat’s theorem can be formulated in a somewhat more general form (to see this,
it is enough to use the „sidewise multiplication trick”).

Theorem 14. (Second version of Fermat’s little theorem) Let be a prime. If p

k2 Z and m;n2
N satisfy mn p
(mod ( 1)) then m n (mod ). In particular, k k p
k2
if Zp then m k k
n
= in Zp.

Example. Since 543  183  3, we have 234543 37 234 3

 123  12 33
 37 36
11


36 36 37 37
37 ( 1) 11 37 26.

What about moduli which are not prime? First note an example: 3  3 so item 2 3
4

of Theorem 13 does not hold for the non-prime modulus 4. This means that we need a
different exponent than just p 1 in general (if such an exponent exists). It turns out
that there is a more general way of finding such numbers. And this method comes from
group theory. Namely, we have:

G;

Theorem 15. (Lagrange theorem) If ( ) is a finite group with elements and n
H;

( ) is its subgroup (this means that as a set and H G
is a group with H


respect to the same operation restricted to ) then card card . H Hj G
Example. The set H:=f0; 2; 4; 6g is a subgroup of (Z ; + ) and card H=4j 8=card Z . 8 8 8

At this point, it may not be obvious how Lagrange theorem can help us find the
exponents that we search for. The missing ingredient is the following:

G;

Property 8. If ( ) is a finite group then for every the set := k: N a2G hai fa k 2 g
is its subgroup. Denote := card m. Then m hai
=1, where 1 is the identity of the a
G
group . Moreover, for every N such that l2, we have l =/ 1. l<m a
The group hai of Property 8 is said to be generated by a.
Warning. If a group ( G;
+) is in additive notation then = : hai fk
a k 2 Ng,
where k
a a||||||{z}
:::}}}}}a H
:= + + , e.g. the group of the previous example is equal to H =h2i
k addends
(check!).

Let us see how the above two facts provide a natural generalization of Fermat’s little
theorem. Fix n2 n>
N, k2
2, and let Zn be a number coprime to . This means that n
k 2G G
n (see page 27 for the definition of n). Since ( n n) is a group, by Lagrange G ;

theorem we have that card hkij G
card n. But we know that card n = ( ), where is G 'n '
the totient function. Using Property 8 we get (in the group n) G
'(n) '(n)
k' n =(k
( ) card hk i)ca r d hki =1c a rd hki =1.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

13. Fermat’s little theorem and its generalizations 33

Hence, we have proved the classical:

Theorem 16. (Euler’s theorem) Let n2N, n>2.

1. If k 2Gn then k' n =1 in Gn.
( )

2. If k 2 Z and k ?n then k' n 1(mod n).

( )

3. If k 2 Gn and a;b 2 N satisfy a b (mod '(n)) then ka =kb in Gn.

4. If k 2 Z, k ?n, and a;b 2 N satisfy a b (mod '(n)) then ka kb (mod n).

Example. 34567233  7 and since 7?10 we can use the fact that '(10)='(2)
'(5)
233

1(mod 4) and hence 7  7.

10
=1 4=4 to get 233 233
10

Exercise 7. In an interactive Maple session issue the following commands:

Experiment with different values of the parameters.

'n
Commentary. In Euler’s theorem, the exponent ( ) is a number which works for all
choices of elements k 2Gn but it does not have to be the smallest such exponent. For
instance, it is easy to check that for every k 2G f ; ; ; g
8= 1 3 5 7 k G
it holds 2 =1 in 8 while
' G
(8)=8 4=4. The least universal exponent for n is given by so-called Carmichael
n G
function ( ). For a specific element of n a much smaller exponent may suffice, e.g.
G
one always has 11 =1 in any n. This smallest exponent for an element k 2G n is called
k
its multiplicative order ordn . By Property 8, ordn =card k hki G
(in n). From Lagrange
theorem we know that always ordn kj ' n
( ). This does not help much, because it turns
k
out that finding ordn is in principle as hard as factoring integers (first we should find
'n( )).

Having prepared all the necessary tools, we may illustrate the theory with a prac-
tical application:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

34 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

The RSA (Rivest, Shamir, and Adleman) cryptographic system. This is an example of a
public key cryptosystem . To use it, Bob must generate a pair of keys – a public and a
private one. The public key is available in a secure repository (a public key server) and
it may be used by Alice to encrypt her message to Bob. After receiving the encrypted
message, Bob may use his private key to decrypt it, obtaining the original message.
Here is how Bob generates his keys. He should:
1. Generate two (large) random primes p and q, p=/q (this can be done efficiently).
2. Compute n:= p
q (the number len n is the key length ) and '(n)=(p 1)
(q 1).
3. Choose e 2 G' n (e does not have to be very big).
( )

4. Compute d :=e in the group G' n .

1

Then: the public key is the pair (n;e) and the private key is (n;d).
( )

In order to encrypt her message to Bob, Alice should:

1. Split her massagem into chunks mi of length less than n.
2. For each chunk mi (recast to an integer) compute ci :=mei in Zn.
Then: the sequence c =(c ;c ;:::) is the encrypted message.
1 2

In order to decrypt the message from Alice, Bob should:

c
m c
1. For each chunk i compute ~ i := di in Zn.
m m
2. Combine the chunks ~ i into one ~ (reversing Alice’s splitting method).
Then: 8i;m m m m
~ i = i and ~ = is the original Alice’s message.
Proof of correctness. To see the general idea of how the above method works, assume
m m ;n
that a chunk i is such that ( i )=1 i.e. im 2G m2
n since for sure i Zn. Then we have
m~i =(ci)d =(mei )d =mei
d (in Gn).
But e
d =1 in G' n so e
d ' n 1 and by Euler’s theorem item 3 we get mei
d = mi
in Gn. This means that m ~ i = mi and Bob decrypts correctly all the chunks of Alice’s
( ) ( )

message (the case of (mi;n) >1 must be treated in another way but still m~i =mi).
Since G' n is an abelian group, the roles played by the numbers d and e can be
( )

interchanged, which gives another application: Bob may publish a file (F) along with
so called hash of F but this hash is encrypted by Bob’s private key. Then, this new
piece of information may work as a Bob’s digital signature (D). Namely, anybody who
downloaded a file that was suppose to be the one published by Bob, may compute the
hash of this file and compare it against the value of the signature D „decrypted” using
Bob’s public key . If those two values do not match, this means the downloaded file is
either a fake and probably does not come from Bob or there was some net error during
the transmission.
A safety remark: you should see that in order to be able to „break the system”, it is
enough to find Bob’s private key, which in turn amounts to finding the number '(n) e2G
satisfyinge
d '(n) 1. But in order to do it, first of all you must compute the modulus
'n n
( ) somehow. And you know only (part of the public key). If you can factor into n
p q
the (secret) prime factors and then clearly you can compute ( ). Otherwise, how 'n
'n
to compute ( )?...

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

14. Chinese remainder theorem 35

14 Chinese remainder theorem

In the previous sections we have learned how to solve congruences of the type axb
(mod n) and how to apply the modular arithmetic to perform certain calculations
rapidly. However, up to now there may have seemed to be no connection with the usual
; ;

calculations in the ring (Z + ). In this section, we indicate such a connection, which
may be traced back to the Vth century.
Our goal is to solve the system of congruences
8
< x
a (mod n )
: x
ar (mod nr)
1 1

(7)

x
for , in the integers. Here 1 a ; :::; a 2
r Z are arbitrary. However, it turns out that in
general in order that the system (7) have solutions, we must impose some conditions
on the natural numbers 1 n ;:::;n
r, as proved by the following:

Example. Consider the system x mod 4)
2(
. One sees easily that all the solutions to the
x
k k2  ;  ;:::
mod 6)
1(

first congruence are the numbers of the form 2+4 , where Z, i.e. 2 6 while the
solutions to the second congruence are just the numbers 1+6 , Z, i.e. 11 5 l l2 :::; ; ;
; ;:::
1 7 In particular, the first series of numbers consists of even integers and the second
series – of odd integers. Hence, there is no common solution Z to this system. x2
What sort of assumptions should be imposed then on the numbers 1 r in order n ;:::;n
to guarantee the existence of some solutions
 to (7)? To find a possible such condition, let
us consider a two-congruence system xx   a (mod m) . This can be rewritten in an equiv-
b (mod n)
alent form as follows:
 x+k
m=a
x +l
n =b ;
where k;l 2
Z are some integers to be found. If this system has some solution x;k;l 2Z
then upon subtracting its two equations we get that and must satisfy k l
k
m+l
( n)=a b. (8)

a b
But now recall that and are arbitrary integers. This means that on the right-hand
side of this equation there can stand virtually any integer; in particular, it may happen
a b
that =1. Thanks to Bezout’s identity (Theorem 8) we know that the equation
k
m l
n
+ ( )=1 has a solution in integers iff ( m; n
)=1 that is iff and are coprime. m n
On the other hand, under this assumption, we have that = = x a k
m b l
n
if the
k l
integers and satisfy equation (8). This means that this value of satisfies also the x
system of congruences that we wished to solve. Moreover, it is not hard to notice that
all other solutions to this system are congruent to the given one modulo . Thus, we m
n
are able to give all the integer solutions to the system (7) in the case of two congruences.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

36 Algebra and Number Theory. Lecture Notes Szymon Brzostowski


Example. Consider the system x  mod . Equation (8) becomes
2( 3)

x  11 mod 13 k
3+l
( 13)= 9.

k ;l )=(10; 3) is a solution to this equation. By the above reasoning,
( )

We easily find that (

x


t = 28 +39
t, where t 2Z. The solution in Z is x=11.
0 0

=2 10 3+3 13 39

In principle, the above method is the idea behind a general algorithm of solving
the system (7). One thing we see at once: if this system (of r > 2 congruences) has a
x x
solution , then this is obviously a solution of any two congruences of this system,
too. This means that for any = i j
/ it should hold ( i j) =1, or in another words – n; n
the numbers 1 n ;:::;n
r should be pairwise coprime. It turns out that this condition is
enough in order that the system (7) have solutions:
Theorem 17. (Chinese remainder theorem) Let 1 r Z and 1 r N be a ;:::;a 2 n ;:::;n 2
natural numbers greater than 1. If 1 n ;:::;n
r are pairwise coprime then the system
8
< x
a (mod n )
: x
ar (mod nr)
1 1

x= a
ns +::: +ar
nsrr +t

(n
:::
nr),

has solutions in Z. These solutions are given by the formula
1
1 (9)
1
1

where t 2 Z and the sj 2 Z are any numbers satisfying sj
n r  1 (mod nj ),

n
:::
n 1
j
for j =1;:::;r. In particular, there exists exactly one solution x 2 Zn
:::
nr of this 0 1
system.

It is not hard to see why Theorem 17 is true. Namely, every number j j 1 nj r is a
s
n
:::
n
a n n
:::
n
congruent to j modulo j because of the relation verified by j . But since 1 n r nk 0
j
s 
for =k j a
s
 k j
/ , we get j j n1
n:::j
nr nk 0 for = x
/ . This means that defined by formula
(9) satisfies x ::: a ::: a n j ; :::; r
0+ +0+ j +0+ +0 j (mod j) for = 1 x , so this is a
x2
solution to our system of congruences. Now, let 0 Z be another solution of this
system. This implies that x x n
0 j ;:::;r
0(mod j) for every =1 . In another words,
8j 2f ;:::;rg;n j x x
1 j ( n ;:::;n
0 ). Since r are pairwise coprime, this means that also
n
:::
n j x x x x n
:::
n
1

(1 r) ( 0 0
) so that and differ by an integer multiple of 1 r, so that
there exists a unique solution of our system of congruences in Zn1
:::
nr and this solution
x n
:::
n
is equal to (mod 1 r).

Example. Consider the system

8
< x1(mod 5)
: xx0(3(mod
mod 9) .
2)
s
 s

We must solve the congruences 1 18 1(mod 5), 2 10 1(mod 9) and 3 45 1(mod 2) s

s s s s2
for 1, 2, 3 (in each case only one solution i Z is enough). Using the methods of Sec-
s s s
tion 11 we find e.g. 1 =2, 2 =1 and 3 =1. According to formula (9), all the solutions
x




to our system are of the form =1 2 18 +( 3) 1 10 +0+ 90 =6+ 90, where t
t

t2 Z. The unique solution in Z90 is thus equal to 6.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

14. Chinese remainder theorem 37

At the beginning of this section we mentioned that Chinese remainder theorem may
work as a connection between the modular arithmetic and the usual one. The main idea
behind such an application of Theorem 17 is the following. Suppose you want to com-
pute a value of some expression E involving big integers. It is a common situation that
you may predict some upper bound for the result. For our discussion, let us assume that
M
this bound is ; more precisely, assume that the result is an integer lying in the interval
[0; :::; M
]. You may choose some sequence 1 n ; :::; n
r of (small) coprime numbers such
that 1 n
:::
n >M
r , compute E j :=E (mod jn) for each 1 j 2f ;:::;rg
and then use Chinese
remainder theorem to recover the unique integer x2
Zn1
:::
nr satisfying the system of
congruences x
nj Ej . Since 1 n
:::
n >M
r , the only possibility is that =E. In another x
words, you may compute the value of E by performing most of the calculations modulo
n
the small numbers j (which is very fast) and only at the end should you produce the
x
final (possibly big) result =E working modulo 1 n
:::
n
r. While this may seem a lot of
work, in practice this approach (when applicable) is usually much more efficient then a
direct computation in Z, provided that the numbers involved are big enough. Moreover,
if you have a computer with a multi-core processor, you may split the calculations of
Ej among several threads which speed things up even more. Another advantage is the
memory usage – it may be much smaller for this method than for the direct one.
Let us see by example how the above method works (this example also shows that
for small numbers it is more efficient to use a direct computation):

Example. Let us say we want to compute the product = 13 63. Clearly, the result k

will not be bigger than 24+6 =210. We may choose e.g. 1 =4, 2 =5, 3 =7, 4 =9. We n n n n
n
:::
n >
have: 1 4 k k
210 and (mod 4)=3, (mod 5)=4, (mod 7)=0, (mod 9)=0. So k k
we must solve the system
8
>
< xx3( mod 4)
4(mod 5) .
> x 
: x0( mod 7)
0(mod 9)
Because of formula (9), in this case there are only two numbers that should be found:
s



1 5 7 9 s



1(mod 4) and 2 4 7 9 1(mod 5) or equivalently 1 ( 1) 1(mod 4) and s

s

2 2 s s
1(mod 5). This gives e.g. 1 =3 and 2 =3. Hence, =3 3 5 7 9+4 3 4 7 9+ x








t



t
t 2
4 5 7 9=5859 + 1260, Z. Since 5859 (mod 1260)=819, this is the value of . k
Commentary. The method of performing calculations with integers by first falling back
on modular arithmetic and then applying Chinese remainder theorem is widely used.
Some example applications of this method include so-called threshold secret sharing
(in cryptography) and also faster decryption in the RSA cryptosystem (typically about
three times faster). Also, it can be used to multiply big matrices or polynomials (with
integer coefficients).
There is another method of speeding up calculations, called rational reconstruc-
tion, which, loosely speaking, allows one to use modular arithmetic first and then re-
cover the result which can be a rational number (see [Sho08, Section 4.6]).

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

38 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

It is worth noting that the assumption that the numbers 1 n ;:::;nr are coprime (see
Theorem 17) is not in general necessary in order that the system (7) have solutions. It
may be proved that solutions exist iff 8i;j 2f ;:::;rg;a a
1 i n ;n
j (mod ( i j )). Moreover,
in such a case there is exactly one solution of the system in Z[n1;:::;nr], where [ 1 r] n ;:::;n
denotes the least common multiple of the numbers 1 n ;:::;n
r .

15 The prime numbers

The most important and difficult problems in Number Theory are connected
with prime numbers. They are also important from the point of view of applications
e.g. in cryptography. For instance, in order to generate the keys in the RSA crypto-
graphic system, you must be able to find (possibly very big) prime numbers. Thus, the
first natural question is if this is always possible. The answer to this problem was pro-
vided already by Euclid (c. 300 BC):
Theorem 18. (Euclid theorem) There are infinitely many prime numbers.

Proof. To the contrary, assume that there are only finitely many primes, e.g. 1 n. p ;:::;p
We may consider the number := 1 N p
:::
p
n +1. Clearly, N
1(mod j) for every = p j
;:::;n N
1 , which means that is not divisible by any prime. This is not possible (why?). 
While the above theorem is good news, it does not provide us with any direct way
of finding big prime numbers. A fascinating property of primes is that their distribution
among the naturals looks as a random one and nobody has found any direct formula
producing only prime numbers (not to mention a formula for, let’s say, -th prime k
number). So, a natural approach to generate big primes would be just to test subsequent
numbers starting from some big enough N
and hope that soon enough in the sequence
NN N
, +1, +2,... there appears a prime number.

Question 1. Is this a reasonable strategy?

Some bad news:

Fact.
There are arbitrary long intervals of natural numbers without prime numbers.

There are also good news:

Theorem 19. (Bertrand–Chebyshev theorem) For every integer n > 1 there
p
exists a prime number such that
n<p<2
n.
Example.

n 23 4 5 6 7 8 9 10 ::: 20
p 3 5 5; 7 7 7; 11 11; 13 11; 13 11; 13; 17 11; 13; 17; 19 ::: 23; 29; 31; 37
2
n 4 6 8 10 12 14 16 18 20 ::: 40

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

15. The prime numbers 39

Theorem 19 gives us some positive information, but it turns out one can do much
better. In order to state the next result, we introduce the following important definition:
Definition 17. (π function) Let x2
R+. Then ( ):=the number of primes less x
x 
than or equal to . The function is called the prime-counting function.
Example.
x 1 2 3 4 5 6 7 8 9 10 11 ::: 106
(x) 0 1 2 2 3 3 4 4 4 4 5 ::: 78498
.

A famous theorem about the asymptotic distribution of primes is the following:

Theorem 20. (Prime Number Theorem)

lim
(xx) =1.
x!1 ln x
x x
This theorem says that for big there are „roughly” ln x prime numbers less than . The x
assertion of the theorem can be written in a somewhat more suggestive way as follows:
(x)= lnxx
(1+o(1)) as x!1,
where the small-o notation o(1) is just a way of saying that the values hidden by the
symbol o(1) tend to 0 (in this case as x!1).
A simple corollary of Theorem 20 is the following improvement of the
Bertrand–Chebyshev theorem:
Corollary 5. For every (small) real ">
0 there exist N 2N such that for all x>N
there is a prime number in the interval ( (1+ ) ). x; "
x
This corollary does not say anything about the value of the number but there are also N
some specific results in this direction. For instance, there is always a prime between x
1
x x>
and (1 + 25
ln(2 x) ) if 396 738. These kind of results show that probably it
should not take „too long” to find a prime number starting from some value of and x
following the strategy described on page 38. So the answer to Question 1 is yes. There
are also much more „optimistic” predictions concerning the distribution of primes in
some specific intervals and these predictions have some heavy empirical evidence. One
such conjecture is Legendre’s conjecture, which states that there is a prime number
n n
between 2 and ( +1)2 for every n2 N. This conjecture is still unsolved . Of the same
p
status is Cramér’s conjecture which states that if is a prime number then in the
p;p O p
interval ( + ((ln )2)) there is also another prime.
Sometimes it is also important to be able to generate big prime numbers of a special
form. For instance in the RSA system, some additional restrictions may be imposed on
p q
the prime numbers and (see page 34). This is connected with the notion of a strong
prime, which in turn is a contra-answer to existing factorizing algorithms working faster
than usually in some special situations. An example of such an algorithm is Pollard’s
p 1 algorithm. In order for this method to be useless to factor = , one should n p
q
p
assure that the prime number is of the form = p k
r
+1, where the number is also r
q
a big prime (and similarly for the prime number ). Thus, the question is: do primes
of such a form exist and how many of them is there? The answer to this question
may be viewed as a generalization of Theorem 20:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

40 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Theorem 21. (Dirichlet’s theorem) If two positive integers and are coprime k l
then there are infinitely many prime numbers in the sequence ( + +2 ) k;k l;k
l;:::
that is there are infinitely many prime number solutions to the congruence l . x k
 x
More precisely, if k;l( ):=the number of these primes less than or equal to that x
k
are congruent to modulo then l
k;lx(x) = 1
x!1
lim
x '(l)
ln
or equivalently
k;l(x)= ' l
xx
(1+o(1)) as x!1.
1

( ) ln

Note that for k =1 and l =1 it holds k;l(x)=(x) and '(1)=1 so Dirichlet’s theorem
is indeed a generalization of Theorem 20. Moreover, this theorem guarantees that if you
take a (big) prime number r and consider the sequence (1; 1+ r; 1+2 r;:::), for sure
therein you will find a prime p =k
r +1 for some k 2 N. If you generate only this sort
of primes p and q for the RSA algorithm, you are safe from the p 1 attack.
Example. In the sequence f8
n+1: n 2Ng there has to be infinitely many primes (by
Dirichlet’s theorem). The first few primes in this set are:
; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;:::
17 41 73 89 97 113 137 193 233 241 257 281 313 337 353 401 409 433 449 457 521
In particular,  ; (521)=21. On the other hand, ' l
x evaluated at l =8 and x =521
x 1

gives the value 20.820844:::; so in this case the prediction of Theorem 21 is almost exact.
1 8
( ) ln

As you can see, the distribution of prime numbers, although chaotic, is also subject
to some restrictions and there are many observations concerning the counting function
. Perhaps the most famous of all unsolved problems in mathematics is the Riemann
Hypothesis and this problem can also be stated in terms of the function . 
Millennium Problem (Riemann Hypothesis 1859). Prove that
(x)=Li(x)+O(px
ln x),
where the Eulerian logarithmic integral Li is given by the formula Li( x):=R x t dt.
2
1

ln
The Riemann Hypothesis postulates that you may estimate the number of primes
6x by the number Lip(x) (which can be easily computed) and by doing so you make a
mistake which is O( x
ln x), so a relatively small mistake. This hypothesis turns out
to be extremely important in mathematics as it implies many other unsolved problems
in Number Theory. That is why it has been chosen as one of Millennium Problems
and as such is worth $ 1000 000. The price is offered by Clay Institute (see http://
www.claymath.org/millennium-problems/millennium-prize-problems).
Although we answered Question 1 in the affirmative, one more information seems
to be crucial in order to be able to generate big primes. Namely, since there are no
formulas for prime numbers, how to check if the number under consideration is a prime
or not? Of course, for a given N2 pN
N you could employ the naïve method of successive
divisions ofN by naturals less than (or N
) but this approach is totally useless for
N
big . Notice also that this method would produce a (partial) factorization of as a by- N
N
product (for a composite ), which is both unnecessary and – as has been said already
– widely believed to be impossible to accomplish in a reasonable time. So we must ask:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

15. The prime numbers 41

Question 2. Is primality testing fast?

The above question is about the existence of an efficient algorithm. In order to find
such an algorithm, it is necessary to observe some special features of prime numbers
which can be used for the testing procedure. One of such observations was Fermat’s
little theorem. Another one is:
Theorem 22. (Wilson’s theorem) For any N, 2, n2 n>
(n 1)!  1(mod n) ,n is a prime number.
Example.
! For n=8 we have 7!=5040  0 so 8 is not a prime.
8

! For n =11 we have 10!=3628800  10  1 so 11 is a prime.

11 11

Although interesting, Wilson’s theorem is not of practical importance for primality

testing (it would result in a very slow algorithm). Still, this theorem shows that there are
possible some characterizations of primality in different terms. In practice, the problem
of primality testing is solved by probabilistic algorithms, e.g. so-called Miller-Rabin
test. Such tests are based on some simple observations concerning prime numbers and
give you the correct answer only with some positive probability. In the case of Miller-
Rabin test, it is based on some simple corollaries from Fermat’s little theorem. If it
returns „composite”, the number is indeed a composite one but if it returns „prime”, you
cannot be totally sure that this is indeed the case. However, you may reduce the prob-
ability of error as much as you wish and in practice this probabilistic test works very
well. And what if you have to be sure that a given number is indeed a prime? For a
long time there have been no means of checking this fast enough (similarly as for the
factorization problem). Only in 2002 did Agrawal, Kayal, and Saxena give so-called
AKS primality test which is a deterministic algorithm and can be used to prove that
a number is a prime. This algorithm is much slower than probabilistic tests (e.g. the
n
running time of Miller-Rabin test is essentially O(length( )3) while the fastest known
n
version of the AKS test requires O(length( )6+ o(1)) binary operations, for a given integer
n ). Still, the existence of this algorithm is quite amusing and suggests giving second
thought to the possibility of existence of a fast algorithm for the factorization problem,
doesn’t it?
Summing up, we have our answer to Question 2: Yes.
The search for primes. By Theorem 18 we know that there are infinitely many prime
numbers. Since these numbers are so important in applications, and because people like
to compete, there is a money prize for finding big prime numbers. Such prize is offered
by Electronic Frontier Foundation (see https://www.eff.org/awards/coop). Cur-
rently, a prize of $ 150 000 is offered „to the first individual or group who discovers a
prime number with at least 100 000 000 decimal digits”. The previous prize offered
by EFF was $ 100 000 and it was awarded in 2009 to the GIMPS project for finding a
prime with at least 10 000 000 decimal digits. GIMPS (Great Internet Mersenne
Prime Search) is a large scale distributed computing project aiming at finding so-
p
called Mersenne primes (these are primes of the form 2p 1, where is also a prime).
Up to now, 48 such primes have been found, the largest one having 17 425 170 decimal
digits. Nobody knows if there are infinitely many Mersenne primes. You can join the

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

42 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

GIMPS project if you wish. If your computer finds a new record 108-digit prime number
using GIMPS software, you will have to split the prize with the GIMPS project; also
awards of about $ 3 000 are offered by GIMPS itself for finding a new Mersenne prime
(see http://www.mersenne.org/legal/#mpa for details).
Unsolved problems. Besides the famous Riemann Hypothesis, there are tons of un-
solved problems in Number Theory. Some of them can be found at http://en.wikipe-
dia.org/wiki/Unsolved_problems_in_mathematics#Number_theory_.28general.29.

16 Systems of linear equations

16.1 From one to several equations
Looking back at the previous sections, the following reflection might be in order: we
developed our new tools and ideas mostly to be able to solve some equations. In a very
general meaning of the word, mathematics is about solving – a proof of a hypothetical
proposition may be treated as a solution to an „equation” of the form: the assumptions ^
)
(an unknown reasoning ) the proposition. In this section we are going to learn how
to solve another class of equations and systems of equations, so-called linear ones.
Let us begin with some examples.
x y
Example. The equation 2 +3 =1 defines a line in R2 (hence, this is a linear equa-
tion with infinitely many solutions in R2):

y
1
1 1 x
1

Let us recall that in Section 11 we sought for the integer solutions of this equation, which
in turn corresponds to finding integer points lying on the above line (e.g. the points
; ;
( 1 1) and (2 1)). In another words, if you had a big enough piece of grid paper, a
long enough ruler and if you were accurate enough, you would be able to solve (in Z)
all equations of the form a
x b
y c
+ = , where a;b;c 2 Z with almost no calculations.
It also makes sense to consider the equation 2 x +3 y =1 from the above example
over Zp, where p is a prime number and p >5 (of course in this situation + means +p
and
means
p). Indeed, multiplication by 3 in Zp produces an equivalent equation
1

y=3 +p (p 2)
p 3
p x= +p
p x which defines „a line” in Zp. Clearly, the inverses

1 1 1 2

in the last formula are to be understood in Zp but other than that, this formula for y is
3 3

in principle the same as the one over R which reads y = +
x. This suggests that 1

3
2

such equations could be considered more abstractly (namely over fields) and that there
should be no major differences between solving them over R and over an abstract field
K.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16. Systems of linear equations 43

x y
Example. Consider the equation 2 +3 =1 in Z25 (=Z5 Z5). We easily find that 
3 1 =2 in Z5. Hence and by the above observations, our equation is equivalent to = y


x x
2 +5 ( 2) 5 2 5 =2 +5 . This means that becomes a function of . The table of y x
values of this function is as follows:
x 0 1 2 3 4.
y23401
Graphically, the „line” 2 x +3 y =1 in Z 2
5 looks like this:
y
5
4
3
2
1
0 12 34 5 x
In general, a linear equation may have many variables and may have coefficients in
any field. Here is the formal definition:
; ;

Definition 18. (Linear equation) Let (K + ) be a field. A linear equation in n
x ;x ;:::;x
variables 1 2 n over K has the form 1 1 + + n n = , where 1 a
x ::: a
x b
n K a ;:::;a 2
are the coefficients and b2 n
K is the constant term. The subset of K built of all S
the solutions to a linear equation is called (if =
/ =/ Kn ): ? S
a point (if n=1),
a line (if n =2),
a plane (if n =3),
a hyperplane (in general).

Example. 2 + πx y 2
z p
= 2 is a linear equation in
3
3 variables x;y;z over R. This
equation defines a plane in R3:

If you intersect several hyperplanes you get either an empty set or another hyper-
plane:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

44 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Examples of various configurations of planes in R3. Let’s say we are given two or
three equations of the form ax by cz d
+ + = , where a;b;c;d 2
R and let’s say we want
to solve them simultaneously. This means that we want to solve a system of linear
equations. The set of solutions of this system consists of exactly those points in R3
that lie in the intersection of all the hyperplanes defined by the equations of the system.

a) Two parallel planes – b) Two planes c) Parallel planes – no

no points in common. intersect – a line in points in common to all
common. three.

d) Two parallel planes e) Three planes inter- f) Three planes intersect

and a third one inter- sect in pairs only – no along a common line.
secting these two – no points in common to all
points in common to all three.
three.

g) Three planes inter-

sect – a unique point in
common.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16. Systems of linear equations 45

The formal definition of a system of linear equations is:

Definition 19. (A linear system) Let (K; +;
) be a field. A system of linear equa-
tions over K (briefly: a linear system) is a finite (non-empty) set of linear equations

8
over K. Usually such a system is written in the following form:

<a

x +::: + a n

xn = b

:am

x +::: + amn

xn = b
m ;
11 1 1 1

1 1

a ;b 2
where ij i K. A solution (in Kn) of this system is any point =( 1 n) Kn a a ;:::;a 2
that satisfies all equations of this system (this means that the substitutions 1 = x
a ;:::;x a
1 n = n lead to genuine equalities in K). A linear system is called consistent
if it has at least one solution and inconsistent in the opposite case.
Our objective is to learn how to solve linear systems. We begin with some simple ones...

16.2 Triangular systems and back substitution

There are situations when a system is really easy to solve. A general class of such
systems is the following:
Definition 20. (Triangular system) A linear system is in triangular form and is

8
called a triangular system if it is of the form

>
>a x + a x + a x +::: + a n xn = b
< a x + a x +::: + a n xn = b
11 1 12 2 13 3 1 1

a x +::: + a n xn = b ;
22 2 23 3 2 2

>
>




33


3 3 3

: ann xn = bn
where a ;:::;ann are non-zero elements of the field of coefficients K.
11

Note that a triangular system always has the same number of variables as the number of
equations. Moreover, if we set 1 x >x >:::>x
n then every equation of a triangular system
x
2

has a different greatest variable j . This variable is called the leading variable of the
equation. In another words, one can say that a system is triangular (up to permutation
of the equations) if its every variable is a leading variable of exactly one equa-
tion of the system . Usually, when no ordering of variables is mentioned, one means the
lexical (=dictionary) ordering, or an ordering which is clear from the context.

8
Example of solving triangular systems using back substitution. Consider the system

>
< 3w + 24 xx + 73 yy + z == 10
> 5 y 2 z = 1 :
: 3z = 6
If we setw>x>y>z then we see that every equation has a different leading variable
(and in exact this order); hence this is indeed a triangular system.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

46 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

In order to solve the system, we start with the simplest equation which is the one
z
involving the smallest variable as the leading variable. We get 3 =6 z ,z
=2. Now we
z
use the discovered value of and substitute this value into the other equations. The next
simplest equation that we get in this way is the second from the bottom of the system:
5 y 2
2 =1 ,5 y =5 ,y =1:
z
Now we also substitute y =1 into the other equations. The third one from the bottom
of the system becomes:
2 x 7
1 +2 = 1 ,2 x =4 ,x =2:
y z
Lastly, we also substitute this value of z into the first equation to get
3 w +4
2 +3
1 =0 , 3 w= 11 ,w = : 11

x y
3

Summing up, our system has the unique solution equal to ( ;;;
w;x;y;z
)= 3 2 1 2 . This 11

means that this system corresponds to case g) of example on page 44 (although in R4).
Note also that we could consider this system over Zp where p> P and p2 11. In such
a case, at each step we should solve our equations in this Zp. It is easy to see that for
w

this particular system the solution would be the same except that = 11 p 3 1 where
p2 p6
3 1 is the multiplicative inverse of 3 in Zp. For P but 7 our system cannot be
p
considered over such Zp unless you reduce its coefficients modulo . If you do so than
p
various things may happen. For instance, if =7 then you still have a triangular system
with unique solution ( w;x;y;z ;;; p ;;
)=(6 2 1 2) (check!) but for =2 3 5 you do not have a
w;x;y;z ; ; ;
triangular system any more. In Z2 the solution is ( )=(1 0 1 0), in Z3 there are
w;x;y;z
t ;t ;t;
no solutions and in Z5 the solutions are of the form ( )=(4 5 +5 3 +5 1 2),
where t2 Z5 (you will learn how to solve such systems later on).

The process of solving triangular systems using the method sketched in the above
example is called back substitution. Note that in each case in which we had a triangular
system there was only one solution to such system (see the example above). This is not
accidental, as it turns out:

Property 9. Every triangular system of equations (over any field K) has exactly
one solution in Kn. This solution can be found using back substitution.

16.3 Matrix notation for a linear system

The idea behind solving a general system of linear equations is simple: we will try
to gradually transform a given system in such a way that its solution set will not change
but the system itself will get simpler and simpler up to a point where it will be easy to
read off the solutions (as was the case for triangular systems). In order to be able to do it,
we must understand what transformations are allowed for a linear system of equations.
Let us see this by example:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16. Systems of linear equations 47

Example. Consider the system

8
< w + 2x + 3 y 5z = 1 (E )
:7ww + 24 xx 46 yy ++ 102 zz == 12 (E ) :
1

(E ) 3

Here is what we can do:

1. We can multiply the first equation by 2 so that (E1) goes into 2 w+4 x+6 y
z
10 =2. This transformation may be denoted by 2 E1 E1. !
2. Next, we can add this new equation to equation (E2) to get w=4. This trans-
formation may be denoted by E1 +E2 E2. !
3. We can interchange the second and third rows. This transformation may be
denoted by E2 E3. $
After these transformations (applied one after another) our system becomes
8
< 2 w + 4 x + 6 y 10 z = 2 (E )
: 7 ww + 2 x 4 y + 2z == 14 (E ) :
1

(E )
3

Now we can apply the transformations E1 2E !E and E2 +7 E3 !E to get

8
3 1 2

< 4 x + 6 y 10 z = 6 (E )
: w 2 x 4 y + 2 z == 294 (E ) :
1

(E ) 3

Using E1 2E !E and E1 $E we get

8
2 1 3

<w = 4 (E )
: 2x 4 y + 2 z = 29 (E ) :
1

(10)
14 y 14 z = 64
2

(E )
3

This system is quite similar to a triangular one but it is not such because the variable
z is not a leading variable of any equation of this system (a more basic reason for this
is that in our system there are less equations than variables so no matter what you do
you cannot reduce it to a triangular form).
To finish our work, we might apply the method of back substitution, but for this we
need a triangular system. This is easy to achieve – we can look at the non-leading vari-
z
able in the last equation of the system and treat it as a parameter (in our case varying
s
over R). So we introduce a new name, e.g. , and we set = . At this point, we may z s
s
treat as a (fixed but arbitrary) constant and rewrite our system in the following form:
8
<w = 4
: 2x 4 y = 29 2 s :
14 y = 64 +14 s

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

48 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

In this way we constructed a triangular system (in the variables ), which we can w;x;y
solve by back substitution. Applying this method we get the following solutions (exactly
s
one for each value of ):


(w;x;y;z)= 4; 5 +s; 4 +s;s , where s 2R .5 4

14 7

Exercise 8. Reduce the coefficients of the system from the example on page 45 modulo 5, and solve
this reduced system over the field Z5.
The above example revealed the allowed transformations on linear systems and also
showed that we cannot expect to be able to transform every given system to a triangular
one. Before we proceed any further, it will be convenient for us to change our language.
Namely, observe that in the examples worked out in this section little role was played by
the variables themselves. They are just names, placeholders and what matters most are
the coefficients of the systems. This suggest that we should be able to dismiss variables
from our notation, but doing so we must nevertheless retain the structure of our system
as to not loose any crucial information. This simple idea leads to the notion of a matrix .
Definition 21. (Matrix) A matrix of shape is a rectangular table of numbers mn
(more generally: of elements from a field K or from some other set) having m
n
rows and columns. The elements of a matrix are called its entries and the num-
mn
bers , are called its dimensions.
In the context of matrices with coefficients in a field K, the elements of K are often des-
ignated as scalars.
Notation. The set of ( mn
)-matrices with coefficients in a set will be denoted S
S
by m  n. For a matrix A2S
m n its entry in the -th row and -th column will i j
A
be denoted by ij and the matrix itself will be written as =[ ij ]11 66 ij66mn or just A A
A A
=[ ij ] if the dimensions are clear from the context. A graphical presentation
A
of a matrix
2 A A ::: A n
looks like this:
3 0 A A ::: A n 1
A=664 A::: A::: ::: An 77 or A=B
@ A::: A::: :::::: A:::n
B C
C
11 12 1 11 12 1

21

::: :::
22 2
5 21 22 2
A.
Am Am ::: Amn
1 2 Am Am ::: Amn
1 2

Sometimes it is also convenient to denote the entries of a matrix A by aij.

Once we have defined matrices, we may use them to encode systems of linear equa-
tions. Namely, with a system
8
<a

x +::: + a n

xn = b

:am

x +::: + amn

xn = b
m
11 1 1 1

1 1

2 a a ::: a n 3
we may associate its coefficient matrix and its augmented matrix :
2 a a ::: a n b 3
66 a a ::: a n
11 12 1
77 66 a a ::: a n b 77:
11 12 1 1

4 ::: ::: ::: :::

21 22 2
5 4 ::: ::: ::: ::: ::: 5
21 22 2 2

am am ::: amn
1 2 am am ::: amn bm
1 2

coefficient matrix augmented matrix

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16. Systems of linear equations 49

The augmented matrix contains all the necessary information about the system and we
may effectively work with this matrix to find the solutions of our system. The three basic
transformations of linear systems considered in the example on page 47 can be trans-
lated into appropriate transformations of rows of matrices associated to such systems:
Definition 22. (Elementary row operations on matrices) Let K be a field. The
three types of elementary row operations on matrices from Km  n are:
1. Interchanging two different rows. (Ri $Rj)
2. Multiplication of a row by a nonzero scalar. (
Ri !Ri)
3. Addition of a multiple of one row to another one. (
Ri +Rj !Rj)
Two matrices are said to be row-equivalent when one can be obtained from the
other by some number of (successively applied) elementary row operations. We will
use the notation AB to indicate the fact that the matrices and are row-equiva- A B
lent. It is not hard to observe what follows:

Property 10. Let K be a field, m;n2N. For matrices in Kmn:

1. Every elementary row operation is reversible by an elementary row opera-
tion of the same type.
2. The relation of being row-equivalent is an equivalence relation in Km  n.

Example. Let us rewrite the transformations performed on the system of the example

8
on page 47 in the language of elementary row operations on matrices. The system was:

< w + 2x + 3 y 5z = 1
:7 ww + 42xx 64 yy ++ 102 zz == 12 :
2 3
The augmented matrix associated to this system is:
1 2 3 5 1
4 1 4 6 10 25:
7 2 4 2 1
Now we shall perform row operations on this matrix mimicking the linear system trans-

2 3 2 3 2 3
formations applied in the aforementioned example:

1 2 3 5 1 2 4 6 10 2 2 4 6 2
4 5
1 4 6 10 2  4 5
1 4 6 10 2  4 1 0 0 0 45 
10

7 2 4 2 1 R !R 7 2 4 2 1 R R !R 7 2 4 2 1 R $R
2 2 4 6 10 23 2 0 4 6 10 63
2 1 1 1+ 2 2 2 3

4 7 2 4 2 15  4 7 2 4 2 15 
1 0 0 0 4 R R !R 1 0 0 0 4 R R3 ! R2
2 3 2 0 0 14 14 64 3 2 1 3
1 2 3 1 2 +7

0 4 6 10 6 0 0 0 4
4 0 2 4 2 29 5  4 0 2 4 2 29 5  4 0 2 4 2 29 5:
1 0 0 0 4 R R !R 1 0 0 0 4 R $R 0
1 2 2 1 1 3 0 14 14 64

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

50 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

This last matrix is the augmented matrix of linear system (10), which is an illustration
of the fact that working with matrices is equivalent to working with the systems them-
selves.

16.4 Row echelon form of a matrix

The matrix we produced as the final one during our calculations in the above
example is of a very special form (similarly as the system (10) corresponding to this
matrix). Such matrices are said to be in row echelon form (you can also say that the
system (10) is in echelon form ). The word „echelon” means a stair-like military forma-
tion (of ships for example). The formal definition of such matrices allows the possibility
that they contain zero rows (=all entries in these rows are equal to 0):

Definition 23. (Row echelon form) Let K be a field and A2

Km  n. When a row
A
of is non-zero, its first (from left) non-zero entry is called the leading entry (of
that row). The matrix A is said to be in row echelon form (ref) if:
1. any zero rows of A are below all non-zero rows of A,
2. for two neighbouring non-zero rows of A, the leading entry in the lower
row is further to the right than the leading entry in the higher row.
If moreover:
3. every leading entry of A is equal to 1,
4. every column of A containing a leading entry has all its other entries equal
to 0,
then the matrix A is said to be in reduced row echelon form (rref).
By the above definition, a matrix in rref is also in ref.

Terminology. Sometimes the leading entries of a matrix are called pivots, their loca-
tions in this matrix are called pivot positions and the rows (columns) containing a pivot
position are called pivot rows (columns).

Example. Consider
21 3 5 0
3 21 3 0 0
3
660 0 1 077 6600 1 077
40 0 0 25 400 0 1 5.
0 0 0 0 0 0 0 0
The first matrix is in ref and the second one is in rref. Moreover, the first matrix can
be transformed into the second one by a sequence of elementary row operations.

The significance of echelon forms is justified by the following fact:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

16. Systems of linear equations 51

Theorem 23. (Reduction to echelon forms) Let K be a field. Every matrix A2

Km  n is row-equivalent to a matrix in rref, denoted by RREF(A) and called the
A
reduced row echelon form of the matrix . Moreover, the matrix RREF(A) is unique
(does not depend on the sequence of elementary row operations used to transform
the matrix A into RREF(A) ). More precisely, if then RREF(A) = RREF(B). AB
Even more importantly, when an augmented matrix is in echelon form the system
corresponding to this matrix is easy to solve:

Example. Consider the matrix

21 2 5 2 3 2
3
40 0 2 1 4 1 5. (11)
0 0 0 0 1 2
This matrix is in ref. In order to solve the system it represents, you may proceed two-
fold.
I. Write down this system just now. Using variables v;w;x;y;z ordered lexically
we get
8
<v 2 w+5 x+2 y +3z = 2
: 2 x + y +4 z = 1.
z= 2
Now we may use a variant of the back substitution method to solve this system
(cf. the trick used in the example on page 47). Namely, since and are not w y
leading variables of the above system, we treat them as parameters: = , = w sy t
8
and rewrite the system in the following form:
>
>v +5 x+3 z = 2+2 s 2 t
< w= s
> 2 x +4 z = 1 t , where s;t; 2R.
>
: y= t
z= 2
At this point we have a system in triangular form with respect to our ordering of
the variables and we may solve it by back substitution (do this yourself!). Since
there are two parameters necessary in order to describe the set of solutions of
this system, we conclude that the solutions define a plane in R5.

21 2 5 2 3 2 3 21 2 5 2
II. Transform matrix (11) into its rref. In this case
0 4
3
40 0 2 1 4 1 5  40 0 2 1 0 95 
0 0 0 0 1 2 R R !R 0 0 0 0 1 2 R !R
21 2 5 2 0 4R3 R !R 21 2 0 3
4
1
2 3 2 2 2
2
1 3 3 1

0
640 0 1 0 75  6640 0 1 77.
1 37

5
2 2

0
1 9
1 9
2 2

0 0 0 0 1 2
2 2
R R !R 1 5 2 1
0 0 0 0 1 2
" "
w s = y t
=

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

52 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

This last matrix is already in rref. Now you may either proceed as before (apply
method I to this matrix) or treat the columns that do not contain leading entries
21 2 s
as corresponding to parameters ( =
0 t 0
3 w s;y 21t
= let’s say) and continue as shown:
0 0 0 0 +2s+ t7
3
66 77and then 66
1 37 37 1

40 0 5 40 t 75.
2 2 2 2

1 1

2
t 0 9

2
0 1 0 0 9

2
1

0 0 0 0 1 2 0 0 0 0 1 2
The system corresponding to the last matrix is trivial to solve with respect to
v;x z w sy t
and (but you have to remember that = , = is a part of the solution).
The two methods of solving linear systems, outlined in the above example, can be
loosely summarized as follows:
Gaussian elimination. In order to solve a linear system you should:
1. write down the augmented matrix of the system,
2. transform this matrix into a new matrix being in ref,
3. translate the new matrix into the linear system it represents,
4. treat all non-leading variables as parameters (introduce new names for
that) and move them to the right-hand side of the system, ( j = j) !x s
5. solve the triangular system you have arrived at using back substitution (re-
x s
member to take into account the equations j = j defining the parameters).
Gauss-Jordan elimination. In order to solve a linear system you should:
1. write down the augmented matrix of the system,
2. transform this matrix into its rref,
and then either
3a. repeat steps 3.–5. of Gaussian elimination,
or
3b. multiply the columns not containing leading entries by new variables treat-
ed as parameters (but not the last column!), ( j = j j j j) ! x s ;s C !C
4b. subtract the columns with parameters from the last column, zeroing them
afterwords, ( n+1 j !C
n+1) j 0
PC !C ;C !
5b. read off the solutions from this matrix (remember to include appropriate
x s
equations j = j defining the parameters).

Warning. In both above methods, the names of the new parameters (variables) must
all be different from each other.
Commentary. Another variation of Gauss-Jordan method would be to also add new
rows to the matrix from step 4b, namely those corresponding to the equations j = j . x s
In this way, you get a triangular system with all the necessary information in step 5b.
Note also that in Gauss-Jordan method you may work with columns. This is some-
thing new but such operations will reappear later on, in another context.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

17. The algebra of matrices 53

17 The algebra of matrices

While we defined matrices just in order to simplify our notation, it turns out that
matrices are interesting in its own right. Namely, one may define natural (as it will turn
out later) operations on matrices of matching shapes:

Definition 24. (Operations on matrices) Let (R; +;
) be a ring, not necessarily

commutative.
1. Let A;B 2R
m n , A=[aij], B =[bij]. The sum A+B of matrices A and B is
a matrix of size mn given by the formula
A+B :=[aij +bij] 66ij66mn . 1
1

2. Let A 2 Rm  n , B 2 Rn  p , A =[aij ], B =[bkl]. The product A
B of matrices

A and B is a matrix of size m p given by the formula
A
B :=[cil] 66li66pm, 1
1
where
cil :=ai
b l +::: +ain
bnl , for 1 6i 6m; 1 6l 6 p.
1 1

3. Let A 2 Rm  n , A=[aij ] and 2 A. The (left) scalar multiple
A of A by

is a matrix of size mn given by the formula

A:=[
aij].
Similarly one may define the right scalar multiple A
of A by :
A
:=[aij ].
Note that two matrices can be multiplied only if the number of columns of the first
matrix is the same as the number of rows of the second matrix. Moreover, the scalar
multiplication does not commute (that is in general =
/ ) unless the ring is A A R
itself commutative.

Example.
1. Let 21 23 2 0 33
A:=42 35and B :=4 4 35.
0 5 2 1
Then 21+0 2+33 2 1 13
A+B =42+4 3+35=4 6 65.
0 2 5+1 2 6
2. Let 21 23 1 
4 5
A:= 2 3 and B := 0 0 2
1 3 .
0 5

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

54 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Then
21
1+( 2)
0 1
0+( 2)
( 1) 1
2+( 2)
( 3)
3
A
B = 4 2
1+3
0 2
0+3
( 1) 2
2+3
( 3)5=
21 2 83 0
0+5
(
0
1+5
0 1) 0
2+5
( 3)
= 42 3 55.
0 5 15

Moreover,
 1
1+0
2+2
0 
1
( 2)+0
3+2
5
B
A = 0
1+( 1)
2+( 3)
0 0
( 2)+( 1)
3+( 3)
5 =
 1 8
= 2 18
.

3. Let
21 23
:= 3 and A:=42 35.
0 5
2 3
1 3
( 2)3 2 3
Then
3 6

A=4 3
2 3
35=4 6 95.
3
0 3
5 0 15

AB BA
The above example shows in particular that even if both products and are
AB BA
defined, then in general =/ (cf. item 2). One might guess that this is because
AB BA
the above two products are of different sizes. But when are the sizes of and the
same? Well, if A2R B2R m  nAB 2R
, n BA
 p then m  p . Since should also be defined,
p m AB2R
first of all we must have = . But then BA2R m m and n n. If these sizes are
m n A2 R B 2R
to be the same, we must also have = . This means that m m and m  m.
A
Such matrices are called square; more precisely, a matrix is called square of order
n nn
if it is of size n R
. The set of all square matrices of order with entries in a ring
M n;R
will be denoted by ( A;B2M n;R AB2M n;R
). Note that if ( ) then also ( ) so the
n
operation of multiplication of square matrices of a given order is an inner operation
in (M n;R AB BA
). This is nice, but does equal for square matrices? The answer is no:

  2 1 
Example. Let

A:= 11 20 and B := 0 2 .

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

17. The algebra of matrices 55

Then
  1 2 
AB = 22 51 and BA= 2 4 .
Hence AB =/BA.
You may wonder what sort of properties do hold for the matrix operations + and

. The following theorem provides a partial answer to such question.
Theorem 24. (General properties of matrix operations) Let R be a commuta-
tive ring. Then:
1. (Rmn; +) is an abelian group. The identity of this group is the zero matrix
O 2Rmn defined as 2 0 0 ::: 0 39 >
>
=
6
O :=6
0 0 ::: 0 7
7
4 ::: ::: ::: ::: 5> m
0 0 ::: 0 >
rows.

;
|||||||||n||||{z}}}}}}}}}}}}}}
columns

The inverse element of a matrix A2R

m n is the matrix A :=( 1)
A,
where 1 is the inverse element to the identity element 1 2R.
2. The operation
is associative in the following sense: if A2Rm  n, B 2Rn  p,
C 2Rpr (that is if the sizes of the matrices match) then
A
(B
C)=(A
B)
C.
3. The operation
is distributive over + in the following sense: if A 2 Rm  n,
B;C 2Rn p then
A
(B +C)=(A
B)+(A
C)
and also if A;B 2 Rm  n, C 2 Rn  p then
(A+B)
C =(A
C)+(B
C).
4. Scalar multiplication is compatible with matrix multiplication in the following
sense: if A2R B 2R
m  n, n  p and 2R then

(A
B)=(
A)
B =(A
)
B =A
(
B)=A
(B
)=(A
B)
.

Theorem 24 exhibits interesting properties of the matrix operations. While all of them
are straightforward to check, the verification of associativity of matrix multiplication is
somewhat tedious (but try to do it!). As was the case in earlier sections, such associative
property means we can safely skip all the brackets when multiplying matrices (also
for the scalar multiplication). Similarly, we agree (as usually) that has a greater

priority than + so that we will skip even more brackets in expressions in which both +


and are involved, e.g. A
B A
C
+ means ( A
B A
C
)+( ). However, as we have seen
already, we cannot interchange the order of the factors when multiplying matrices.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

56 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Example of associativity of matrix multiplication. Let

1 1  0 2   3
A:= 1 0 , B := 2 1 and C := 0 .
We have
  3 6
(AB) C = 20 32 0 =0
and
1 1 0 6
A(BC)= 1 0 6 =0 .

Hence, (AB) C =A(BC).

Theorem 24 can be strengthen for square matrices:

Theorem 25. (Algebra of square matrices) Let be a commutative ring. Then R

M n;R ; ;

( ( ) + ) is a ring with unity. Its multiplicative identity is the identity matrix
In2M n;R
( ) given by
2 1 0 ::: 0 39 >
>
=
6
6
In :=4
0 1 ::: 0 7
7
::: ::: ::: ::: 5> >
n rows.

0 0 ::: 1 ;
|||||||||n|||||{z}}}}}}}}}}}}}}
columns

Moreover, the condition 4 of Theorem 24 holds, which may be expressed by say-

ing that ( M n;R
) is a (unitary associative non-commutative) algebra over . R
In the particular case of n=1 the ring M(1;R) is just R. This means that if R is a
field then M(1;R) is also a field. Hence, a natural question is: is M(n; K) a field if n>1
and K is a (non-commutative) field? The answer is no:

Example. Consider the matrix A2M(2; R) with real entries defined as

1 1 
A:= 0 0 .
1 2 
Clearly, A=/O. On the other hand, for B := 1 2 2M(2; R) we have B =/O and
0 0
A
B = 0 0 =O.
A
This means that is a zero-divisor (see page 15 for the definition). By Property 3, is A
M ;
not invertible in the ring (2 R), although = A
/ O. Hence, (2 R) is not a (skew) field.M ;

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

18. Which matrices are invertible? 57

18 Which matrices are invertible?

Let us begin by setting some commonly used terminology. An invertible matrix (see
Definition 9 item 1 for the general notion of an invertible element of a ring) is often called
non-singular and a matrix that is not invertible is called non-invertible or singular .
Definition 25. (The set of non-singular matrices) Let K be a field. We define
GL(n; K):=fthe set of non-singular matrices A2M(n; K)g.
The set GL(n; K) will be called the general linear group (of degree n over K).

It is easy to see that if A;B 2GL(n; K) then A 2GL(n; K) and A
B 2GL(n; K). 1

Indeed, this reduces to noting the familiar identities (A ) =A and (A
B) =B
A . 1 1 1 1 1

Hence, we get:
Theorem 26. (The structure of GL(n, K)) (GL( n; K);
) is a group.
In principle, the answer to the question in the title of the section is simple: similarly
as was the case with the rings Zn (cf. Commentary on page 23), the invertible elements
M n;
of ( K) are exactly the non-zero-divisors of this ring. To see why this is indeed the
case, first we interpret the elementary row operations on matrices in a new way.
Definition 26. (Elementary matrix) Let K be a field. A matrix ( K) is A2M n;
called an elementary matrix if it is the result of a single elementary row operation
performed on the identity matrix In. More specifically:
! A is an elementary matrix of the first kind if it is the result of the elementary
operation Ri $Rj on In; we will write A=Eij.
! A is an elementary matrix of the second kind if it is the result of the elemen-
tary operation Ri !Ri on In (here = / 0); we will write A=Ei( ).
! A is an elementary matrix of the third kind if it is the result of the elemen-
tary operation Ri +Rj !Rj on In; we will write A=Eij ( ).

Remark. The distinction between elementary matrices of the first, second and third
kinds is merely a matter of terminology convenience. Thus, depending on author’s pref-
erences, the enumeration of these kinds may vary.

00 00
The general form of elementary matrices can be represented graphically as follows:

0 0 0 0
2 3 2 3
1
6
6


...



0

7
7
6
6
1 ...





0

7
7
6 7 6 7
6 0
6
... 1 7
7 ith row 6 0 ...
6
1 7
7 ith row
Eij = Eij( )=
6 0 0 ... 0 1 7 6 1 0 ... 0 0 7

00 00
6 7 6 7
0 1 ... 0 0 0 1 ... 0 0
6
6
6
6









7
7
7
7
6
6
6
6









7
7
7
7
6 0 0 ... 1 0 7 6 0 0 ... 1 0 7
6
6
6
6
1 0 ... 0 0
7
7
7
1 ... 0 7
j th row 6
6
6
6
0 ... 0 1
1 ...
7
7
7
0 7
j th row
6
4







7
5
6
4






7
5
0 ... 1 0 ... 1

First kind Third kind

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

58 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

2
0
66







Ei( )=66
00
0
1 ... 0
3
77
77 i
00
0 ... 1
1 0 0

4 0 0
0 0 1
1 ... 0








5 th row .

0 ... 1

Second kind

M ;
Example. Consider the set (3 C). The elementary matrix of the first kind corre-
R $R
20 3
sponding to the elementary operation 1 3 is

0 1
E =4 0
13 1 0 5,
1 0 0
The elementary matrix of the second kind corresponding to the elementary operation
1
R !R
2 2 is
21 3

=640 0 0
3

E 2
1
075 1

0 0 1
3 3

and the elementary matrix of the third kind corresponding to the elementary operation

R R !R
i 2 + 3 3 is 21 3
0 0
E (i)=40
23 1 05.
0 i 1
The first simple observation concerning elementary matrices is the following:

Property 11. Every elementary matrix is non-singular. Its inverse is an elemen-

tary matrix of the same kind. More specifically,

(Eij) =Eij ;
1
Ei( ) =Ei
; 1 1
Eij( ) =Eij( ).
1

The above property is not accidental, because it is just a restatement of an analogous

property of elementary row operations on matrices (cf. Property 10 item 1). This is a
consequence of:
Theorem 27. (Elementary operations and elementary matrices) Let K be a
field and let A2Km  n. The matrix that is the result of applying an elementary
row operation to the matrix A
is equal to the product , where ( K) E
A E 2M m;
is the elementary matrix corresponding to this elementary row operation.

Example. Consider the matrix 22 13

A:=43 45.
0 3

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

18. Which matrices are invertible? 59

If we want to perform the row operation ( 2)
R +R !R 2 3 3 on A, we may to this by

computing the following product:
21 0 0 2 1 2 1
32 32 3
E ( 2)
A=40
23 1 0
3 4 = 3 45.
5 4 5 4
0 2 1 0 3 6 5

Using Theorem 27 and Theorem 23 we immediately conclude:

Corollary 6. Let K be a field and let A2Kmn. Then there exist elementary matri-
E ;:::;E 2M m;
ces 1 r ( K) such that
RREF( A)=Er
Er
:::
E
A. 1 1 (12)

Let us observe that equality (12) tells something useful about invertibility of the
matrix A. Namely, if A 2 M(n; K) then it may happen that RREF(A)=In. In such a
case, putting B :=Er
Er
:::
E we have that B 2 M(n; K) and In =B
A. At this
E
1 1

point we may exploit Property 11. Namely, multiplying this last equality by r 1 from
E E
:::
E
A
left we get r 1 = r 1 E
. Now multiplying this equality by r from right we get
E
:::
E
A
E E
:::
E
A
E
E
1

In = r 1 r . Similarly we find that In = r 2 r r 1. Continuing

A
E
:::
E A
B B A
1 1

this process we finally arrive at In = r 1 = . This means that = 1 .

On the other hand, if RREF(A)= / In then in RREF(A) the last row have to be the
zero one. But this implies that for any matrix C 2 M(n; K) having non-zero entries
in the last column only (so other columns are zero) it holds C
RREF(A) = O or –
in another words – (C
Er
Er
:::
E )
A=O. If n>1, clearly we may choose this C to
be different from O. Since by Property 11 the matrices E ;:::;Er are invertible, we infer
1 1

that also D:=C
Er
Er
:::
E = / O. Summing up, we have D= / O and D
A=O which
1

means that A is a (right) zero-divisor and as such is non-invertible (see Property 3).
1 1

Thus, basically we have proved:

Theorem 28. (First characterization of invertible matrices) Let K be a field.

A matrix A2M n; A A
( K) is invertible iff RREF( )=In and so iff is a product of
B A B
A
elementary matrices. Moreover, = 1 iff =In iff A
B
= I n.
In order to see that a matrix A2M(n; K) which is a right zero-divisor is also a left
zero-divisor we will exploit the following tool:

Definition 27. (Transpose of a matrix) If A=[aij] 66ij66mn is a matrix of size mn

1

A n m defined as AT :=[aji] 66ij66mn .

1
then its transpose T is the matrix of size 1
1

In another words, to transpose a matrix means to interchange its rows with its columns,
or to flip this matrix about the imaginary „diagonal line” emanating from the upper left
corner of the matrix.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

60 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Example. Let
21 3 22 13 1 
A:=4 4 5; B :=43 05; C := 0 24 14 .
3 0 1
Then
2  2 1 0
3
AT =[1 4 3]; B = 1 30 1 ; 0 C =4 2 45.
1 4
The basic properties of the transpose operation are:

8
Property 12. Let R be a commutative ring with unity. Then:

8
1. (AT )T =A (in words: the operation
T is an involution=self-inverse),
A 2 Rm  n

8
2.
m  n
(A+B)T =AT +BT,
A;B 2R
(c
A)T =c
AT,

8
3.
A2R m  n
c 2R
4. (A
B)T =BT
AT,
A 2 Rm  n
B 2Rn  p

6. 8
A 2M n;R
(
;
5. OT =O (In)T =In,

)
(A is invertible )(AT ) =(A )T ).
1 1

All of the above facts are straightforward to check. We remark only that item 6 is a con-
sequence of items 4 and 5 because In =ITn =( A
A
) =( 1)T T and similarly In =
1 T
A
A
A
A A
T ( 1)T which means that the inverse matrix to T is equal to ( 1)T and this A
is what is asserted in item 6.
Assume now that we are given a right zero-divisor matrix A2 M n; A
( K). Hence,
is non-invertible. This means that also T A
is non-invertible (otherwise, by item 6 of the
A
above property, we would have in particular that there exists (( T )T ) 1 which would
mean that A 1
also exists). By Theorem 28 and the analysis on page 59 we know that
A T must be a right zero-divisor; so C
A C 2 M n;
T = O for some non-zero ( K). By
Property 12 items 4–5 we thus get O = O =( ) T A
C A
C
T T T = T C
. Clearly, T is also
A
non-zero and hence is a left zero-divisor in ( K). M n;
Similarly, if A2M n; A A
( K) is a left zero-divisor then is non-invertible so RREF( )= /
A
In and hence is a right zero-divisor.
We may sum up these observations:

Corollary 7. Let K be a field and A2M(n; K). The following conditions are equiv-
alent:
i. A is non-invertible,
ii. RREF(A)= / In,

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

18. Which matrices are invertible? 61

iii.A is a left zero-divisor in M(n; K),

iv. A is a right zero-divisor in M(n; K).

Using the above informations we can indicate a method of finding the inverse matrix
A of a matrix A2GL(n; K). Namely, by Theorem 28, A2GL(n; K) iff
1

Er
Er
:::
E
A=In, 1 1

for some elementary matrices E ;:::;Er 2M(n; K). Moreover, then A =Er
Er
:::
1

E . But this means that also A =Er
Er
:::
E
In. By Theorem 27 the elementary
1 1
1

Ej correspond to elementary row operations. Summing up these observations,

1 1 1

matri-ces
we get:
Theorem 29. (First method of finding the inverse matrix) Let K be a field and
A2M n; A
( K). Then the matrix is invertible iff there exists a sequence of elemen-
tary row operations transforming A
into In. Moreover, if this happens then the
same sequence of elementary row operations performed on the identity matrix In
produces the matrix 1
. A
Note that if A
In then necessarily In =RREF( ) because In is in rref (cf. Theorem A
23). Hence, the above suggests using Gauss-Jordan elimination to find 1
(if it exists). A
A convenient method to accomplish this goal is to adjoin matrix In to the matrix and A
consider the matrix of the form [ A
In ]. If using Gauss-Jordan elimination you manage
 A A
to transform the –part of this matrix to In then the whole matrix will be of the form
In 1
. If you find that RREF( )= A
/ In you may conclude that the matrix is singular. A
A2M(2; Q) be of the form
Example. Let
2 1 
A:= 3 4 .
We adjoin I2 to this matrix and perform the Gauss-Jordan elimination (actually only its
reduction-to-rref part) on it:
2  2  2 
A In = 3 14 10 01  1 1 0
6 8 0 2  1
0 5
1 0
3 2 
R2 ! R2 R1 R2 ! R2 R1 ! R1
2 3 2 3
2 3 + 1
2
1
R2 ! R2
4 1 0 5  41 0 5= In A
5
1 1 8 1

2 2 10 5 1
.
0 1 3

5
2

5
0R1 12 R2!R1
1 3

5
2

2
If our calculations are correct, we have found that
3  
A =4 5= 15
4 1
8 1

10
3 2
1
3
5
2
.
5 5

We may verify our result:

  2 1   
A 1

A= 15
43 12
= 1
5 0 = 1 0 =I .
3 4 5 0 5 0 1 2

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

62 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Thanks to Theorem 28 (second part) we do not have to check the other equality because
it must hold automatically. Thus, we have indeed found the matrix 1
. A

19 Invertibility and determinants

In the previous section we found a characterization of non-singular matrices and we
indicated a first method of finding inverse matrices. In this section we will show how to
achieve these goals in a different, „formula-based”, way. The basic tool that we need for
these purposes is called determinant. Below, we define this concept recursively. This
recursive definition requires also some convenient auxiliary notions:
Definition 28. (Determinant of a matrix, cofactors and minors) Let ( + ) be R; ;

A a 2M n;R
a commutative ring with unity and let =[ ij ] ( ). The determinant of the
A
matrix , denoted by det or A jAj ja j R
or ij , is an element of defined as follows:
1. If n =1, that is if A=[a ], then det A:=a .
11 11

2. If n> 1 then det A:=a
C +a
C +:::+an
Cn , where Cij is called the
cofactor of the entry aij and is defined as Cij :=( 1)i j
Mij , Mij is called the
11 11 21 21 1 1

minor of the entry aij and is defined as the determinant of the (n 1)(n 1)
matrix obtained by deleting ith row and jth column from the matrix A.

Example.
i. It is easy to check that det In =1 and det O =0.
a a 
ii. Let A=
a a 2M(2;R), R"– a commutative
#
11 12
ring with unity. Then

M =det aa jjj aa =det[a ]=a

12 22

—————
11 12
11 22 22

"a j a #
12 22

and

M =det a jj a =det[a ]=a .

21
11

—————
12
12

22
12 12

This gives C =( 1)
M =a and C =( 1) = a

11
1+1
11 22 21
2 +1
12 . Summing up:
det A=a C +a M =a a a a. (13)
22 3
11 11 21 21 11 22 21 12

4 3
6
iii. Let A=41 3 17 5. We have
0 1 2
j2j 4 3 2jj 4 3 2jj 4 3
jAj = 2
( 1) j1j 3 1 +1
( 1) 1jj 3 1 +0
( 1) 1jj 3 1
———————
1+1 2+1 ——————— 3+1

j0 1 2 0j 1 2 0j 1 2 ———————

=
13
(
2
(3
2 ( 1)
( 1)) 1
(4
2 ( 1)
3)+0
(4
( 1) 3
3)=2
5 1
11 +0= 1.
)

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

19. Invertibility and determinants 63

The example above shows how to compute determinants – this can be done using
step-by-step reduction of the dimension of the determinant(s) to compute, up to the
point where one can apply formula (13). While such a procedure always works (by the
very definition of determinant), often various speed-ups are possible. We will see this
shortly, but first let us note the following:

Theorem 30. (Laplace expansion) Let R be a commutative ring with unity and
A2M n;R
( ). Then for every 1 i;j 2f ;:::;ng it holds
det A=a j C j +::: +anj Cnj
1 1 (jth column expansion)
and
det A=ai Ci +::: +ain Cin i
( th row expansion),
Ckl is the cofactor of the entry akl.
1 1

where
22 4 3
3
6
Example. Let us consider the matrix A=41 3 17 5from example iii) on page 62.
0 1 2
We may compute its determinant using e.g. 3rd row expansion as follows:

2 4jj 3 2 4 j3j
jAj=0+( 1)
( 1) 1 j3j 1 +2
( 1) 1 3 1jj =
3+2 3+3

0 1j 2
——————— 0 1 j2 ———————

=1
21 13 +2
21 43 =
13
1
(2
( 1) 1
3)+2
(2
3 1
4)=1
( 5)+2
2= 1.
( )

As you can see, the result is the same as before.

An easy conclusion of the possibility of using rows instead of columns in determinant

computation is:

R
Corollary 8. Let be a commutative ring with unity and ( ). Then det A2M n;R A
A
=det T. In words: the determinants of a matrix and of its transpose are the same.
A computation speed-up is possible in the following special situations:

Property 13. Let K be a field and A2M(n; K). Then:

1. if A contains a zero column (row) then det A=0,
2. if A contains two identical columns (rows) then det A=0,
3. if a column (resp. row) of A is a multiple of another column (resp. row) of
A then det A=0.
Item 1 above is an immediate consequence of Theorem 30. Items 2 and 3, in turn, follow
from a more general fact. Namely, determinants behave nicely with respect to the ele-
mentary row (and also column) operations on matrices:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

64 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Theorem 31. (Determinants and elementary operations) Let K be a field and

let A2M n;
( K).
1. If B is obtained from A by interchanging two rows (columns) of A, then
det B = det A:
2. If B is obtained from A by multiplying a row (a column) of A by some 2K
(here can be zero), then
det B =
det A:
3. IfB is obtained from A by adding a multiple of a row (resp. column) of
A to another row (resp. column) of A, then
det B =det A:
The reason why we may also perform elementary column operations in the above the-
orem comes from an easy application of Corollary 8. Hint: an elementary row operation
A
applied to the matrix T leads to a matrix which when transposed gives the matrix
that is the result of applying elementary column operation to the matrix . A
Example. Using Theorem 31 we may calculate as follows:

2 3 1 2 2 1 0 2 1 2 1 = 2.
1 1 0 C C=!C 1 1 0 C C=!C 0 1 0 =2
( 1) 3+1

1 0
5 4 1 5 3 1
2+ 3 2
2 3 1 1+ 2 1

Using item 2 of Theorem 31 we immediately conclude:

Property 14. Let K be a field, A2M(n; K) and 2K. Then det(
A)= n
det A.
Theorem 31 gives more information that can be seen at first sight. Namely, when
applied to elementary matrices it says that (cf. Definition 26): det Eij = det In = 1,
det Ei( )= det In = and det Eij ( )=det In =1. Combining these formulas with The-
orem 27, we may restate (the „row part” of) Theorem 31 in the following simple form:

Corollary 9. Let K be a field and let A2M n;

( K). For every elementary matrix E2
M n; E
A
( K) it holds det ( )=det det . E
A
A further consequence of Corollary 9 is that if = r 1 RREF( A E
:::
E

), where j are A E
A

elementary matrices, then det = det RREF( ) for some K 0 . Hence det =A 2 nf g A
, A
0 det RREF( )=0. By the analysis on page 59 we know that either RREF( )=In or A
A
RREF( ) has a zero row. In the first case we get det = = A
/ 0 and in the second case
A A
det =0. But by Theorem 28 we also know that RREF( )=In iff is invertible. Hence: A
Theorem 32. (Second characterization of invertible matrices) Let K be a field
and A2M n; A
( K). Then is non-singular iff det = / 0. A
Remark. Last theorem is the reason why invertible matrices are also called non-sin-
gular.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

19. Invertibility and determinants 65

Now let us use informations provided by Corollary 7. Let A;B 2M n;

( K). Assume
A B A B
that or are singular. This means that or are zero-divisors. Hence also A
B
is
A
B
a zero-divisor, so A
is singular. By Theorem 32 we infer that if det =0 or det =0 B
then also det A
B A
B
=0. In another words, in this case det( )=det det . On the A
B
A B
other hand, if both and are non-singular then = r A E
:::
E B F
:::
F
1 and = s 1 for

E ;F
some elementary matrices i j . Successively applying Corollary 9 to these expressions
A B
for and we get
det(A
B) = det(Er
:::
E
Fs
:::
F )=det Er
:::
det E
det Fs
:::
det F =
= det (Er
:::
E )
det(Fs
:::
F )=det A
det B.
1 1 1 1

1 1

Thus we have proved (cf. also Property 2 item 5):

Theorem 33. (Cauchy formula) Let (K ; +;
) be a field and A;B2M(n; K). Then
det (A
B)=det A
det B.
In particular,
1. det:(GL( n; K);
) !(K;
) is a homomorphism of groups,
2. if A 2 GL(n; K) then det A = A . 1 1

det

Thanks to Theorem 32 we already know that the concept of determinant is con-

nected to invertibility of matrices. It turns out that this connection is even deeper. To
explain this, we need:
Definition 29. (Adjoint of a matrix) Let be a commutative ring with unityR
and A2M n;R A
( ). The adjoint (or adjugate) adj( ) of the matrix is given by the A
formula 2 C ... C n 3T
adj(A):=4



5 , 11 1

Cn ... Cnn 1

where Cij is the cofactor of the entry Aij of the matrix A.

Now we can state:
Theorem 34. (Second method of finding the inverse matrix) Let R be a com-
mutative ring with unity and A2M n;R
( ). Then
A
adj A=adj A
A=det A
In.
In particular, if det A is invertible in the ring R then A is invertible in M(n;R)
and
A = A
adj A.
1
det
1
(14)
Note that for a matrix A 2 M(n; K), where K is a field, the condition of det A being
/ 0 so formula (14) holds for all A2GL(n; K).
invertible in K is equivalent to det A=

Example. Consider 2 2 3 1
3
A=4 1 1 0 5.
5 4 1

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

66 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

C =( 1) 1
0 =1, C = 3 1 = 1, C = 3 1 = 1,
We have
1 4 4 1 1 0
1 +1
11 21 31

C = 15 01
12 =1, C 2 1 = 3, C =
5 1
22 = 2 1 = 1, C = 1 1 =
1 0 5 4 32 13

1, C = 52
23
3 = 7, C = 2 3 = 1. Hence,
4 1 1 33

1 1 1 T
2 1 1 1
3 2 3
adj A=[Cij ]T =4
1 3 7 = 1 3 1 5.
5 4
1 1 1 1 7 1
From example on page 64 we know that det A= 2. Using Theorem 34, we thus get
2 1 1 13
A = 4 1 3 1 5. 1 1

1 7 1
2

Verification:
2 1 1 1 2 3 1
32 3 2 2 0 0
3
1
4 1 3 1 54 1 1 0 5= 1
4 0 2 0 5=I . 3

1 7 1 5 4 1 0 0 2
2 2

20 Linear systems revisited

The theory of matrices that we have developed so far may in turn be applied to
linear systems. First, let us take a look at the following matrix equation:
A
X =B; (15)
where A 2 M(n;R);X 2 Rn  m;B 2 Rn  m and R is a commutative ring with unity. If
the matrix A is invertible in the ring M(n;R), then we can multiply equation (15) by
A from left to get
1

X =A
B.
2x 3 2b 3
1

4

5 4

5 1 1

In particular, let us take m=1. This means that A=[aij ] 66ij66nm, X = xn and B = bn 1
1
so equation (15) looks as follows
2a a
n 3 2x
3 2b
3
...
4

11

5
4
5=4
5.
1 1 1

(16)
an ... ann xn bn
1

2a x a
x + ... + a n
xn 3 2b
3
Computing the product gives the equation

+
4

11

1

12
5=4
5
2 1 1

an x + an x + ... + ann xn bn
1 1 2 2

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

20. Linear systems revisited 67

which holds iff

8
<a
x + a
x + ... + a n
xn = b

:an
x


.
11 1 12 2 1 1

(17)
1 1 + an x + ... + ann xn = bn
2 2

2x 3
This means that matrix equation (16) is equivalent to linear system (17) in the sense

that X =4

5is a solution of (16) iff (x ;:::;xn) is a solution of (17). Hence, the above
1

xn
1

analysis gives:

Theorem 35. (A linear system as matrix equation) Let be a commuta- R

tive ring with unity. Consider system ( 17). Let be the coefficient matrix of A
this system. Then ( 17) can be written as
A
X = b ,
2x 3 2b 3 coefficient
matrix
column
of constants

where X =4

5and b =4

5. If A is invertible in M(n;R) then the linear system

1 1

xn bn
( 17) has a unique solution which is equal to
X =A
b. 1

It turns out that there is also another way of solving equation (16) or – what amounts
to the same thing – of solving system (17). Namely, let us multiply the equation
2x 3 2b 3
A4

5=4

5
1 1

(18)
xn bn
by adj A from left. By Theorem 34 we thus get
2x 3 2b 3
det A
4

5=adj A
4

5.
1 1

xn bn
Let us take a look at the right hand side of this equation. This is the matrix whose th i
C b C b ::: C b
row is equal to 1i 1 + 2i 2 + + ni n. But this is, according to Theorem 30, equal
i
to th column expansion of
2a ... a i b a i ... a n 3
det4











5.
11 1 1 1 1 +1 1

|||a||n|||||||...|||||||a||ni||||||||||{z}
1 1 bn }}}a}}}ni}}}}}}}}}}...}}}}}}}a}}nn
Ai =:
+1
}}}}}
In another words, for every i 2f1;:::;ng we get
det A
xi =det Ai.

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

68 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Now, assume we are working over a field K. Then we have two cases. If det =0 then A
A
we get 0=det i, for every i 2f ;:::;ng
1 , which is a necessary condition for solvability of
equation (18) in this case. If det = A
/ 0 then i = det Ai , for every
det A
x 1 . Summing i 2f ;:::;ng
up, we have:
Theorem 36. (Cramer’s rule) Let K be a field. Consider system ( 17). Let be A
the coefficient matrix of this system. Denote by i the matrix constructed fromA A
i b
by replacing its th column with the column of constants of system ( 17).
1. If / 0 then ( 17) has the unique solution (x ; :::;xn) 2Kn, where
det A= 1

xi = det Ai for i 2f1;:::;ng.

det A
2. If det A=0 and det Aj =/ 0 for some j 2f1;:::;ng then ( 17) is inconsistent.
3. If det A=0 and det Ai =0 for every i 2f1;:::;ng then ( 17) is either incon-
sistent or has infinitely many solutions.
(A careful reader might notice that in the discussion preceding Theorem 36 we have not
actually justified why in item 3 above there cannot be a unique solution to the system;
try to think it over!)

Example.
1. Consider the system:
8
<2 x+3 y +4 z =2
:3 xx+47 yy+23zz=0
=1 .

2 32 3 2 3
Written as matrix equation, this system takes the form
2 3 4 x 2
4
1 4 35
4y5=415.
3 7 2 z 0
We have det A = 2

4 3 + ( 1)
( 1)
3 4 + 3
3 4 =
7 2 7 2 4 3
2
( 13)+34 +3
( 25)= 26 +34 75 = 67. Since det A=
/ 0 we know at this
22 3 43
point that our system has a unique solution. To find this solution, we compute:

det A =det41 4 35=2

4 3 +1
( 1)
3 4 +0=2
( 13) 34 = 60,
1

0 7 2 7 2 7 2
2 2 2 43
det A =det4 1 1 35=2
( 1)

1 3 +1
2 4 +0= 2
7+( 8)=
2

3 0 2 3 2 3 2 22,

2 2 3 23
det A =det4 1 4 15=2

1 4 +1
( 1)
2 3 =2
( 5) ( 23)=13.
3
3 7
3 7 0 3 7

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

20. Linear systems revisited 69

According to Theorem 36, this gives

x= A1 =
det
A
det
60
67
= 6067 ;
y = AA = = ; z = AA = = .
det
det
2 22
67
22
67
det
det
3 13
67
13
67

It is easy to check that this (x;y;z) is indeed the solution of our system.
2. Consider the system
8
<2 x+3 y +4 z =2
:2 xx+3
+4 y 3 z =1 .
y +4 z =0
Its coefficient matrix is 2 2 3 43
A=4 1 4 35.
2 3 4
Since the first and the third rows of this matrix are identical, by Property 13 item
A
2 we infer that det =0. On the other hand, one checks easily that det 1 = / 0, A
which by Theorem 36 item 2 means that this system is inconsistent.
3. Consider the system
8
<2x+3 y +4 z =1
:22xx+3
+3 y +4 z =2 .
y +4 z =3
Its coefficient matrix is 22 3 43
A=42 3 45.
2 3 4
Here, again by Property 13 item 2, we infer that det =0. Similarly, det i =0 A A
i ;; A
for =1 2 3, because in every i one of its columns is a multiple of another one
(cf. Property 13 item 3). Clearly, in this case the system is inconsistent because
by subtracting e.g. its first two equations we get 0=1 2= 1.
4. Consider the system
8
<2x+3 y +4 z =1
:22xx+3
+3 y +4 z =1 .
y +4 z =1
As above, its coefficient matrix is
22
3 4
3
A=42
3 45.
2 3 4
We have det A =0 and det Ai =0 for i =1; 2; 3 (same reasons as in the previous
example). But in this case we have infinitely many solutions, because the system
x y z
reduces to only one equation: 2 +3 +4 =1 – a plane in R3.

Examples 3 and 4 show that in general one cannot strengthen item 3 of Theorem 36
(both cases may happen). There are, however, some special cases when more can be said.
The first one is:

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

70 Algebra and Number Theory. Lecture Notes Szymon Brzostowski

Property 15. Using the same notations as in Theorem 36, assume that system
x x
( 17) has only two variables 1 , 2 (and two equations as well). If det =0 and A
A A
det 1 =det 2 =0 then ( 17) has infinitely many solutions.

For the second one, we need the following definition:

Definition 30. (Homogeneous system) Let be a commutative ring with unity. R
A linear system over R
is called homogeneous if its column of constants is zero

8
that is if the system has the form

<a
x + a x + ... + a n xn = 0






.
:an
x
11 1 12 2 1

1 1 + an x + ... + ann xn = 0
2 2

Obviously, a homogeneous system always has a solution (the trivial one, that is x =::: =
x
1

n =0). Hence:
Corollary 10. Using the same notations as in Theorem 36, assume that system
A
( 17) is homogeneous. If det =0 and det i =0 for every 1 , then ( 17) A i 2f ;:::;ng
has infinitely many solutions.

A more detailed information about the number of solutions of a linear system is

provided by so-called Rouché-Capelli theorem. In order to state this result, we need
the notion of rank of a matrix:
Definition 31. (Rank) Let K be a field and Km  n. The rank of , denoted by A2 A
A
rank , is defined as the number of non-zero rows in any row echelon form of . A
It is easy to see that the above definition is indeed correct (that is that for any ref form
A
of the number of non-zero rows is the same). But even more can be said:

Property 16. Let K be a field and A2Kmn. Then rank A6min (m;n). Moreover,
A
rank =rank T. A
We have:

8
Theorem 37. (Rouché-Capelli) Let K be a field. Consider the system
<a
x a
x + ... + a n
xn = b

+
:am
x


, ()
11 1 12 2 1 1

1 + am x + ... + amn xn = bm
1 2 2

where aij ;bi 2 K. Then system ( ) has a solution in K iff the ranks of the coef-
ficient matrix A and the augmented matrix [Ajb] are the same; in symbols – iff
rank A = rank [Ajb]. Moreover, if ( ) does have solutions, then the dimension
of the hyperplane of solutions is equal to n rank A. In particular, ( ) has
a unique solution iff n =rank A=rank [Ajb].

TBC...

Downloaded by Priya Palraj (priya77palraj@gmail.com)

 lOMoARcPSD|56020158

Further reading 71

Further reading
[Gar07] Garrett, P. Abstract Algebra . Available at http://www-users.math.umn.edu/~garrett/m
/algebra/notes/Whole.pdf.
[Goo06] Goodman, F., M. Algebra: Abstract and Concrete. Available at http://homepage.math.
uiowa.edu/~goodman/algebrabook.dir/book.2.6.pdf.
[Sho08] Shoup, V. A Computational Introduction to Number Theory and Algebra . Available at
http://shoup.net/ntb

Downloaded by Priya Palraj (priya77palraj@gmail.com)