UNIVERSITÉ SIDI MOHAMED BEN ABDELLAH

Faculté des Sciences Dhar El Mahraz Année Universitaire : 2024-2025

F è s Filières (Semestre) : MIP & IA (S1)
Département de Mathématiques Module : Algèbre 1

Série de TD n◦1

Exercice 1. Soient E et F deux ensembles non vides et P (x, y) un prédicat tel que x ∈ E et
y ∈ F . Donner la négation de l’assertion suivante :

∀x ∈ E, ∃!y ∈ F, P (x, y).

Solution. On a :

∀x ∈ E, ∃!y ∈ F, P (x, y),

≡ ∀x ∈ E, [(∃ y ∈ F, P (x, y)) et (∀(y, y ′ ) ∈ F 2 , (P (x, y) et P (x, y ′ )) =⇒ y = y ′ )],
≡ ∃x ∈ E, [(∀ y ∈ F, P (x, y)) ou (∃(y, y ′ ) ∈ F 2 , (P (x, y) et P (x, y ′ )) et y ̸= y ′ )],
≡ [∃x ∈ E, (∀ y ∈ F, P (x, y))] ou [∃x ∈ E, ∃(y, y ′ ) ∈ F 2 , (P (x, y) et P (x, y ′ )) et y = ̸ y ′ ].

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 2.
1) Soient P et Q deux assertions. Montrer, par la table de vérité, que le fait de dire que
P ⇐⇒ Q est équivalent à dire que P et Q ont la même valeur de vérité.
2) Énoncer le principe de raisonnement par contraposée et le redémontrer par un raisonnement
directe et aussi par la table de vérité.
3) Soient P , Q et R trois assertions. Montrer par un raisonnement directe qu’on a :

[(P ou Q) ⇒ R] ⇔ [(P ⇒ R) et (Q ⇒ R)].

Solution.
1) On a :
P Q P =⇒ Q Q =⇒ P P ⇐⇒ Q
0 1 1 0 0
1 0 0 1 0
1 1 1 1 1
0 0 1 1 1
Alors, on tire que P et Q sont équivalent si et seulement si elle ont la même valeur de vérité.
2) On a :
⋆ Le principe de raisonnement par contraposée s’énonce comme suit :

www.youtube.com/@Departement_de_Mathematiques Page 1/4

 Théorème (Principe de contraposition). Soient P et Q deux assertions. Alors,
P =⇒ Q ≡ Q =⇒ P .
Autrement dit, les assertions P =⇒ Q et Q =⇒ P sont équivalentes.
⋆ On a

Q =⇒ P ≡ Q ou P (par la définition de l’implication),

≡ Q ou P (car Q ≡ Q),
≡ P ou Q (par la commutativité de la disjonction),
≡ P =⇒ Q (par définition).
D’où Q =⇒ P ≡ P =⇒ Q. Ce qui est une démonstration directe du principe de raison-
nement par contraposée. .
⋆ On démontre le principe de raisonnement par contraposée, en utilisant la table de vérité,
comme suit :
P Q P Q P =⇒ Q Q =⇒ P
0 1 1 0 1 1
1 0 0 1 0 0
1 1 0 0 1 1
0 0 1 1 1 1
Donc les assertions P =⇒ Q et Q =⇒ P ont toujours la même valeur de vérité. Donc
elle sont équivalentes.
3) On a :
(P ou Q) ⇒ R ⇐⇒ (P ou Q) ou R,
⇐⇒ (P et Q) ou R,
⇐⇒ (P ou R) et (Q ou R),
⇐⇒ (P ⇒ R) et (Q ⇒ R).

D’où [(P ou Q) ⇒ R] ⇐⇒ [(P ⇒ R) et (Q ⇒ R)].

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 3. Soient a, b ∈ R. Montrer que (∀ε > 0, |a − b| < ε) ⇒ a = b.
Solution. Supposons que a ̸= b. Alors |a − b| > 0. Donc, ∃ε > 0, |a − b| ≥ ε (prenez par
exemple ε = |a−b|
2
). Donc, on vient de démontrer que
a ̸= b =⇒ (∃ε > 0, |a − b| ≥ ε).
Alors, par contraposée, on a :
(∀ε > 0, |a − b| < ε) ⇒ a = b.

www.youtube.com/@Departement_de_Mathematiques Page 2/4

 ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

Exercice 4.
1) Soit n ∈ N. Montrer que 9 divise 4n + 6n − 1.
2) Montrer par récurrence forte que tout entier supérieur à 2 admet un diviseur premier.

Solution.
1) Pour n = 0, on a 4n + 6n − 1 = 0. Donc 9 divise 4n + 6n − 1 dans ce cas.
Supposons que 9 divise 4n + 6n − 1 pour un certain entier naturel n fixé (C’est ce qu’on
appelle l’hypothèse de récurrence). Montrer que 9 divise 4n+1 + 6(n + 1) − 1. Puisque, par
hypothèse de récurrence, 9 divise 4n + 6n − 1, alors 4n + 6n − 1 = 9k, pour un certain entier
k. Donc en multipliant par 4 on obtient 4n+1 + 6 × 4 × n − 4 = 9k. Alors 4n+1 + 6 × 4 × n − 4 =
4n+1 + 6 × n + 6 × 3 × n − 4 = 9 × 4k. Par suite, 4n+1 + 6 × n = 9 × 4k + 6 × 3 × n + 4. Donc,
4n+1 + 6 × n − 1 = 9 × 4k + 6 × 3 × n + 3 et alors 4n+1 + 6 × n + 6 − 1 = 9 × 4k + 6 × 3 × n + 9.
Finalement, 4n+1 + 6(n + 1) − 1 = 9(4k + 2 × n + 1) et 9 divise 4n+1 + 6(n + 1) − 1.
Il s’ensuit, par récurrence, que pour tout entier naturel n, 9 divise 4n + 6n − 1.
2) Soit n un entier naturel supérieur à 2. Si n = 2, alors n est divisible par 2 qui est un nombre
premier. Donc, le résultat est vrai dans ce cas.
Soit n un entier naturel fixé. Supposons que le résultat est vraie pour tout entier naturel k
tel que 2 ≤ k ≤ n, c’est-à-dire, tout entier naturel k, tel que 2 ≤ k < n, admet un diviseur
premier (C’est ce qu’on appelle l’hypothèse de récurrence forte). Montrons que le résultat
est vrai pour n + 1. On distingue deux cas :
⋆ Si n + 1 est un nombre premier, alors dans ce cas il est divisible par lui même, qui est un
nombre premier, donc dans ce cas le résultat est vrai pour n + 1.
⋆ Si n + 1 est n’est pas un nombre premier, alors il admet un diviseur d tel que d ̸= 1 et
d ̸= n + 1. Donc, 1 < d < n + 1 (c’est-à-dire, 2 ≤ d ≤ n). Alors, par hypothèse de récurrence
forte, d admet un diviseur premier qu’on va noter p. Puisque p divise d et d divise n + 1,
alors p divise n + 1. Donc, dans ce cas aussi le résultat est vrai pour n + 1.
Il s’ensuit, par récurrence forte, que tout entier supérieur à 2 admet un diviseur premier.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

Exercice 5. Soient A, B et C trois sous-ensembles d’un ensemble non vide E. Montrer que :
1) A ∪ B = A ∩ C ⇐⇒ B ⊆ A ⊆ C.
2) A∆B = A ∩ B ⇐⇒ A = B = ∅.
3) A∆B = ∅ ⇐⇒ A = B.

Solution.
1) On a :
⇐= Supposons que B ⊆ A ⊆ C. Alors, A ∪ B = A et A ∩ C = A. Par suite, A ∪ B = A ∩ C.
=⇒ Supposons que A ∪ B = A ∩ C. On a B ⊆ A ∪ B = A ∩ C ⊆ A. Donc, B ⊆ A. De
même, A ⊆ A ∪ B = A ∩ C ⊆ C. Alors, A ⊆ C. Par suite, B ⊆ A ⊆ C.

www.youtube.com/@Departement_de_Mathematiques Page 3/4

2) On a :

A∆B = A ∩ B ⇐⇒ = (A ∪ B) ∩ (A ∩ B) = A ∩ B,
= (A ∪ B) ∩ (A ∩ B) = A ∩ B = ∅ (sinon A ∩ B ̸⊂ (A ∩ B)),
= (A ∪ B) ∩ E (car (A ∩ B) = ∅ = E),
= A ∪ B = ∅,
= A = ∅ et B = ∅.

3) On a :

A∆B = ∅ ⇐⇒ = (A\B) ∪ (B\A) = ∅,

= (A\B) = ∅ et (B\A) = ∅,
= (A ⊂ B) et (B ⊂ A),
= A = B.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

Exercice 6. Soient E, F et G des ensembles non vides. Soient f : E → F et g : F → G des

applications. Montrer que :
1) Si g ◦ f est injective, alors f est injective.
2) Si g ◦ f est surjective, alors g est surjective.
3) Si g ◦ f est bijective, alors f est injective et g est surjective.

Solution.
1) Supposons que g ◦ f est injective. Soient x et y ∈ E tels que f (x) = f (y). Donc g ◦ f (x) =
g ◦ f (y). Puisque g ◦ f est injective, alors x = y. D’où l’injectivité de f .
2) Supposons que g ◦ f est surjective. Soit z ∈ G. Puisque g ◦ f est surjective, alors ∃x ∈ E
tel que g ◦ f (x) = y. Posons x′ = f (x). On a x′ ∈ F et g(x′ ) = g(f (x)) = y. Donc, g est
surjective.
3) Supposons que g ◦ f est bijective, alors elle est injective et surjective. Donc d’après 1) f est
injective et d’après 2) g est surjective.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

Exercice 7. Soient A et B deux parties d’un ensemble non vide E. Considérons l’application
suivante :
f : P(E) −→ P(A) × P(B)
X 7−→ (X ∩ A, X ∩ B).
1) Montrer que f est injective si et seulement si A ∪ B = E.
2) Montrer que f est injective si et seulement si A ∩ B = ∅.

www.youtube.com/@Departement_de_Mathematiques Page 4/4

Solution.
1) Montrons la première équivalence.
⋆ Supposons que f est injective. Montrons que A ∪ B = E. Supposons par l’absurde que
A ∪ B ̸= E. Donc, A ∪ B ⊊ E (car on a toujours A ∪ B ⊆ E). Alors, il existe x ∈ E tel que
x ̸∈ A∪B. Posons X = {x}. Comme x n’appartient ni à A ni à B, alors A∩X = X ∩B = ∅.
D’où f (X) = (∅, ∅) = f (∅). Donc, du fait que f est injective, on a X = ∅, ce qui est
absurde. Donc, A ∪ B = E.
⋆ Supposons que A ∪ B = E. Montrons que f est injective. Soient X et Y deux partie E
tels que f (X) = f (Y ). Alors (X ∩ A, X ∩ B) = (Y ∩ A, Y ∩ B). Alors, X ∩ A = Y ∩ A
et X ∩ B = Y ∩ B, et donc, on a (X ∩ A) ∪ (X ∩ B) = (Y ∩ A) ∪ (Y ∩ B). Puisque
(X ∩ A) ∪ (X ∩ B) = X ∩ (A ∪ B) = X ∩ E = X et (Y ∩ A) ∪ (Y ∩ B) = Y ∩ (A ∪ B) =
Y ∩ E = Y , alors X = Y . Par suite, f est injective.
2) Montrons la deuxième équivalence.
⋆ Supposons que f est surjective et montrons que A∩B = ∅. Puisque (∅, B) ∈ P(A)×P(B),
alors il existe X ⊂ E tel que f (X) = (∅, B). Alors, (X ∩ A, X ∩ B) = (∅, B) et donc
X ∩ A = ∅ et X ∩ B = B. En particulier, on a B ⊆ X. Par suite, A ∩ B ⊆ A ∩ X = ∅.
D’où A ∩ B = ∅.
⋆ Inversement, supposons que A ∩ B = ∅. Montrons que f est surjective. Soit (X, Y ) ∈
P(A) × P(B). Remarquer que X ∩ B = Y ∩ A = ∅, car X ⊆ A et Y ⊆ B. On a :

f (X ∪ Y ) = ((X ∪ Y ) ∩ A, (X ∪ Y ) ∩ B),
= ((X ∩ A) ∪ (Y ∩ A), (X ∩ B) ∪ (Y ∩ B)),
= ((X ∩ A) ∪ ∅, ∅ ∪ (Y ∩ B)),
= (X ∩ A, Y ∩ B) = (X, Y ).

D’où f est surjective.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 8. Dans R2 , on considère la relation R définie par :

(a, b)R(c, d) ⇔ a2 + b2 = c2 + d2 .

1) Montrer que R est une relation d’équivalence.

2) Décrire la classe d’équivalence de (a, b).
3) On désigne par R2 /R l’ensemble quotient modulo R. Montrer que l’application

f : R2 /R −→ [0, +∞[
(a, b) 7−→ a2 + b2
est bien définie et qu’elle est bijective.
Solution.
1) ⋆ La relation R est réflexive, en fait on a pour tout (a, b) ∈ R2 , on a a2 + b2 = a2 + b2 . Donc,
(a, b)R(a, b).

www.youtube.com/@Departement_de_Mathematiques Page 5/4

 ⋆ Soient maintenant (a, b), (c, d) ∈ R2 tels que (a, b)R(c, d). Alors a2 + b2 = c2 + d2 , ceci
donne aussi c2 + d2 = a2 + b2 . Donc, (c, d)R(a, b) et par suite R est symétrique.
⋆ Montrons maintenant que R transitive. Soient (a, b), (c, d) et (e, f ) ∈ R2 tels que (a, b)R(c, d)
et (c, d)R(e, f ). Donc, a2 + b2 = c2 + d2 et c2 + d2 = e2 + f 2 . Alors a2 + b2 = e2 + f 2 et
donc (a, b)R(e, f ). Par suite, R est transitive.
Finalement R est une relation d’équivalence.
2) On a (a, b) = {(c, d) ∈ R2 : (a, b)R(c, d)} = {(c, d) ∈ R2 : a2 + b2 = c2 + d2 }.
3) Soit (c, d) ∈ R2 un autre représentant de la classe (a, b). Donc a2 + b2 = c2 + d2 . Alors
f ((a, b)) = f ((c, d)). Ainsi l’application f est bien définie.
Montrons que l’application est injective. Soient (a, b), (c, d) ∈ R2 tels que f ((a, b)) =
f ((c, d)). Donc, a2 + b2 = c2 + d2 . Alors (a, b)R(c, d). Donc (a, b) = (c, d). D’où l’injec-
tivité de f .
q 2 q 2
Montrons la surjectivité de f . Soit α ∈ [0, +∞[. On a α = 12 α + 12 α = f (( 12 α, 12 α)).
Donc f est surjective.
Il s’ensuit que f est bijective.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 9. Soit E un ensemble non vide. On considère la relation définie sur P(E) par

∀A, B ∈ P(E), ARB ⇐⇒ A = B ou A = B.

avec B désigne le complémentaire de B dans E. Montrer que R est est une relation d’équiva-
lence.
Solution. Il suffit de vérifier que R est réflexive, symétrique et transitive. On a :
⋆ Pour toute partie non vide A de E, on a A = A, donc ARA et alors R est réflexive.
⋆ Soient A et B deux parties non vides E telles que ARB. On a deux cas, ou bien A = B et
dans ce cas BRA, ou bien A = B et dans ce cas on a B = A, donc on a aussi BRA. Par
suite, R est symétrique.
⋆ Soient maintenant A, B et C trois parties non vides E telles que ARB et BRC. On distingue
quatre cas :
1) Si A = B et B = C, alors A = C.
2) Si A = B et B = C, alors A = C.
3) Si A = B et B = C, alors A = C.
4) Si A = B et B = C, alors A = C.
Donc dans tous les cas on a ARC et alors la relation R est transitive.
Par suite, R est une relation d’équivalence.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 10.

www.youtube.com/@Departement_de_Mathematiques Page 6/4

1) Soit n un entier relatif. Montrer que 2n + 1 et 9n + 4 sont premiers entre eux.
2) Trouver tous les entiers relatifs x et y tels que 5(x − 1) = 7y.
3) Soit m un entier relatif impair. Montrer que m + 2 et m − 2 sont premiers entre eux.

Solution.
1) On a :
9(2n + 1) − 2(9n + 4) = 18n + 9 − 18n − 8 = 1.
Par suite, (2n + 1)x + (9n + 4)y = 1, avec x = 9 et y = −2. Donc, par le théorème de Bézout,
2n + 1 et 9n + 4 sont premiers entre eux.
2) Soient x et y deux entiers relatifs tels que 5(x − 1) = 7y. Alors, 5 divise 7y. Comme 5 et 7
sont premiers entre eux, alors par le théorème de Gauss, 5 divise y. On a alors, y = 5k, où
k est un entier relatif. En replaçant dans l’égalité 5(x − 1) = 7y, on a :

5(x − 1) = 7 × 5k ⇐⇒ x − 1 = 7k ⇐⇒ x = 7k + 1.

Par suite, x = 7k + 1 et y = 5k, avec k ∈ Z.

3) On a m + 2 = (m − 2) + 4. Donc, pgcd(m + 2, m − 2) = pgcd(m − 2, 4) = 1, car m − 2 est
impair (et 4 = 22 ).

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

Exercice 11. Soit n un entier relatif.

1) Montrer que pgcd(5n3 − n, n + 2) = pgcd(n + 2, 38).
2) Déterminer toutes les valeurs possibles de pgcd(5n3 − n, n + 2).
3) Déterminer les entiers n ∈ Z vérifiant pgcd(5n3 − n, n + 2) = 19.

Solution.
1) Soit n un entier relatif. Montrer que pgcd(5n3 − n, n + 2) = pgcd(n + 2, 38).
En effectuant la division euclidienne de 5n3 − n par n + 2, on obtient

5n3 − n n + 2
−5n3 − 10n2 5n2 − 10n + 19
−10n2 − n
10n2 + 20n
19n
−19n − 38
−38
Donc, 5n3 − n = (n + 2)(5n2 − 10n + 19) − 38. Par suite, −(5n3 − n) = (n + 2)(−5n2 + 10n −
19) + 38 et alors pgcd(5n3 − n, n + 2) = pgcd(n + 2, 38).
2) Soit d = pgcd(5n3 − n, n + 2). D’après 1) on a d = pgcd(n + 2, 38). Donc, d|38 et alors
d ∈ {1, 2, 19, 18}.

www.youtube.com/@Departement_de_Mathematiques Page 7/4

3) Soit n ∈ Z. On a :

pgcd(5n3 − n, n + 2) = 19,
⇐⇒ pgcd(n + 2, 38) = 19 d’apès 1),
n+2
⇐⇒ 19 divise n + 2 et est impair, car sinon on aura pgcd(n + 2, 38) = 38,
19
n+2
⇐⇒ ∃k ∈ Z, tel que n + 2 = 19k et est impair,
19
⇐⇒ ∃k ∈ Z, tel que n + 2 = 19(2h + 1), pour un certain h ∈ Z,
⇐⇒ ∃k ∈ Z, tel que n = 38h + 19 − 2 = 38h + 17, pour un certain h ∈ Z.
Par suite, n ∈ {38h + 17 : h ∈ Z}.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆
Exercice 12.
1) Utiliser l’algorithme d’Euclide pour trouver pgcd(255, 141).
2) Déduire une solution (x, y) ∈ Z de l’équation diophantienne 3 = 255x + 141y.
Solution.
1) On va appliquer l’algorithme d’Euclide pour trouver pgcd(255, 141). On a :
255 = 141 × 1 + 114, (1)
141 = 114 × 1 + 27, (2)
114 = 27 × 4 + 6, (3)
27 = 6 × 4 + 3, (4)
6 = 3 × 2 + 0. (5)
Donc, pgcd(255, 141) = 3.
2) Trouvons maintenant les entiers relatifs x et y tels que 3 = 255x + 141y. On va procéder
dans le sens inverse de l’algorithme d’Euclide en remplaçant le reste ri par ri−1 comme suit :
par l’avant dernière équation de l’algorithme d’Euclide ci-dessus (i.e. (4)) on a :
27 = 6 × 4 + 3 ⇒ 3 = 27 − 6 × 4
= 27 − 4 × (114 − 27 × 4) (par (3))
= 17 × 27 − 4 × 114
= 17 × (141 − 114) − 4 × 114 (par (2))
= 17 × 141 − 21 × 114
= 17 × 141 − 21 × (255 − 141) (par (1))
= −21 × 255 + 38 × 141.
D’où x = −21 et y = 38.

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆⋆

www.youtube.com/@Departement_de_Mathematiques Page 8/4