TD 3 : Anneaux - Algèbre de boole

Exercice 1 : Anneau sur R.

On définie sur RxR les opérateurs ± et ¤ par :
x ± y = x + y - 1
x ¤ y = x + y - xy
Montrez que (R, ±, ¤) est un anneau. Est-ce un corps ?

Solution exercice 1

Soit x et y deux réels quelconques.
Puisque + et  .  sont deux  lois de composition interne sur R, on en déduit que : ±, ¤ sont deux lois de composition interne sur R.

De même, puisque + et  .  sont deux  lois commutatives sur R nous obtenons :
x ± y = x + y - 1 = y + x - 1 = y ± x
x ¤ y = x + y - xy = y + x - yx = y ¤ x
Les deux lois sont donc commutatives

Associativité  pour tout triplet de réels x,y,z :
En utilisant le fait que + est associatif et commutatif,
(x ± y) ± z = (x + y - 1) ± z  = (x + y - 1) + z - 1 = x  + (y + z - 1) - 1 = x ± (y ± z)
En utilisant le fait que ¤ est associatif et commutatif,
(x ¤ y) ¤ z = (x + y - xy) ¤ z = (x + y - xy) + z - (x + y - xy) z = x + y + z - xy - xz - yz +xyz
(x ¤ y) ¤ z = x + (y + z - yx) - xy - xz +xyz = x + (y + z - yx) - x (y+z - yz) = x + (y ¤ z) - x (y ¤ z) = x ¤ (y ¤ z)
Les deux lois sont associatives

Éléments neutres :
On cherche un élément e tel que pour tout x, x ± e = x.
x ± e = x + e - 1  donc on veut résoudre x + e - 1 = x  d'où e = 1
On cherche un élément e' tel que pour tout x, x ¤ e' = x.
x ¤ e' = x + e' - xe', donc on veut résoudre x + e' - xe' = x d'où e' - xe' = 0 et
e'(1- x) = 0. Donc e' = 0 ou x = 1 (élémént neutre de la première loi)
1 et 0 sont les éléments neutres de nos lois.

Inverse pour la première loi :
Pour tout x existe-t-il un élément x' tel que x ± x' = e = 1.
On cherche à résoudre : x ± x' = x + x' - 1 = 1 donc x' = 2 - x.
Tout élément possède un inverse par la première loi.
(R, ±) est un groupe abélien

Distributivité pour tout trplet de réel x, y, z:
x ¤ (y ± z) = x ¤ (y + z - 1) = x + (y + z - 1) - x (y + z - 1) =x + y + z - xy - xz + x - 1
x ¤ (y ± z) = (x + y - xy) + (x + z - xz) - 1 = (x ¤ y) + (x ¤ z) - 1 = (x ¤ y) ± (x ¤ z)
Donc la distributivité de la seconde loi sur la première est assurée.

Donc R muni de ces deux lois est un anneau

R muni de ces deux lois est-il un corps ?
La seule chose à vérifier est la notion d'inverse pour la seconde loi.
Pour tout x différent de e, existe-t-il un élément x' tel que x ¤ x' = e' = 0.
On cherche à résoudre : x ¤ x' = x +x' - xx' = 0. D'où x' (1 -  x) = x.
Deux cas :
Cas 1  x =1 :  x est l'élément neutre de la première loi il ne peut donc pas avoir d'inverse pour la seconde loi.
Cas 2 x  est différent de 1 : alors  x' = x/(1-x)
R muni de ces deux lois est un corps

L'exercice 2 est identique à l'exercice 1 Il n'y aura donc pas de corrections.

Exercice 3 : Idéal
a - Si I est un idéal de A alors (I,+) est un groupe. De plus, pour tout x de A et tout y de I, xy est un élément de I
Pour des problèmes de clavier, je change de notations.
W : ensemble des x de A tel qu'il existe un entier naturel n tel que xn  soit un élément de  I.

Il faut donc montrer que (W,+) est un goupe

En posant n = 1 on remarque que I est inclus dans W.
D'autre part si xn  est un élément de  I alors pour tout t > n xt  est un élément de  I (xt = xt-nxn et I est un Idéal)

Rappel : (x+y)k = Somme( C(i,k) xiyk-i) pour i variant de 0 à k avec C(i,k) = (k!)/(i!(k-i)!)

Soit x un élément de W  soit t un entier naturel tel que xt est un élément de I
Soit y un élément de W  soit u un entier naturel tel que yu est un élément de I

Regardons les monomes de (x+y)t+u Un tel monome est de la forme
C(i,t+u) xiyt+u-i Il nous faut regarder deux cas :
Cas 1 i > t-1. Alors xi appartient à I donc puisque I est un Idéal, C(i,t+u) xiyt+u-i est un élément de I
Cas 2 i < t alors t+u-i > u donc yt+u-i appartient à I donc puisque I est un Idéal, C(i,t+u) xiyt+u-i est un élément de I

Donc Chaque monome appartient à i donc puisque + est une loi de composition interne pour I (x+y)k est un élément de I.

+ est une lois de composition interne pour W.

Il nous faut vérifier que si x est dans W alors son inverse par la première loi (+) est dans W.
Si x appartient à W alors il existe n tel que xn  est un élément de  I.
Posons x' l'inverse de x par la première lois, alors x2 = x'2 donc x2n = x'2n et 2n > n donc x2n est un élément de I. Donc x' est un élément de W.

(W,+) est un groupe.

b - Posons WI et WJ les  deux ensembles concernés.  

Si x est un élément de WI il existe un entier n tel que xn  est un élément de  I or I est un sous ensemble de J donc xn  est un élément de  J donc x est un élément de WJ.

WWI contient WI qui lui même contient I
Soit x un élément de WWI alors il existe un entier n tel que xn  est un élément de  WI.
Si xn  est un élément de  WI alors il existe un entier m tel que (xn)m  est un élément de  I.
Donc xnm  est un élément de  I et x est un élément de WI.
WI=WWI.

4 Théorème du reste chinois.

Selon l'énoncé on a :

x = 17 k + 3
x = 11 l + 4
x = 6 m + 5

k1 = 66, k2 = 102 et k3 = 187

Premier système :
x1 = 17 k + 1
x1 = 11 l
x1 = 6 m
Ceci revient à chercher deux entiers u et v tels que 66u + 17v = 1
En appliquant l'algorithme de Bezout :

66 = 3*17 + 15
17 = 1*15 + 2
15 = 2*7 +1
étape
 r
 q
 u
 v
0
 66
1
 0
1
 17
0
 1
2
 15
 3
 1-3*0 = 1
 0-3*1 = -3
3
 2
 1
 0-1*1 =-1
 1-1*-3 = 4
4
 1
 7
 1- (-1*7) = 8
 -3 - 4*7 = -31
5
 0
 2
 -1 - 2*8 = -17
 4-2*(-31) = 66

66 * 8 - 31 * 17 = 528 - 527 =1 donc x1 = 8*66 =528

Second système
x2 = 17 k
X2 = 11 l +1
X2 = 6 m

Ceci revient à chercher deux entiers u et v tels que 102u + 11v = 1
En appliquant l'algorithme de Bezout :


étape
 r
 q
 u
 v
0
 102
1
 0
1
 11
0
 1
2
 3
 9
 1-9*0 = 1
 0-9*1 = -9
3
 2
 3
 0-3*1 =-3
 1-3*-9 = 28
4
 1
 1
 1- (-3*1) = 4
 -9 - 1*28 = -37
5
 0
 2
 -3 - 2*4 = -11
 28-2*(-37) = 102

102 * 4 - 11* 37 = 408 - 407 = 1 donc x2  = 408

Troisième système :
x3 = 17 k
X3 = 11 l
X3 = 6 m + 1

Ceci revient à chercher deux entiers u et v tels que 187u + 6v = 1

187 * 1 - 31* 6 = 187 - 186 = 1 donc x3  = 187


Posons
S1 = x1* 3 + x2 * 4 + x3 * 5 = 528 * 3 + 408 * 4 + 187 * 5 = 1584 + 1632 + 935 = 4151

S1 est une somme possible mais est-ce la plus petite ?

Pour le savoir calculons le ppcm des trois entiers 17, 11 et 6 : 1122

Divisons 4151 par 1122 :  quotient 3 reste 785.
or

785 = 46*17 + 3
785 = 71*11 + 4
785 = 130*6 + 5

785 est donc la valeur attendue.

Exercice 5 Algèbre de Boole

a- non corrigé ici car il suffit de vérifier des formules...

b- ax + bx' = x  (x' désigne le complémentaire de x)

On compose par x' des deux cotés :
(ax + bx') x' = xx' = 0 donc axx' + bx'x' = 0 +bx' = bx' = 0
Or bx' = 0 si et seulement si b est inférieur ou égal à x

En reprenant l'équation initiale on obtient ax = x
Or ax = x si et seulement si a est supérieur ou égal à x.

Réciproquement, la double inégalité entraîne que bx' = 0 et ax = x  donc :
ax + bx' = x + 0 = x.

c- ax + bx' = 0

pour tout x on sait que x+0 = 0+x = x. Donc l'équation x+y =  0 n'a qu'une seule solution :  x=0 et y = 0.

Donc ici  ax=0 et bx' = 0
ax=0 si et seulement si x est inférieur ou égal à a'
bx' = 0  si et seulement si b est inférieur ou égal à x.

That's all folk...