Articles
Mathématiques
Arithmétique dans Z

Rappels


1. Division euclidienne:

Si n est un entier relatif, et m est un entier naturel non nul, il existe un unique couple d’entiers (k ; r) tel que :

n = mk + r avec 0 ≤ r < m

Définitions :

n est le dividende, m le diviseur, et r est le reste de la division euclidienne de n par m.

2. Congruences:

On dit que le dividende d est congru à r 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.

3. Classes d'équivalence

Pour un diviseur p fixé, et à partir des restes des divisions par p , on construit des classes pour chaque reste inférieur à p. On met les p classes obtenues dans un ensemble noté Z/pZ .

La classe "r" est notée (r).

Propriétés des classes

a, b sont des entiers, (a) et (b) sont leurs classes respectives, on a:

• (a) + (b) = (a + b)
• (a) x (b) = (a x b)
• n ∈ N , n x (a) = (n x a)

Exemple

1) p = 5. Les restes tel que: 0 ≤ r < 5 sont :
0, 1, 2, 3, et 4.
On aura 5 classes dans Z/5Z x Z/5Z, avec

Z/5Z = {(0), (1), (2), (3), (4)}

(r) = {n ∈ Z / n ≡ r[5] ou n - r = 5k , k ∈ Z}

(0) = {n ∈ Z / n ≡ 0[5] ou n = 5k , k ∈ Z} =
{... - 15, - 10 , - 5, 0, 5, 10, 15 , ... }:
C'est l'ensembles des multiples de 5.

(1) = {n ∈ Z / n ≡ 1[5] ou n = 5k + 1, k ∈ Z} =
{... - 14, - 9 , - 4, 1, 6, 11, 16 , ... }:

.... ....

Dans Z/5Z, on veut résoudre le système suivant:

(3) x + (2) y = (1)
(2) x + (4) y = (3)

Pour éliminer les y, on multiplie la première équation par 2, et on la soustrait de l'équation 2 du système. Il vient :

2(3) x + 2(2) y = 2(1)
(2) x + (4) y = (3)

(6) x + (4) y = (2)
(2) x + (4) y = (3)

(4) x = (- 1) = (4)
(2) x + (4) y = (3)

La première équation donne x = (1)
La deuxième donne (2) + (4) y = (3)
⇒ (4) y = (3) - (2) = (1)
(4) y = (1) ⇒ y = (4)

L'ensemble des solutions est :

S = {((1), (4))}


2) On veut résoudre l'équation :

x³⁰ = (1) dans Z/7Z.

Voici les classes de Z/7Z:

Z/7Z = {(0), (1), (2), (3), (4), (5), (6)}

• (0)³⁰ = (0)

• (1)³⁰ = (1)

• (2)³⁰ = ((2)³)¹⁰ = ((8))¹⁰ = (1)¹⁰ = (1)

• (3)³⁰ = ((3)³)¹⁰ = ((27))¹⁰
= (6)¹⁰ = ((6)²)⁵ = (36)⁵ = (1)⁵ = (1)

• (4)³⁰ = ((4)²)¹⁵ = ((16))¹⁵ = (1)¹⁵ = (1)

• (5)³⁰ = ((5)²)¹⁵ = ((25))¹⁵
= (4)¹⁵ = ((4)³)⁵ = (64)⁵ = (1)⁵ = (1)

• (6)³⁰ = ((6)²)¹⁵ = ((36))¹⁵ = (1)¹⁵ = (1)

L'ensemble des solutions est donc:

S = {(1), (2), (3), (4), (5), (6)}


3) Divisibilité dans une suite:

n ∈ N, On a la suite suivante:

u_n = 4ⁿ - 3n - 1

a) Pour n + 1, on a:

u_n+1 = 4ⁿ⁺¹ - 3(n + 1) - 1 =
4 x 4ⁿ - 3n - 4 + 9n - 9n =
4 x 4ⁿ - 12n - 4 + 9n =
4 (4ⁿ - 3n - 1) + 9n = 4 u_n + 9 n

Donc:

u_n+1 = 4 u_n + 9 n


b) On veut montrer que 9 divise u_n.

On fait un raisonnement par récurrence:

Proposition P(n): 9 divise u_n

1)P(0): n = 0 , u₀ = 0 divisible par 9 : VRAIE

2) P(n) On admet que 9 divise u_n.

3) P(n + 1): L'est-il pour n + 1 ?

On a : u_n+1 = 4 u_n + 9 n

9 divise 4 u_n par hypothèse et disive 9 n , donc 9 divise u_n+1. P(n + 1) VRAIE.

Conclusion:

P(0) est vraie, P(n) est héréditaire, donc par récurrence P(n) est vrai pour tout entier naturel n ≥ 0, c'est à dire pour tout entier naturel n.

-- Abdurrazzak Ajaja
mars 2024