|
Arithmétique modulaire Applications Intérêt de cette
arithmétique basée sur les restes aux problèmes de divisibilité. Autres
applications. |
|
||
Le calcul
modulo offre bien des avantages, mais résoudre des équations dans ce mode
nécessite une bonne intuition ou une grande pratique. Ici, ajouter
du 13 pour réussir à mettre en évidence un carré |
|
|
|
||
Démontrer
que si n est égal à 0 ou 5 mod 10 alors n est divisible par 5. |
|
|
On se
souvient que, par exemple: C'est une manière d'écrire la division
euclidienne en ignorant le quotient (ici 7 = k). |
73 = 10 x 7 + 3 73 = 10 x k + 3 |
|
n égal 0
mod 10 est un raccourci pour dire: n égal 5
mod 10 est un raccourci pour dire: |
n = 10k = 5 x
2k n = 10k + 5 = 5
(2k + 1) |
|
Que l'on
soit dans le premier cas ou le second: |
n est divisible par 5 |
|
Voir Divisibilité
par 5
|
|||||||||||||||||||||||
Soit , prouver: |
|
||||||||||||||||||||||
Les
exemples du tableau semblent confirmer la propriété: un carré divisé par 4
produit un reste nul ou unité; jamais 2 ou 3. Un nombre
comme 1234 = 308 x 4 + 2 ne peut pas être un carré. 1236 = 309 x 4 pourrait
l'être, mais ne l'est pas. En revanche, 1296 = 324 x 4 est un bon candidat et
1296 = 36². |
|
||||||||||||||||||||||
Cas des nombres pairs Alors n =
2k, le carré est divisible par 4. |
|
||||||||||||||||||||||
Cas des nombres impairs Alors n =
2k+1, le carré est un multiple de 4 plus 1. |
|
||||||||||||||||||||||
Voir Carrés
divisés par 2 et par 4 / Somme
de carrés
|
||
Voici un exemple tout simple qui va servir dans des démonstrations
plus compliquées. Est-ce que l'expression E = 3s² + q² est divisible par 3, sachant que
q ne l'est pas? Non, cette expression n'est pas divisible. D'ailleurs, c'eût été la même chose sans les carrés! |
3s²
0
mod 3 3s²
+ q² q²
mod 3 q²
mod
3 3s²
+ q² q²
mod 3 3s
0
mod 3 3s
+ q q
mod 3 q
mod
3 3s
+ q q
mod 3 |
|
Démonstration de divisibilité |
|
|
Démontrer que |
2047
= 211 – 1 est divisible par 23 |
|
Commençons avec |
25
= 32 |
|
Avec modulo 23 |
25
= 32 9 mod 23 |
|
En élevant au carré |
210 9² mod 23 81 mod 23 12 mod 23 |
|
En multipliant par 2 |
2
. 210 2 . 12 mod 23 211 1
mod
23 |
|
Enfin, en retirant 1 |
211
– 1 1- 1
mod
23 |
|
Résultat final |
211
– 1 0
mod
23 |
|
Nombre parfait ?
210 (211 - 1) n'est donc pas un
nombre parfait.
Car le deuxième terme n'est pas premier. Voir Formule d'Euclide |
||
|
|||
Pour tout nombre impair
x |
x
{1 , 3 , 5 ,
7} mod 8 |
||
Son carré |
x²
{1² , 3² , 5² ,
7²} mod 8 |
||
Calculons |
x²
{1 , 9 , 25 ,
49} mod 8 {1 , 1 , 1 ,
1} mod 8 |
||
Ah! surprise |
x² 1 mod 8 avec x impair |
||
Conclusion
Exemple : 13² = 169 = 21 x 8 + 1 |
|||
|
|||||||||||||||||||
CARRÉ en MODULO 2 Un nombre x divisé par 2 donne soit 0 soit 1 comme reste. Son carré donne les mêmes restes au carré. Il se trouve que ce sont les mêmes valeurs. D'où la propriété:
|
Exemple 42
4 mod 2 16 = 2 x 6 + 4 |
||||||||||||||||||
CUBES en MODULO 3 Même type de commentaire.
|
Exemple 43
4 mod 3 64 = 2 x 30 + 4 |
||||||||||||||||||
Puissance 4 en
MODULO 4 Même type de commentaire.
|
|
|||||||||||||||||||||||||
Puissance 5 en
MODULO 5 Même type de commentaire.
|
Exemple 45
4 mod 5 1
024 = 5 x 204 + 4 |
PUISSANCE p en
MODULO p On aura compris que le truc: ça ne marche qu'avec les nombres
premiers. Et on aura en effet, comme l'a trouvé Fermat: Petit théorème de Fermat
Voir Démonstration
/ Fermat |
|
|
Outils nécessaires
Nombres premiers
entre eux (ou étrangers),
Petit théorème de
Fermat (PTF): xp-1 1 mod p (x et p étrangers),
Propriété
(règle) des multi-modulos.
Montrez que 35 divise toujours 36n – 26n.
|
Voir
Divisibilité
Suite |
Petit théorème de Fermat –
Calculs |
Voir |
Clé de divisibilité, |
Aussi |
Preuve par 9 – Glossaire |
Diconombre |
Référence de cette page |
Arithmétique modulaire et ses applications |