Exercice 1 tp

Soit 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

Soit 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 ; 0≤r=4< 7
et 123=17x7+4 ; 0≤r'=4< 7
donc a et b ont le meme 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

Rappelu∈ℤ 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; k∈Z
17=4x4+1 ⇔ 17-4x4=4x(-4)-17(-1)=1
(-4;-1) est une solution particulière de l'équation (E) il suffit donc de prendre x=-4 qui est exactemment 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]

Exercice 5 tp

Résoudre dans ℤ/4ℤ l'équation 2x=0

Correction

On peut utiliser le tableau de la congruence modulo 4

donc S = {0;2}
Remarque
2x=0⇏ x=0