Table des matières

1 Mathematical logic 3
1.0.1 Logical connectors . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.0.2 Properties of logical connectors . . . . . . . . . . . . . . . . . . . 8
1.0.3 Mathematical quanti…ers . . . . . . . . . . . . . . . . . . . . . . . 8
1.0.4 Reasonings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Sets-Relations and Applications 13

2.1 Binary relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Algebraic structures 23
3.1 General notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 Subgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Group morphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 Kernel and image . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.1 Subrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.2 Ring without zero divisor . . . . . . . . . . . . . . . . . . . . . . 28
3.4.3 Homomorphism-Isomorphism of rings . . . . . . . . . . . . . . . . 28
3.4.4 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1
 3.5 Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Concept of polynomial with an indeterminate coe¢ cient in a ring 30

4.1 Operations on K [X] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Arithmetic of polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.1 Euclidean division in K [X] . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Concept of rational fraction with an indeterminate . . . . . . . . . . . . 33
4.3.1 Operations on K (X) . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.2 Decomposition of a rational fraction . . . . . . . . . . . . . . . . . 34

2
Chapitre 1

Mathematical logic

Logic can be de…ned as the science of reasoning. It represents a non-empirical science

like mathematics. Its task is to distinguish correct reasoning from incorrect reasoning.
Also to make inferences i.e. draw conclusions, data, information and facts. Any well-
constructed mathematical theory must contain the following points :

Dé…nition 1.1 An axiom is a statement assumed to be true a priori and which we do

not seek to demonstrate. In other words, a principle serving as the basis for a self-evident
demonstration.

Exemple 1.1 Euclid’s axioms for plane geometry

– There always exists a line that passes through two points on the plane.
– Any segment can be extended along its direction into an (in…nite) line.
– From a segment, there exists a circle whose center is one of the points of the segment
and whose radius is the length of the segment.
– All right angles are equal to each other.
– Through a point exterior to a line, one and only one line parallel to this line passes.

Exemple 1.2 Peano axioms for the construction of integers

– The element called zero and denoted 0 is a natural number.

3
 – Every natural number n has a unique successor, denoted s(n) which is a natural
number.
– No natural number has 0 for successor.
– Successor injectivity 8x; y 2 N : s(x) = s(y) ) x = y.
– If a set of natural numbers contains 0 and contains the successor of each of its
elements, then this set is N.

Dé…nition 1.2 A proposition (or assertion) is a statement that can be true or false, not
both at the same time.
p
Exemple 1.3 4= 2 is a false proposition.

Exemple 1.4 j 5j = 5 is a true proposition.

Remarque 1.1 A statement is any mathematical expression containing a variable x

which cannot be said to be true or false and is called a propositional form.

Exemple 1.5 "x be a positive real number" is a propositional form, it becomes a propo-
sition depending on the value attributed to x.

Dé…nition 1.3 A de…nition is a statement in which we describe the particularities of a

mathematical object.

Exemple 1.6 A is said to be a convex set, if for all x; y 2 A, tx + (1 t) y 2 A, where

t 2 [0; 1].

Dé…nition 1.4 A demonstration or proof is the realization of a process which allows one
to move from hypotheses assumed to be true to a conclusion.

Dé…nition 1.5 A lemma is a result of minor importance or a known partial result used
to prove a major result.

Dé…nition 1.6 A theorem is a result of major importance.

4
Dé…nition 1.7 A corollary is a consequence of a theorem.

Dé…nition 1.8 A conjecture is a mathematical result that is assumed to be true without

being able to prove it.

Dé…nition 1.9 A proposition is a mathematical statement that can be true or false, it

is denoted by the letters P; Q; R,...etc.

Every proposition corresponds to a truth table

P P
V or 1
F 0

For two unspeci…ed propositions P and Q, correspond to 22 possibilities of truth attri-

bution
P Q
1 1
1 0
0 1
0 0

In general, for n propositions it correspond to 2n possibilities of truth attribution.

1.0.1 Logical connectors

These are logical connections that allow other propositions to be developed from
certain known propositions.

5
Negation of a proposition

The negation of a proposition P is a proposition denoted P is the opposite or the

opposite of the proposition P . It is de…ned from the following truth table

P P
1 0
0 1

Exemple 1.7 P : x2 + 1 0 its negation is P : x2 + 1 < 0.

Conjunction

The conjunction is the logical connector ^ which associated with the propositions P
and Q the proposition P ^ Q, the latter is true if P and Q are both true simultaneously
and false in the other cases. It is de…ned from the following truth table

P Q P ^Q
1 1 1
1 0 0
0 1 0
0 0 0

Exemple 1.8 P is the assertion "This card is a queen" and Q is the assertion "This
card is a club". The proposition is true if the card drawn is a queen of clubs and false
otherwise.

Disjunction

The disjunction is the logical connector _ which associated with the propositions P
and Q the proposition P _ Q, the latter is false if P and Q are both false simultaneously

6
and true in the other cases. It is de…ned from the following truth table

P Q P _Q
1 1 1
1 0 1
0 1 1
0 0 0

Implication

The implication is the logical connector ) which associated with the propositions P
and Q the proposition P ) Q, the latter is false if P is true and Q is false, and true in
the other cases. It is de…ned from the following truth table

P Q P )Q
1 1 1
1 0 0
0 1 1
0 0 1

Equivalence

Equivalence is the logical connector () which associated with the propositions P

and Q the proposition P () Q, the latter is false if P and Q have the same truth value,
and true in the other cases. It is de…ned from the following truth table

P Q P () Q
1 1 1
1 0 0
0 1 0
0 0 1

7
1.0.2 Properties of logical connectors

Dé…nition 1.10 A proposition that is true regardless of the truth values of the proposi-
tions that compose it is called a Tautology.

Proposition 1.1 Let’s consider the proposals P; Q and R, whatever the truth values of
the latter, the following propositions are always true i.e. are tautologies.
– P _ P;
– P , P;
– P ^ P , P;
– P _ P , P;
– P ^ Q , Q ^ P;
– P _ Q , Q _ P;
– (P ^ Q) ^ R , Q ^ (P ^ R) ;
– (P _ Q) _ R , Q _ (P _ R) ;
– P ^ (Q _ R) , (P ^ Q) _ (P ^ R) ;
– P _ (Q ^ R) , (P _ Q) ^ (P _ R) ;
– P ) Q , P _ Q;
– P ) Q , Q ) P;
– P ^ Q , P _ Q;
– P _ Q , P ^ Q;
– (P ) Q) ^ (Q ) R) ) (P ) R) ;
– (P , Q) , (P ) Q) ^ (Q ) P ) :

Preuve. It is enough to draw up their truth table.

1.0.3 Mathematical quanti…ers

Propositional form

Dé…nition 1.11 A propositional form is a mathematical statement which includes one

or more variables and which is true for certain values attributed to these variables and

8
false in other cases, denoted P (x) or P (x1 ; x2 ; :::; xn ).

Exemple 1.9 x + 1 0 this proposition is true for x 1 and false otherwise.

From a propositional form P (x) de…ned on a set E, we construct new propositions

called quanti…ed propositions using the universal quanti…ers "8" whatever or existential
"9" there exists at least.

Universal quanti…er and existential quanti…er

The quanti…er "whatever", denoted 8, makes it possible to de…ne the proposition

"8x 2 E; P (x)" which is true for all the elements x 2 E. The quanti…er "at least there
exists", denoted 9, allows us to de…ne the proposition "9x 2 E; P (x)" which is true if we
can …nd at least one element x 2 E such that the proposition P (x) be true.

Remarque 1.2 If there exists one and only one element x 2 E, for which P (x) is true
we write "9!x 2 E; P (x)". 9! reads there exists a unique.

Exemple 1.10 8x 2 N : x(2x 3) > 0 is a false proposition.

9x 2 N : x(2x 3) > 0 is a true proposition.

Negation rules

Consider the propositional form P (x) on a set E.

– The negation of 8x 2 E; P (x) is 9x 2 E; P (x).
– The negation of 9x 2 E; P (x) is 8x 2 E; P (x).

Remarque 1.3 We can combine quanti…ers of di¤erent natures, respecting their orders
and not swapping two di¤erent quanti…ers.

9
1.0.4 Reasonings

Direct reasoning

To show that an assertion “P ) Q” is true. We assume that P is true and we show

that then Q is also true.

Exemple 1.11 Let n 2 N. if n is odd, then n2 is odd too.

n is an odd number then there exists a p 2 N : n = 2p + 1. So n2 = (2p + 1)2 =
4p2 + 4p + 1 = 2 (2p2 + 2p) + 1. Thus n2 is odd.

Case-by-case reasoning or disjunction reasoning

If we wish to verify an assertion P (x) for all the x in a set E, we show the assertion
for the x in a part A of E, then for the x not belonging to A.

Exemple 1.12 Let a; b 2] 1; +1[. Prove that ja + bj < 1 + ab.

If a+b < 0, then ja + bj = (a + b). Since a > 1 then a+1 > 0. Similarly b+1 > 0.
Then (1 + a) (1 + b) > 0. Since (1 + a) (1 + b) = 1 + a + b + ab > 0. So (a + b) < 1 + ab.
In the case where a + b 0 we have ja + bj = a + b. Since a < 1 and b < 1. It yield
a 1 < 0 and b 1 < 0. So (a 1) (b 1) > 0. Like (a 1) (b 1) = ab a b + 1 > 0.
Then a + b < 1 + ab. Thus the proposition is proven.

Contraposition reasoning

Reasoning by contraposition is based on the following equivalence : P ) Q , Q ) P .

Exemple 1.13 Let x 2 R. Show that if (x 6= 5 et x 6= 5) ) 2x2 50 6= 0.

We suppose that 2x2 50 = 0, then x2 = 25. So jxj = 5. Thus x = 5 or x = 5.

Reasoning through the absurd

Absurd reasoning to show “P ) Q” is based on the following principle : we assume

both that P is true and that Q is false and we obtain a contradiction.

10
 p
Exemple 1.14 Show that 2 is an irrational number.
p
Assume that 2 is an irrational number, so there exists a and b prime to each other
p 2
with b 6= 0 i.e. (pgcd(a; b)= 1) such 2 = ab . So 2 = ab2 , hence 2b2 = a2 . It is obvious from
the last equation that 2 divides a2 , so a2 is even. Thus a is even therefore there exists k
such that a = 2k and therefore 2b2 = 4k 2 ) b2 = 2k 2 therefore 2 divides b2 , hence b2 is
even thus b is even. We can therefore conclude that pgcd(a; b) = 2. Which contradicts the
p
fact that a and b are relatively prime so 2 is an irrational number.

Reasoning by counterexample

If we want to show that an assertion of the type "8x 2 E : P (x)" eis true then for each
x of E we must show that P (x) is true. On the other hand, to show that this assertion
is false then it is enough to …nd x 2 E such that P (x) is false. (Remember the negation
of "8x 2 E : P (x)" is "9x 2 E : P (x)".) Finding such an x is …nding a counterexample
to the assertion "8x 2 E : P (x)".

Exemple 1.15 Show that for every x 2 R : (x 1)2 > 0.

For x = 1, we have 0 > 0, therefore the proposition is false.

Recurrence

The principle of recurrence makes it possible to show that an assertion P (n), depen-
ding on n, is true for all n 2 N. The proof by induction takes place in three steps : during
initialization we prove P (0).
For the inheritance step, we assume n 0 given with P (n) true, and we then de-
monstrate that the assertion P (n + 1) at the next rank is true. Finally in the conclusion,
we recall that by the principle of recurrence P (n) is true for all n 2 N.

n(n+1)
Exemple 1.16 Show that for all n 2 N : 1 + 2 + ::: + n = 2
.
For n = 1, we have 1 = 1. So P (1) is true.

11
 n(n+1)
Suppose that P (n) = 1 + 2 + ::: + n = 2
is true and we prove P (n + 1) =
(n+1)(n+2)
1 + 2 + ::: + n + (n + 1) = 2
is too.
n(n+1)
Clearly P (n + 1) = 1 + 2 + ::: + n + (n + 1) = P (n) + (n + 1) = 2
+ (n + 1) =
(n+1)(n+2)
2
.
Thus for all n 2 N : P (n) is true.

12
Chapitre 2

Sets-Relations and Applications

Dé…nition 2.1 A set is a collection of objects that satisfy one or more properties. They
are also called elements.

Exemple 2.1 The set of natural numbers N.

Remarque 2.1 A set that does not contain any elements is called an empty set and is
denoted by = fx : x 6= xg.

Remarque 2.2 A set that contains a single element is called a singleton.

p
Exemple 2.2 A = f1g ; B = y 2 R : y = x2 .

Dé…nition 2.2 Let A and B be two sets. We say that A is a subset of B or A is a part
of B, when every element of A is also an element of B. Often we say that A is included
in B, which we denote by A B and we have formally

A B , 8x : x 2 A ) x 2 B:

Exemple 2.3 Consider the following sets A = f2; 3g and B = f1; 2; 3; 4; 5g. Clearly we
have A B.

13
Dé…nition 2.3 Two sets A and B are said to be equal if and only if they contain the
same elements.
A = B , 8x : x 2 A , x 2 B;

or
A = B , (A B) ^ (B A) :

Exemple 2.4 Consider the following sets A = [ 1; 5] and B = fx 2 R : jx 2j 3g.

We have A = B.

Remarque 2.3 The set of all the parts of a set E constitutes a new set denoted P (E).

Exemple 2.5 Consider the following set A = f1; 2; 3g.

We have P(A) = f ; f1g ; f2g ; f3g ; f1; 2g ; f1; 3g ; f2; 3g ; Eg.

Operations on sets

Intersection

Dé…nition 2.4 Let A and B be two parts of a set E. We call the intersection of the sets
A and B the set of elements which belong to both A and B and is denoted A \ B.

A \ B = fx 2 E : (x 2 A) ^ (x 2 B)g ;

or
x 2 A \ B , (x 2 A) ^ (x 2 B) :

Exemple 2.6 Consider the following sets A = f1; 2; 3; 5; 9g and B = f1; 2; 7; 6; 8g. We
have A \ B = f1; 2g.

Remarque 2.4 Two sets are disjoint if their intersection is empty i.e. A and B disjoint
)A\B = .

Exemple 2.7 Consider the following sets A = f1; 2; 3; 5; 9g and B = f7; 6; 8g. We have
A\B = .

14
Union

Dé…nition 2.5 Let A and B be two parts of a set E. We call the union of sets A and
B the set of elements which belong to at least one of the two sets A or B and is denoted
A [ B.
A [ B = fx 2 E : (x 2 A) _ (x 2 B)g ;

or
x 2 A [ B , (x 2 A) _ (x 2 B) :

Exemple 2.8 Resuming example 2.6, we have : A [ B = f1; 2; 3; 5; 6; 7; 8; 9g.

Complementary

Dé…nition 2.6 Let A be a subset of E. We call complement of A in E, the set of elements

of E which do not belong to A and is denoted A or CE A.

A = CE A = fx 2 E : x 2
= Ag :

Exemple 2.9 Resuming example 2.3, we have : CB A = f3; 4; 5g.

Di¤erence

Dé…nition 2.7 Let A and B be two parts of a set E. We call the di¤erence of A and B
in this order, the set of elements of E belonging to A but not to B and is denoted AnB.

AnB = fx 2 E : (x 2 A) ^ (x 2
= B)g :

Exemple 2.10 Resuming example 2.6, we have : AnB = f3; 5; 9g and BnA = f7; 6; 8g.

Symmetric di¤erence

15
Dé…nition 2.8 Let A and B be two parts of a set E. We call the symmetric di¤erence
of A and B the set of elements of E belonging to A only or to B only and is denoted
A B.
A B = fx 2 E : [(x 2 A) ^ (x 2
= B)] _ [(x 2 B) ^ (x 2
= A)]g :

Remarque 2.5 We can also write A B = AnB [ BnA = (A [ B) n (A \ B).

Exemple 2.11 Resuming example 2.6, we have : A B = f3; 5; ; 6; 7; 8; 9g.

Properties of set operations Consider a set E and let A; B and C be three subsets
of E. The following properties are satis…ed.
– Commutativity
A \ B = B \ A and A [ B = B [ A:

– Associativity

A \ (B \ C) = (A \ B) \ C and A [ (B [ C) = (A [ B) [ C:

– Distributivity

A \ (B [ C) = (A \ B) [ (A \ C) and A [ (B \ C) = (A [ B) \ (A [ C) :

– Morgan’s laws
A \ B = A [ B and A [ B = A \ B:

Partition Consider a set E and a family fAi gi=1;n of subsets from E.

Dé…nition 2.9 We say that the fAi gi=1;n constitutes a partition of E if the following
conditions are satis…ed :
1/ For all i 2 f1; 2; :::; ng, we have Ai 6= .
2/ For all i; j 2 f1; 2; :::; ng with i 6= j, we have Ai \ Aj = .
n
3/ [ Ai = E.
i=1

16
Exemple 2.12 Consider the following sets E = fx 2 R : jx 2j 2g ; A = fx 2 R : jx 1j < 1g ;
A = fx 2 R : jx 3j < 1g and C = f0; 2; 4g. It is clear that A; B and C form a partition
of E they satisfy the 3 conditions.

Cartesian produc

Dé…nition 2.10 We call the Cartesian product of the sets fAi gi=1;n , all the elements
n
(a1 ; a2 ; :::; an ), such that ai 2 Ai noted A1 A2 ::: An or Ai .
i=1

n
A1 A2 ::: An = Ai = (a1 ; a2 ; :::; an ) : ai 2 Ai for all i = 1; n :
i=1

Exemple 2.13 Consider the following sets A = f1; 2; 3g and B = f ; g, we have

A B = f(1; ) ; (2; ) ; (3; ) ; (1; ) ; (2; ) ; (3; )g.

2.1 Binary relation

Dé…nition 2.11 A relation from a set E to a set F is a set of pairs of the Cartesian
product E F , whose components are connected by a certain proposition often denoted
R.

Remarque 2.6 In the case where F = E, the relation R is called a binary relation in
E.

Remarque 2.7 The part of the Cartesian product whose elements are related or in agree-
ment is called the graph of R.

Properties of binary relations in a set Consider a set E and R a relation de…ned

in E.

Dé…nition 2.12 The relation R is said to be re‡exive, if 8x 2 E : xRx.

17
Exemple 2.14 De…ne the binary relation R on R2 as follows :
8 (x; y) ; (x0 ; y 0 ) 2 R2 : (x; y) R (x0 ; y 0 ) , x = x0 .
Show that R is re‡exive.
It is clear that 8 (x; y) 2 R2 : (x; y) R (x; y), because x = x. So R is re‡exive.

Dé…nition 2.13 The relation R is said to be symmetric, if 8x; y 2 E : xRy ) yRx.

Exemple 2.15 Returning to example 2.13, we have : (x; y) R (x0 ; y 0 ) , x = x0 , which

we can also write x0 = x , (x0 ; y 0 ) R (x; y). So R is symmetric.

Dé…nition 2.14 The relation R is said to be antisymmetric, if 8x; y 2 E : xRy^yRx )

x = y.

Exemple 2.16 De…ne the binary relation R on R as follows : 8 (x; y 0 ) 2 R2 : xRx0 ,

x x0 .
Assume that xRx0 and x0 Rx we obtain x x0 x. So x = x0 . Thus R is antisymme-
tric.

Dé…nition 2.15 The relation R is said to be transitive, if 8x; y; z 2 E : xRy ^ yRz )

xRz.

Dé…nition 2.16 Returning to Example 2.13, and considering the 3-tuples (x; y) ; (x0 ; y 0 )
and (x00 ; y 00 ) of R2 . Suppose that (x; y) R (x0 ; y 0 ) and (x0 ; y 0 ) R (x00 ; y 00 ) we …nd x = x0 = x00 .
Hence (x; y) R (x00 ; y 00 ). So R is transitive.

Remarque 2.8 Do not confuse a transitive relationship and a circular relationship i.e.8x; y; z 2
E : xRy ^ yRz ) zRx.

Dé…nition 2.17 A relation R on a set E is called an equivalence relation if it is re‡exive,

symmetric and transitive.

Exemple 2.17 Returning to Example 2.13. Since R is re‡exive, symmetric and transi-
tive, so it is an equivalence relation.

18
Dé…nition 2.18 Let R be an equivalence relation on E. We call the equivalence class
:
of x the subset of E of the elements in relation with x and is denoted x

:
x = fy 2 E : xRyg :

:
Exemple 2.18 Returning to Example 2.13. Calculate (x; y)

:
(x; y) = (x0 ; y 0 ) 2 R2 : (x; y) R (x0 ; y 0 )

= (x0 ; y 0 ) 2 R2 : x0 = x; 8y 0 2 R

= fxg R:

Remarque 2.9 Two equivalence classes are either identical or disjoint.

Dé…nition 2.19 The set of all equivalence classes together is called the quotient of E by
R and is denoted E=R.

Remarque 2.10 The set of all equivalence classes of E form a partition of E.

Dé…nition 2.20 A relation R on a set E is called an order relation if it is re‡exive,

antisymmetric and transitive.

Exemple 2.19 Returning to Example 2.15. It is obvious that R is re‡exive because

x=x x ) xRx. R is transitive because if xRy and yRz we automatically have xRz
in e¤ect x y z. From Example 2.15 R is antisymmetric. So it is an order relation.

Dé…nition 2.21 The order relation is said to be of total order if any two elements of
E are comparable i.e. 8x; y 2 E we have xRy or yRx. Otherwise the order is said to be
partial.

Exemple 2.20 Returning to Example 2.18. R is an order relation on R. Consider any

two real numbers x and y, we have either x y or y x. Thus R is a total order
relation.

19
2.2 Applications
Consider two non-empty sets E and F and f a correspondence between the elements
of these two sets i.e. f : E ! F

Dé…nition 2.22 A function is a correspondence which to any element of a starting set

E associates at most one element of an arrival set F .

Dé…nition 2.23 The elements of E are called antecedents but the elements of F are
called direct images or simply images.

Dé…nition 2.24 The domain of de…nition of f is the subset of E containing only the
elements which admit images and is denoted Df .

Dé…nition 2.25 The graph of a function f is denoted f = f(x; y) 2 E F : y = f (x)g.

Dé…nition 2.26 An application is a function which associates with any element of the
starting set E an element of an arrival set F . In other words Df = E.

Dé…nition 2.27 Two maps f and g are equal if they have the same starting set and
same ending set i.e. f; g : E ! F , in addition they must satisfy the following condition :
8x 2 E : f (x) = g (x).

Dé…nition 2.28 Let f : E ! F be a map and A E. We call direct image of A

by f the subset of F constitutes by images of the elements of A by f i.e. f (A) =
ff (x) 2 F : x 2 Ag.

Dé…nition 2.29 Let f : E ! F be a map and B F . We call reciprocal image of B

1
by f the subset of E constitutes by antecedents of the elements of B by f i.e. f (B) =
fx 2 E : f (x) 2 Bg.

20
Some properties of direct and reciprocal images Consider the map f : E ! F
and the following subsets : A; B E and C; D F.
–A B ) f (A) f (B),
– f (A [ B) = f (A) [ f (B),
– f (A \ B) f (A) \ f (B),
1 1
–M N )f (M ) f (N ),
1 1 1
–f (M [ N ) = f (M ) [ f (N ),
1 1 1
–f (M \ N ) = f (M ) \ f (N ).

Application composition Consider the applications f : E ! F and g : F ! K

Dé…nition 2.30 We call composed of applications f and g, the application constructed

f g
of applications f and g de…ned as follows g f : E ! F ! K where (g f ) (x) = g (f (x)).

Remarque 2.11 Note that in general (g f ) (x) 6= (f g) (x).

Consider the application f : E ! F .

Dé…nition 2.31 f is said to be injective if every element y of F has at most one ante-
cedent in E i.e.
8x1 ; x2 2 E : f (x1 ) = f (x2 ) ) x1 = x2 ;

or
8x1 ; x2 2 E : x1 6= x2 ) f (x1 ) 6= f (x2 ) :

Dé…nition 2.32 f is said to be surjective if every element y of F has at least one

antecedent in E i.e.
8y 2 F; 9x 2 E : y = f (x) :

Dé…nition 2.33 f is said to be bijective if and only if it is both surjective and injective
i.e.
8y 2 F; 9!x 2 E : y = f (x) :

21
Dé…nition 2.34 If f realizes a bijection of E into F , then there exists a unique de…ned
bijection of F into E which associated with the image its antecedent the latter is called
1
reciprocal or inverse map and is denoted f .

Remarque 2.12 If f : E ! F is bijective and there exists a map g : F ! E satisfying

1
f g = IdF and g f = IdE , then g = f where IdK is the identity application on the
set K checking K ( ) = for all 2 K.

1 1 1
Remarque 2.13 Let f g be a bijection map, then we have (f g) (x) = (g f ) (x).

Remarque 2.14 Do not confuse reciprocal image and reciprocal application.

22
Chapitre 3

Algebraic structures

3.1 General notions

Consider a non-empty set G.

Dé…nition 3.1 We call the law of internal composition any application :G G!G
which associates with any pair of elements (x; y) of G G the element x y of G. In other
words the composite of two elements of G remains in G and we write

8x; y 2 G; x y 2 G.

We also say that the law is stable in G.

In the rest of the chapter we assume that and are two internal composition laws
on the non-empty set G.

Dé…nition 3.2 is called commutative, if and only if :

8x; y 2 G; x y = y x.

23
Dé…nition 3.3 is called associative, if and only if :

8x; y; z 2 G; x (y z) = (x y) z.

Dé…nition 3.4 is said to be distributive to the left (resp. to the right) with respect to
in G, if and only if :

8x; y; z 2 G; x (y z) = (x y) (x z) ,

respectively
8x; y; z 2 G; (y z) x = (y x) (z x) .

If is distributive to the left and right with respect to on G, we say that it is distributive.

Dé…nition 3.5 e is said to be a neutral element on the left (resp. on the right) with
respect to in G, if and only if :

9e 2 G; 8x 2 G : e x = x;

respectively
9e 2 G; 8x 2 G : x e = x:

e is a neutral element if it is both a left and right neutral element.

Dé…nition 3.6 x0 is said to be a left (resp. right) symmetric element of x with respect to
in G, if and only if :
8x 2 G; 9x0 2 G : x0 x = e;

respectively
9e 2 G; 8x 2 G; x x0 = e;

where e is a neutral element with respect to in G. If x0 is both a left and right symmetric
element then we simply say that x0 is the symmetric element of x.

24
Remarque 3.1 The symmetrical element is commonly said to be the inverse of x and
we note it x 1 .

3.2 Group
Dé…nition 3.7 We call a group any set G =
6 provided with an internal composition law
satisfying :
– is an associative law.
– admits a neutral element.
1
– Every element x 2 G admits a symmetric element (an inverse) x 2 G.

Dé…nition 3.8 We say that (G; ) is a commutative or abelian group, if (G; ) is a group,
moreover is commutative.

Remarque 3.2 In certain books we …nd the following names :

– Magma : any set G =
6 provided with an internal composition law .
– Monoid : any set G =
6 provided with an internal composition law is associative.
– Commutative monoid : any set G =
6 provided with an internal composition law
is associative and commutative.

3.2.1 Subgroup

Consider the group (G; ) and H a non-empty part of G.

Dé…nition 3.9 We say that 6= H G is a subgroup of G, if (H; ) is a group for the

law restricted to H and we note (H; ) < (G; ).

Proposition 3.1 Let (G; ) be a8group of which e is the neutral element and H G,
>
> H= 6 i.e. e 2 H
>
<
(G; ) is a Subgroup of (G; ) , 8x; y 2 H : x y 2 H
>
>
>
: 8x 2 H : x 1 2 H

25
 8
< 8x; y 2 H : x y 2 H
Remarque 3.3 The following 2 conditions : , can be replaced
: 8x 2 H : x 1 2 H
by the following equivalent condition : 8x; y 2 H : x y 1 2 H where y 1 is the symmetric
element of y in H.

Remarque 3.4 The trivial subgroups of G are G and feg.

Dé…nition 3.10 Let (G; ) be a group and H G a subset of G. The subgroup generated
by H is the smallest subgroup of G containing H.

3.3 Group morphisms

Dé…nition 3.11 Let (G; ) and (H; >) be two groups. A map f : (G; ) ! (H; >) is
called a group morphism if :

8x; y 2 G : f (x y) = f (x) >f (y) :

Proposition 3.2 Let f : (G; ) ! (H; >) be a group morphism, we have

– f (eG ) = eH .
– 8x 2 G : f (x 1 ) = (f (x)) 1 .

Dé…nition 3.12 Let f : (G; ) ! (H; >) be a group morphism, if f is bijective, then f
is called isomorphism.

3.3.1 Kernel and image

Let f : (G; ) ! (H; >) be a group morphism.

Dé…nition 3.13 We call the kernel of f the subset of G, denoted ker f = fx 2 G : f (x) = eH g.

Dé…nition 3.14 We call the image of f the subset of H, denoted Im f = ff (x) 2 H : x 2 Gg.

26
Proposition 3.3 Let f : (G; ) ! (H; >) be a group morphism, then
– (ker f; ) is a subgroup of (G; ).
– (H; >) is a subgroup of (H; >).
– The map f is injective if and only if ker f = feG g.
– The map f is surjective if and only if Im f = H.

3.4 Rings
Consider a set A equipped with two internal composition laws and >.

Dé…nition 3.15 We say that (A; ; >) is a ring if

– (A; ) is a commutative group.
– > is associative.
– > is distributive with respect to .

Dé…nition 3.16 (A; ; >) is called a commutative ring if (A; ; >) is a ring, additionally
> is commutative.

Dé…nition 3.17 (A; ; >) is called a unitary ring i (A; ; >) is a ring, additionally >
admits a neutral element.

3.4.1 Subrings

Dé…nition 3.18 Let (A; ; >) be a ring and 6= H A. (H; ; >) is called a subring,
if (H; ; >) is itself a ring.

Dé…nition 3.19 Let (A; ; >) be a ring and 6= H A. (H; ; >) is called a subring,
if (H; ) < (A; ) and 8x; y 2 H, x>y 2 H.

27
3.4.2 Ring without zero divisor

Let (A; +; ) be a ring such that 0 is the neutral element of the law + and 1 the
neutral element of the law , and let a 2 A such that a 6= 0.

Dé…nition 3.20 a is said to be a divisor from zero to the left in A if there exists x 2
A : x 6= 0 et a x = 0.

Dé…nition 3.21 a is said to be a divisor from zero to the right in A if there exists
x 2 A : x 6= 0 et x a = 0.

Dé…nition 3.22 a is said to be a divisor of zero in A if it is a divisor of zero on the left

and right simultaneously.

Dé…nition 3.23 A ring (A; +; ) is said to be ring without zero divisor, if it does not
admit divisors of zero.

3.4.3 Homomorphism-Isomorphism of rings

Let (A; ; >) and (B; r; ?) be two rings and f : A ! B

Dé…nition 3.24 We say that f is a ring homomorphism, if it satis…es :

– 8x; y 2 A; f (x y) = f (x) rf (y).
– 8x; y 2 A; f (x>y) = f (x) ?f (y).

Dé…nition 3.25 We say that f is a ring isomorphism, if f is a bijective homomorphism.

Dé…nition 3.26 We say that f is a ring endomorphism, if f is a homomorphism and

A = B.

Dé…nition 3.27 We say that f is a ring automorphism, if f is a bijective endomorphism.

28
3.4.4 Ideals

Let (A; ; >) be a ring and I A.

Dé…nition 3.28 We say that I is an ideal to the left of A, if

– (I; ) is a subgroup of (A; ).
– 8x 2 A; 8y 2 I, y>x 2 I.

Dé…nition 3.29 We say that I is an ideal to the right of A, if

– (I; ) is a subgroup of (A; ).
– 8x 2 A; 8y 2 I, x>y 2 I.

Dé…nition 3.30 We say that I is a two-sided ideal, if it is an ideal to the left and right
of A at the same time.

Remarque 3.5 If (A; ; >) is a commutative ring, then every ideal is two-sided.

3.5 Field
Dé…nition 3.31 (A; ; >) is called a …eld, if
– (A; ) is a commutative group.
– (A feg ; >) is a group.
– > is distributive with respect to .

De…nition 3.30 is equivalent to the following de…nition

Dé…nition 3.32 (A; ; >) is called a …eld, if

– (A; ; >) is a unit ring.
– All elements of A feg admits an symmetric where e is the neutral element of the
law .

Dé…nition 3.33 (A; ; >) is called a commutative …eld, if (A; ; >) has a …eld structure
and > is commutative.

Proposition 3.4 Every …eld (A; ; >) is a ring without zero divisor.

29
Chapitre 4

Concept of polynomial with an

indeterminate coe¢ cient in a ring

Let K be a …eld (K =Q or K =R or K =C).

Dé…nition 4.1 A polynomial with coe¢ cients in K is an expression of the form :

P (X) = an X n + Xn 1 X n 1
+ ::: + a1 X + a0 ;

where n 2 N and fai gi=1;2;:::;n 2 K is called coe¢ cients of the polynomial.

Remarque 4.1 The set of polynomials on the …eld K is denoted K [X].

Dé…nition 4.2 Let 0 6= P (X) 2 K [X]. We call the degree of P (X) the largest integer
n such that an 6= 0, we denote it deg(P ), and the element adeg(P ) is called the dominant
coe¢ cient of P .

Remarque 4.2 The degree of the zero polynomial adeg(P =0) = 1 by convention.

Dé…nition 4.3 Let 0 6= P (X) 2 K [X]. We say that P is unitary (normalized) if and
only adeg(P ) = 1.

Dé…nition 4.4 A one-indeterminate polynomial with coe¢ cients in K [X] whose coe¢ -
cients are all zero from a certain rank.

30
4.1 Operations on K [X]
P
n
Consider the two polynomials P (X) = an X n + Xn 1 X n 1
+ ::: + a1 X + a0 = ai X i
i=0
and
P
n
Q (X) = bn X n + bn 1 X n 1
+ ::: + b1 X + b0 = bj X j .
l=0
We de…ne addition, product of polynomials and multiplication by a scalar 2 K as
follows :
P
n
– (P + Q) (X) = ci X i where ci = ai + bi .
i=0
P
2n P
n
– (P Q) (X) = vk X k where vk = ak b n k .
k=0 k=0
P
n
– ( P ) (X) = ci X i .
i=0
– P (X) = Q (X) , 8i 2 N; ai = bi .

Dé…nition 4.5 The addition and multiplication de…ned above de…ne internal composi-
tion laws on the set of polynomials with an indeterminate coe¢ cient in K.

Dé…nition 4.6 The set of polynomials with an indeterminate coe¢ cient in K provided
with addition and multiplication de…ned a commutative ring structure which we denote
K [X].

4.2 Arithmetic of polynomials

Dé…nition 4.7 Let P and Q be two polynomials of K [X], We say that the polynomial
P is divisible by the polynomial Q if there exists a polynomial A such that P = QA and
we write QnP and we say that P is multiple of Q (where Q is a divisor of P ).

Proposition 4.1 Let P; Q; R 2 K [X] we have :

– P nQ and QnP ) 9 2 K : P = Q.
– P nQ and QnR ) P nR.
– P nQ and P nR ) P n ( Q + R) where ; 2 K.
– P nP; 1nP and P n0.

31
4.2.1 Euclidean division in K [X]

Let P and Q be two polynomials of K [X] and Q 6= 0, then there exists a unique pair
(D; R) in K [X] K [X] :

P = DQ + R with 0 deg(R) < deg(Q).

Greatest common divisor (gcd)

Dé…nition 4.8 Let P; Q 2 K [X] with P 6= 0 and Q 6= 0. There is a unique unit poly-
nomial that divides both P and Q. This polynomial is called the greatest common divisor
and is denoted gcd (P; Q).

Proposition 4.2 Let P; Q 2 K [X] with P 6= 0 and Q 6= 0. Then

– AnP and AnQ ) An gcd (P; Q).
– gcd ( P; Q) = gcd (P; Q).

Dé…nition 4.9 Let P; Q 2 K [X]. We say that P and Q are coprime if is only if
gcd (P; Q) = 1.

Théorème 4.1 (Bézout’s theorem) Let P; Q 2 K [X] be polynomials with P 6= 0 and

Q 6= 0, and let D = gcd (P; Q). There are two polynomials '; 2 K [X] : 'P + Q = D.

Root of a polynomial-factorization

Dé…nition 4.10 Let P 2 K [X] and 2 K. We say that is a root of P if P ( ) = 0.

Théorème 4.2 (d’Alembert-Gauss theorem) Any polynomial with complex coe¢ -

cients of degree m 1, admits m root including their multiplicities, at least one of which
is in C.

Proposition 4.3 P ( ) = 0 , (x ) nP .

32
Dé…nition 4.11 Let m 2 N . We say that is a root of multiplicity m of P if (X )m nP
while (X )m+1 does not divide P .

Remarque 4.3 When m = 1, is called a simple root. If m > 1, is called a root of

order m.

Proposition 4.4 Let P 2 K [X] and 2 K such that is a root of order m 2 N f1g,
the following assertions are equivalent
– 9Q 2 K [X] : P = (X )m Q with Q ( ) 6= 0.
– P ( ) = 0; P 0 ( ) = 0; :::; P (m 1)
( ) = 0 and P (m) ( ) 6= 0 where P (i) is the deriva-
tive of order i of P .

4.3 Concept of rational fraction with an indetermi-

nate
We denote by K [X] the set of non-zero polynomials i.e. K [X] = K [X] n 0K[X]
and we consider on K [X] K [X] the equivalence relation R de…ned as follows :

8 (P; Q) ; (A; B) 2 K [X] K [X] ; (P; Q) R (A; B) , P B=Q A:

Dé…nition 4.12 We call the rational fraction on K the equivalence class of (P; Q) 2
P
K [X] K [X] and is denoted P=Q or Q
i.e.

P
= f(A; B) 2 K [X] K [X] : P B=Q Ag :
Q

A
Remarque 4.4 We note by K (X) = K [X] K [X] =R = B
: (A; B) 2 K [X] K [X] .

Dé…nition 4.13 We call irreducible form of a non-zero rational fraction P of K (X)

any couple (A; B) 2 K [X] K [X] : gcd (A; B) = 1K[X] .

33
4.3.1 Operations on K (X)

The set K (X) endowed with the following two laws of internal composition
P A P A P B+Q A P A P A
8Q ; B 2 K (X) ; Q + B
= Q B
and Q B
= Q B
has a commutative …eld
structure.

Canonical injection of K [X] into K (X)

Consider the map J : K [X] ! K (X) which associates with each polynomial P of
P
K [X] the rational fraction 1K[X]
. We can easily prove that J is injective. So we can
identify the elements of K [X] with the elements of K (X) and we have K [X] K (X).

Remarque 4.5 J is called canonical injection.

Roots and poles of a rational fraction

P
Dé…nition 4.14 Consider the irreducible rational fraction F = Q 2 K (X) .
– The roots of F are the zeros of P in K [X].
– The order of multiplicity of the root of F is the same when considering it as the
root of P in K [X].
– The poles of F are the zeros of Q in K [X].
– The order of multiplicity of the pole of F is the same when considering it as the
root of Q in K [X].

P
Dé…nition 4.15 Consider the rational fraction F = Q 2 K (X). We call an associated
function to F any function Fe : K ! K de…ned for all x di¤erent from the poles of F i.e.
Pe(x)
the application Fe (x) = e
Q(x)
.

4.3.2 Decomposition of a rational fraction

P
Consider the irreducible rational fraction F = Q 2 K (X). By means of the Euclidean
division in K [X] we have the existence and the uniqueness of two polynomials D and R

34
of K [X] :
P =D Q + R with deg(R) < deg(Q);

and by injection into the …eld K (X) of rational fractions, we get

P D R
= + :
Q 1K[X] Q

P
Remarque 4.6 D is called an integer part of the rational fraction Q
and is worth zero
if deg(P ) < deg(Q).

Decomposition into simple elements on K

P D R R
Lemme 4.1 Consider the rational fraction F = Q = 1K[X]
+ Q
where Q
is irreducible
and deg(R) < deg(Q), let us also assume that Q can be decomposed into prime factors of
K [X] i.e. Q = Qn1 1 Qn2 2 ::: Qknk . Then there exist k polynomials L1 ; L2 ; :::; Lk 2 K [X] :

R L1 L2 Lk
= n1 + n2 + ::: + nk with deg(Li ) < deg(Qi ) for i = 1; 2; :::; k:
Q Q1 Q2 Qk

This decomposition is unique.

Lemme 4.2 Consider the irreducible rational fraction F = QLn et deg(L) < deg(Qn ).
Then there exist n polynomials S1 ; S2 ; :::; Sn 2 K [X] :

L S1 S2 Sn
n
= + 2 + ::: + n with deg(Si ) < deg(Q) for i = 1; 2; :::; n:
Q Q Q Q

This decomposition is unique.

Remarque 4.7 In the general framework, we can combine the two previous lemmas when
decomposing any rational fraction if necessary.

S1 S2 Sn
Remarque 4.8 The part Q
+ Q2
+ ::: + Qn
is called the relative part of the polynomial
L.

35
Remarque 4.9 In the case where Q = X the partial sum is called the polar part
relative to .

Remarque 4.10 In the case where Q = X , we speak of the decomposition into

simple elements of the …rst kind. On the other hand if Q = aX 2 + bX + c we speak of
decomposition into simple elements of the second kind.

36