Articles
Mathématiques
Arithmétique dans Z

On n'oublie pas les formules :

1) De la division euclidienne:

a = b q + r ⇒ a = r[b], a, q, r ∈ N et b ∈ N^*

avec 0 ≤ r < b

2) du PGCD:

a et b sont des entiers relatifs non tous les deux nuls. PGCD(a,b) = PGCD(b,a) = PGCD(a − b,b) = PGCD(a,b - a) = PGCD(a − kb, b) pour tout k ∈ Z.


Exemples

Soit l'équation :

1) 11x - 17 y = 4       (E)

On cherche une solution particulière par l'algorithme d'Euclide:

17 = 11 x 1 + 6       (2)
11 = 6 x 1 + 5       (3)
6 = 5 x 1 + 1       (4)
5= 1 x 5 + 0

En remonte à partir de l'équation (4):

À partir de (4) , on a:

1 = 6 - 5 x 1
On remplace 5 par sa valeur dans (3)
= 6 - ( 11 - 6 x 1) x 1
On factorise:
= 6 - 11 x 1 + 6 x 1 =
= 6 x 2 - 11 x 1
On remplace 6 par sa valeur dans (2)
= ( 17 - 11 x 1) x 2 - 11 x 1
On factorise:
= 17 x 2 - 11 x 3
Finalement,

1 = 17 x 2 - 11 x 3 , ou

(- 3) 11 - (- 2) 17 = 1

On multiple par 4, on obtient:

(- 12) 11 - (- 8) 17 = 4       (P)

On obtient donc le couple x = - 12, y = - 8 comme solution particulière.

2) calculer le pgcd de (17p + 5) et (11p + 3)

On va utiliser les deux formules suivantes:

PGCD(a,b) = PGCD(b,a) = PGCD(a − b,b) = PGCD(a,b - a) = PGCD(a − kb, b) pour tout k ∈ Z.

(17p + 5) ∧ (11p + 3) = (17p + 5 - 11p - 3) ∧ (11p + 3) =
(6p + 2) ∧ (11p + 3) = (6p + 2 ) ∧ (5p + 1) = (5p + 1) ∧ (p + 1 )
= (5p + 1 - 5(p + 1)) ∧ (p + 1) = (- 4) ∧ (p + 1) =
(4 ) ∧ (p + 1)

(17p + 5) ∧ (11p + 3) = 4 ∧ (p + 1)

3) α et β sont des solutions de (E)

a) On a donc : 11 α - 17 β = 4

On pose d = α ∧ β

On utilisant la solution particulière (P) :
(- 12) 11 - (- 8) 17 = 4
et l'équation (E), on trouve les solutions génèrales de (E) :

11x - 17 y = 4       (E)
(- 12)11 - (- 8) 17 = 4       (P)

On soustrait membre à membre (E) et (P), on trouve:

11(x + 12) - 17( y + 8 ) = 0 , ou

11(x + 12) = 17( y + 8 )

11 et 17 sont premiers entre eux, donc:

17 divise x + 12 et 11 divise y + 8. D'où:

x + 12 = 17 k    k ∈ Z
y + 8 = 11 k'    k' ∈ Z

La solution générales de l'équation (E) est alors donnée par :

x = - 12 + 17 k et y = - 8 + 11k , k et k' ∈ Z

Si α et β sont des solutions de (E), on aura:

α = - 12 + 17 k et β = - 8 + 11k' , k et k' ∈ Z

d = α ∧ β = (- 12 + 17 k) ∧ (- 8 + 11k') k et k' ∈ Z

Pour k = 1 et k' = 1, on aura un autre couple de solutions : α = 5 et β = 3 . Donc

α = 5 + 17p et β = 3 + 11p , p ∈ Z

On a donc: d = α ∧ β = (5 + 17 p) ∧ (3 + 11p) = (p+1) &and 4 , p ∈ Z

Voici les valeurs de d:

d = (p+1) ∧ 4 , p ∈ Z

b) α = 5 + 17p et β = 3 + 11p , p ∈ Z

α + β = 8 + 28p = 4(2 + 7p), p ∈ Z

Nous avons donc:

4 divise (α + β)

c) Les couples solutions de (E) sont a = (5 + 17 p) et b = (3 + 11p), p ∈ Z

a ∧ b = (p+1) ∧ 4 , p ∈ Z

Pour que a ∧ b = 4 , il faut que p + 1 = 4 k , k ∈ Z.

Donc :

Les couples solutions de (E) sont telles que a ∧ b = 4, sont:

a = ∈ Z

ou

a = - 12 + 68k et b = - 8 + 44k , k∈ Z


2) Le résultat suivant est le même pour n = 9.

Divison de (a-1) par b et (abⁿ - 1) par bⁿ⁺¹

Division de a - 1 par b :

a - 1 = b q + r avec,

0 ≤ r < b

a = b q + r + 1

donc on a : 1 ≤ (r+1) ≤ b , et la seconde inégalité devient non stricte.

On multiplie par bⁿ :

a. bⁿ = q. bⁿ⁺¹ + (r+1).bⁿ

On soustrait 1:

a. bⁿ - 1 = q.bⁿ⁺¹ + (r+1).bⁿ- 1

C'est le quotient de a.bⁿ - 1 par bⁿ⁺¹ qui s'écrit:

a.bⁿ - 1 = Q.bⁿ⁺¹ + R avec 0 ≤ R < bⁿ⁺¹ , la econde inégalité est stricte.

On va déterminer R:

1 ≤ (r+1) ≤ b

On multipliant par bⁿ qui est positif :

bⁿ ≤(r+1). bⁿ ≤ bⁿ⁺¹

bⁿ - 1 ≤ (r+1).bⁿ - 1 ≤ bⁿ⁺¹ - 1

Ou avec une inégalité au sens stricte :

bⁿ - 1 ≤ (r+1).bⁿ - 1 < bⁿ⁺¹

0 ≤ bⁿ - 1 ≤ (r+1).bⁿ - 1 < bⁿ⁺¹

0 ≤ (r+1) bⁿ - 1 < bⁿ⁺¹

C'est la condition requise pour le reste R.

Conclusion:

Le reste R vaut bien (r+1)bⁿ - 1 et le quotient Q vaut q


3) 1) On veut montrer que :

(n + 2)ⁿ⁺² - 2ⁿ⁺² (n + 1) ≡ 0[n²]

C'est à dire que L'expression (n + 2)ⁿ⁺² - 2ⁿ⁺² (n + 1) est est divisible par n²"

Le développement de (n + 2)ⁿ⁺² s'ecrit:

(n + 2)ⁿ⁺² = C(n+2,0). nⁿ⁺²2⁰ + C(n+2,1).nⁿ⁺¹ 2¹ + C3(n+2,2). nⁿ 2² + C(n+2,3) . n^n-1 2³ + ... +

+ C(n+2,n-3)n³ 2^n-1 +C(n+2,n-2) n² 2ⁿ + C(n+2,n-1)n¹ 2ⁿ⁺¹ + C(n+2,n) n⁰ 2ⁿ⁺²

C(n+2,k) sont les coefficients binomiaux de la formule du binôme de Newton (n + 2)(n + 2)ⁿ⁺²

L'expression:

- 2ⁿ⁺² (n + 1) vaut - n 2ⁿ⁺² - 2ⁿ⁺²

On aura donc:

(n + 2)ⁿ⁺² = C(n+2,0). nⁿ⁺²2⁰ + C(n+2,1).nⁿ⁺¹ 2¹ + C3(n+2,2). nⁿ 2² + C(n+2,3) . n^n-1 2³ + ... +

+ C(n+2,n-3)n³ 2^n-1 + C(n+2,n-2) n² 2ⁿ + C(n+2,n-1)n¹ 2ⁿ⁺¹ + C(n+2,n) n⁰ 2ⁿ⁺²
- n 2ⁿ⁺² - 2ⁿ⁺²

=

n² {nⁿ + n^n-1 2¹ + ... - n^-1 2ⁿ⁺¹} = K n²

Résultat divisible par n² .


Voir l'annexe plus bas, pour plus de détails ..


2) On veut montrer si : ((((((7)⁷)⁷)⁷)⁷)⁷)⁷) ≡ 7[10] ?

7 à la puissance 7 , six fois.

Nous avons la série suivante des opérations modulo 10:

7 ≡ 7[10]

7² ≡ 49[10] ≡ 9 [10] ≡ -1 [10]

7⁴ ≡ (-1)² [10] ≡ 1[10]

7⁶ ≡ -1 [10]

7⁷ ≡ -7 [10] ≡ 3 [10]

(7⁷)⁷ ≡ 3⁷ [10] ≡ 2187 [10] ≡ 7[10]

((7⁷)⁷)⁷ ≡ 7⁷[10] ≡ 3[10]

....

On résume:

7 ≡ 7[10]
une fois : 7⁷ ≡ 3 [10]
deux fois: (7⁷)⁷ ≡ 3⁷ [10] = 7[10]
trois fois: ((7⁷)⁷)⁷ ≡ 3[10]
quatre fois: (((7⁷)⁷)⁷)⁷ ≡ 7[10]
cinq fois: ((((7⁷)⁷)⁷)⁷)⁷ ≡ 3[10]
six fois: ((((((7⁷)⁷)⁷)⁷)⁷)⁷ ≡ 7[10]
sept fois: (((((((7⁷)⁷)⁷)⁷)⁷)⁷)⁷ ≡ 3[10]


Annexe pour l'exercice 3) 1):

Il s'agit d'utiliser la formule du binôme de Newton:

Soit l'expression:

(n + 2)^{n + 2} - 2ⁿ⁺²(n + 1)     (E)

• Le deuxième terme vaut:
- 2ⁿ⁺²(n + 1) = - 4(n + 1) 2ⁿ

• Le premier terme vaut:
(n + 2)^{n + 2} = (n + 2)² . (n + 2)ⁿ

La formule du binôme de Newton donne :

(n + 2)ⁿ = 1. nⁿ . 2⁰ + n. n^n-1.2¹ + ((n - 1)n/2). n^n-2. 2² + ... + ((n - 1)n/2). n² 2^n-2 + n. n¹ 2^n-1 + 1.n ⁰. 2ⁿ

= nⁿ + 2 nⁿ + (2(n - 1)n). n^n-2 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1 + 2ⁿ

= 3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1 + 2ⁿ

Donc, le premier terme de (E) devient:

(n + 2)² . (n + 2)ⁿ =
(n + 2)² [ 3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1 + 2ⁿ ] =

On sépare le dernier terme: 2ⁿ. On a:

= (n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] + (n + 2)² [2ⁿ] = (n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] +
n² + 4n + 4 [2ⁿ] =

(n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] + n² 2ⁿ + 4(n + 1) 2ⁿ =

(n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] +
n² 2ⁿ + 4(n + 1) 2ⁿ =

En rajoutant le deuxième terme - 4(n + 1) 2ⁿ, qui disparaitra, on obtient une nouvelle expression de (E), soit:

(n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] + n² 2ⁿ + 4(n + 1) 2ⁿ + - 4(n + 1) 2ⁿ =

(n + 2)² [3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] +
n² 2ⁿ

On va faire apparaitre le facteur n² dans l'expression entre crochets:

[3 nⁿ + 2(n - 1) n^n-1 + ... + ((n - 1)n/2). n² 2^n-2 + n² 2^n-1] =

n²[3 n^n-2 + 2(n - 1) n^n-3 + ... + ((n - 1)n/2). 2^n-2 + 2^n-1]

Finalement, l'expression de (E) s'ecrit:

n²[3 n^n-2 + 2(n - 1) n^n-3 + ... + ((n - 1)n/2). 2^n-2 + 2^n-1]

Qui est bien divisible par n².

On peut donc écrire:

(n + 2)^{n + 2} - 2ⁿ⁺²(n + 1) ≡ 0[n²]

-- Abdurrazzak Ajaja
Avril 2024