Exercice 1 tp

1) Décomposer 12285 et 23400 en facteurs premiers.
2) Déterminer (12285∧23400) et (12285∨23400).

Exercice 2 tp

1) Décomposer 1232 et 1904 en facteurs premiers.
2) Déduire (1904∧1232) et (1904∨1232).

Exercice 3 tp

Soient x=3510 et y=1575 deux entiers.
1) Déterminer x∧y et x∨y.
2) Vérifier que x.y=(x∧y).(x∨y).

Correction

1) On a x=2.3³.5.7°.11°.13
et y=2°.3².5².7.11°.13° donc
x∧y=2^inf(1;0).3^inf(3;2).5^inf(1;2)
. 7^inf(0;1).11^inf(0+0).13^inf(1;0)
=2⁰.3².5¹.7⁰.11⁰.13⁰=1.9.5.1.1=45.

x∨y=2^sup(1;0).3^sup(3;2).5^sup(1;2)
. 7^sup(0;1).11^sup(0+0).13^sup(1;0)
=2¹.3³ .5².7¹ .11⁰.13¹
= 2.27.25.7.13 = 122850
2) x.y= 45.122850=5528250
et on aussi x.y=3550.1575=5528250
on trouve le même résultat :)

Exercice 2 tp

Soient a=137 ; b=123 ; n=7.
Montrer que 137≡123[7].

Correction

On effectue la division euclidienne de 137 par 7 puis 123 par 7.
137=19x7+4 et 0≤r=4<7
123=17x7+4 et 0≤r'=4<7
donc a et b ont le même reste dans la division euclidienne par 7
ainsi 137≡123[7]
de plus 137≡123≡4[7].

Exercice 3 tp

Déterminer v un inverse de 4 pour la congruence modulo 17.

Correction

Rappel Soient u∈ℤ et n∈IN*.
v est un inverse de u pour la congruence modulo n signifie que u x v≡1[n].

4 x v≡1[17] ⇔ (E): 4v-17k=1 tel que k∈Z.
17=4x4+1 ⇔ 17-4x4=4x(-4)-17(-1)=1.
(-4;-1) est une solution particulière de l'équation (E) et donc -4 est l'inverse de 4 pour la congruence modulo 17.

Exercice 4 tp

Montrer que 594²⁰≡1[7].

Correction

Rappel Soit p∈IN*
1) Si u≡v [p] ⇒ uⁿ ≡ vⁿ[p]
2) Si (u≡v[p]) et (u'≡v'[p])
⇒ (u + u')≡(v + v') [p]
3) Si (u≡v[p]) et (u'≡v'[p])
⇒ (u x u')≡(v x v')[p]

Première méthode
594 = 27x22 = 27x(21 + 1)
27≡-1[7] car 7|28
donc 27²⁰ ≡ 1[7].
22≡1[7] car 7|21
donc 22²⁰≡1[7]
ainsi 27²⁰ x 22²⁰≡1[7] alors 594²⁰≡1[7]. Deuxième méthode
594≡-1[7] car 7|595
donc 594²⁰≡1[7].