Articles
Mathématiques
Arithmétique modulaire

Rappels:

1. Divisibilité

La congruence est une arithmétique sur les restes des divisions euclidiennes des nombes entiers. Le diviseur considéré est toujours un entier positif.

Soit n et m deux entiers relatifs.
On dit que n divise m s'il existe un entier relatif k tel que m = kn.

2. Division euclidienne:

Si n est un entier et m est un entier naturel non nul, il existe un unique couple d’entiers (q ; r) tel que :
n = mq + r avec 0 ≤ r < m

Définitions :

• q est appelé le quotient de la division euclidienne de n par m,
• r est appelé le reste.

3. Congruence:

Soit m un entier naturel non nul.
Deux entiers n et r sont congrus modulo m lorsque n – r est divisible par m.
On ecrit, n ≡ r[m] ou n - r = 0[m]

Le nombre n est la base, r est nommé résidu (ou reste) de n modulo m. Cette égalité s'appelle congruence.

Propriétés d'une congruence:

a, b , c et des entiers relatifs, m un entier naturel.

• Si n ≡ r[m] ⇒ k n ≡ k r [m]; k ∈ Z.

• n ≡ r [m] ⇒ n ^x ≡ r ^x[m] ; x ∈ N
• Si n1 ≡ r1[m] et n2 ≡ r2[m] , alors
n1 ≡ r1[m] + n2 ≡ r2[m] = (n1 + n2) (r1 + r2)[m]
n1 ≡ r1[m] - n2 ≡ r2[m] = (n1 - n2) (r1 x r2)[m]
n1 ≡ r1[m] x n2 ≡ r2[m] = (n1 x n2) (r1 x r2)[m]


Exemple 1:

1) 3²ⁿ⁺¹ + 2ⁿ⁺² = 3 x 3²ⁿ + 4 x 2ⁿ

On a:

3 ≡ 3 [7] → 3² ≡ 2 [7] ⇒ 3²ⁿ ≡ 2ⁿ [7]

et :

2 ≡ 2 [7] → 2ⁿ ≡ 2ⁿ [7] ⇒ 3²ⁿ ≡ 2ⁿ [7]

On fait la somme:

3 x 3²ⁿ + 4 x 2ⁿ ≡ 3 x 2ⁿ[7] + 4 x 2ⁿ[7] = 7 x 2ⁿ[7] ≡

0[7] x 2ⁿ[7] ≡ 0[7]

3 x 3²ⁿ + 4 x 2ⁿ ≡ 0[7] ⇒ 3²ⁿ⁺¹ + 2ⁿ⁺² ≡ 7 k .
C'est à dire 7 divise 3²ⁿ⁺¹ + 2ⁿ⁺².


2) 2⁶ⁿ⁺³ + 3²ⁿ⁺¹ = 8 x 2⁶ⁿ + 3 x 3²ⁿ

On a:

2 ≡ 2 [11] ⇒ 2³ ≡ 8 [11]

⇒ 8 x 8²ⁿ[11] + 3 x 3²ⁿ [11]

= 8 x 64ⁿ[11] + 3 x 9ⁿ [11]

Or 64[11] = 9 [11] ⇒ 64ⁿ[11] = 9ⁿ [11]

Il reste

8 x 9ⁿ[11] + 3 x 9ⁿ [11] =

11 x 9ⁿ [11] = 0[11]

2⁶ⁿ⁺³ + 3²ⁿ⁺¹ ≡ 0[11] ⇒ 2⁶ⁿ⁺³ + 3²ⁿ⁺¹ = 11 k .
C'est à dire 11 divise 2⁶ⁿ⁺³ + 3²ⁿ⁺¹.


Exemple 2:

n est un nombre entier impair. Montrons que 8 divise 7ⁿ + 1

n impair ⇒ n = 2k + 1 ,k ∈ N

7ⁿ + 1 = 7 x 7^2k + 1 = 7 x 49^k + 1

49^k = 1 [8]

1 = 1 [8]

Donc:

7 x 49^k + 1 = 7 x (1)^k [8] + 1 [8] =
7 [8] + 1 [8] = 8 [8] = 0

7ⁿ + 1 ≡ 0[8] ⇒ 7ⁿ + 1 = 8 k .
C'est à dire 8 divise 7ⁿ + 1


Exemple 3:

n ∈ N: n divise n + 8 ↔ n + 8 = k n , k ∈ Z

⇒ n = 8/(k - 1) , k = 2, 3, ...

Nous avons donc l'expression de l'ensemble E en compréhension :

E = {n ∈ N/ n = 8/(k - 1), k = 2, 3, , ... }

On cherhe les solutions dans N:

n ∈ N ⇒ 8/(k - 1)≥ 1
C'est à dire: k - 1 ≤ 8 ou
k ≤ 9

On trouve des solutions pour

k = 2 → n = 8
k = 4 → n = 4
k = 5 → n = 2
k = 9 → n = 1


Donc S = {2, 4, 7, 8}

De façon simple:

n/ n + 8
n/n

Donc
n /(n+8) - n = 8

D'où n/8

Les diviseurs de 8 sont 1, 2, 4, et 8, don:

S = {2, 4, 7, 8}


F = {n ∈ N/ (n³ - 3)/(n - 3) ∈ Z }

(n³ - 3)/(n - 3) ∈ Z ⇒

(n³ - 3)/(n - 3) = n² + 3 n + 9 + 24/(n-3) ∈ Z

⇒ 24/(n-3) ∈ Z

⇒ 24/(n-3) = k ; k ∈ Z

⇒ n = 24/k + 3 ; k ∈ ]- ∞ ; 0[ + ]0; + ∞[

F = {n = 24/k + 3 ; k ∈ ]- ∞ ; 0[ ∩ ]0; + ∞[ }


Exemple 4:

Dans une division euclidiènne n = m q + r, le diviseur m = 45, le reste est le carré du quotient q. On cherche le dividende n .

On a:

n = m q + r
r = q²
0 ≤ r < d

Donc:

n = 45 q + q²
q² < 45 ⇒ q < 7

n = 45 q + q²
q = 0, 1, 2, 3, 4, 5, 6

n (0) = 0 , n(1) = 46, n(2) = 94, n(3) = 144 , n(4) = 196, n(5) = 250 , n(6) = 306 .

S = { 0 , 46, 94, 144 , 196, 250 , 306} .


Exemple 5:

On a:

a = 3n + 8 , et
b = 11n + 29

Montrer que pgcd (a, b) = 1

Nous allons utiliser les deux propriétés suivantes du PGCD:

• pgcd(a,b) = pgcd(a, b + a) = pgcd(a, b - a)
• pgcd(a,b) = pgcd(a - b, b)

pgcd(3n + 8, 11n + 29) = pgcd(3n + 8, 11n + 29 - 3n - 8) =
pgcd( 3n + 8, 8n + 21)= pgcd( 3n + 8, 8n + 21 - 3n - 8) =
pgcd( 3n + 8, 5n + 13)= pgcd( 3n + 8, 5n + 13 - 3n - 8) = pgcd( 3n + 8, 2n + 5) =
pgcd( 3n + 8 - 2n - 5, 2n + 5) = pgcd(n + 3, 2n + 5) =
pgcd( n + 3 , 2n + 5 - n - 3 ) = pgcd( n + 3, n + 2) =
pgcd( n + 3 - n - 2, n + 2) = pgcd( 1, n + 2) = 1

On peut aussi utiliser le théorèeme de Bézout por prouver que l'égalité pgcd (a, b) = 1 = 1.


Exemple 6:

On a

n ∈ Z,
a = 20 n - 1, et
b = 15 n + 1

d = a ∧ b

1) d = pgcd(a,b) ⇒ d divise a et d divise b et divise aussi une combinaison linéaire quelconque des a et b: v a + w b

soit v = 3 et w = - 4. On aura donc:

v a + w b = 3 a - 4 b = 3(20n - 1) - 4 (15 n + 1) = 60 n - 3 - 60n - 4 = - 7

d divise - 7 , donc d divise 7 .

d divise 7


2) Les valeurs possibles de d sont soit 1 , soit 7 .

d = {1, 7}

-- Abdurrazzak Ajaja
mars 2024