Cours : Arithmétique    Fermer cette fenêtre     Imprimer



Introduction
Division Euclidienne
Systèmes de numérotation
Diviseur et multiple dans
Congruence modulo n
Caractère de divisibilité
PPCM et PGCD
Nombres premiers
Théorème de Bezout
Théorème de Gauss
Cryptologie




1) Introduction :       retour

    1.1) Arithmétique:

L'arithmétique est la branche des mathématiques qui s'intéresse à l'étude des entiers naturels
désigne l'ensemble des entiers naturels c'est à dire l'ensemble {0 ; 1; 2; 3; ...,n,...}
désigne l'ensemble des entiers relatifs c'est à dire  l'ensemble  :
{...,-n,...; -4; -3; -2, - 1; 0 ; 1; 2; 3; ...,m,...}


    1.2) Relation d' ordre et d' équivalence:

  • Une relation est réflexive si tout élément x de E est en relation avec lui même : x x
  • Une relation est antisymétrique signifie que pour x et y appartenant à E si x y et y
    alors x = y
  • Une relation est transitive signifie que pour x et y appartenant à E si x y et y z alors  x z
  • Une relation est symétrique signifie que pour x et y appartenant à E si x y alors y x
  • Une relation est antiréflexive signifie que pour x et y appartenant à E si x y alors x y
    ( pour traduire le fait que x est en relation avec y on note x y )
Définition 1:

Soit E un ensemble, on nomme relation d'ordre sur E toute relation binaire réflexive, antisymétrique et transitive  sur E.

Définition 2:

Soit E un ensemble, on nomme relation d'ordre strict sur E toute relation binaire antiréflexive   et transitive  sur E.

Définition 3:

Soit E un ensemble, on nomme relation d'équivalence sur E toute relation binaire réflexive, symétrique, transitive.

Ordre total, ordre partiel.

Une relation d'ordre sur E est dite relation d'ordre total si deux éléments quelconques de E sont comparables, c'est à dire on a situation x y ou bien y x.  Si par contre il existe au moins un couple (x; y) où x et y ne sont pas comparables la relation  est dite relation d'ordre partiel.






2) Division Euclidienne:       retour

    2.1) Définition:

Propriété:

  Toute partie non vide et majorée de possède un plus grand élément. 

Définition:

Soient a et b deux entiers naturels avec b 0, considérons l'ensemble B des multiples de b inférieurs ou égaux à a : B = {x ; x = kb avec k et x a }
L'ensemble B est non vide puisque 0 B,
B est donc un sous ensemble de non vide et majoré par a .
Par suite B admet un plus grand élément et il existe donc un entier naturel q unique tel que :
bq a < b(q +1) en posant r = a - bq.

On peut dire qu'il existe un couple unique (q, r) d'entiers naturels tel que :
         
  • On dit que q est le quotient entier et r le reste de la division euclidienne de a par b.
  •  Si r = 0 : a est par définition divisible par b, on dit dans ce cas que a est un multiple de b ou que b est un diviseur de a.


    2.2) Exemples:

Exemple 1:


Pour a = , b =  



Exemple 2:

Vous pouvez diviser le nombre par le nombre avec autant de que vous le voulez, il vous suffit pour cela de cliquer autant de fois que vous voulez. 
Cela permet de mettre en évidence par exemple l'aspect périodique de certains rationnels.






3) Systèmes de numérotation :       retour

    3.1) Définition:

Soit a un entier naturel non nul quelconque et b un entier naturel strictement supérieur à 1. 
On admet que l'on peut décomposer le nombre a  de façon unique : 

où les nombres a0, a1, ....ap sont strictement inférieurs à b et le nombre ap non nul. 
Cette décomposition est appelée décomposition du nombre a dans la base b.
La représentation symbolique du nombre a dans la base b nécessite b symboles, appelés chiffres.  Les premiers symboles utilisés sont 0,1,2,..,9 puis les 26 lettres de l'alphabet : A,B, ...,Z . Le nombre a est alors écrit sous la forme  a = ap ....a3a2a1a0 où les ai sont les chiffres.

Quelques cas: 

  • le système binaire de base 2 utilisant 0 et 1 comme  chiffre.
  • le système décimal de base 10 utilisant les chiffres 0 à 9
  • le système hexadécimal de base 16 utilisant les chiffres de 0 à 9 et les lettres de A à F.


    3.2) Exemple:

On veut la représentation du nombre dans la base




4) Diviseur et multiple dans :       retour



    4.1) Définition:

Soient a et b deux entiers relatifs, on dit que b divise a s'il existe un entier relatif k tel que a = kb.

On note: b|a

Remarques:
  • Il est équivalent de dire que a est un multiple b ou b est un diviseur de a
  • La notion de diviseur dans est analogue à celle dans il suffit de compléter les diviseurs avec leurs opposés respectifs.
  • La relation | est une relation d' ordre partiel sur .
    En effet, elle est réflexive, antisymétrique et transitive mais il existe des couples (a, b) non comparables par cette relation. ( 3 ne divise pas 4 et 4 ne divise pas 3)
  • est l'ensemble des multiples de 0, mais 0 n'admet qu'un seul multiple lui-même.


    4.2) Propriétés:

Soient a, b, c trois entiers relatifs et n un entier naturel non nul.
  • 1) a | b et b|c a|c (transitivité )
  • 2) c|a et c|b c divise toute combinaison linéaire à coefficient entier ua + vb de a et b ( u et v sont des entiers relatifs quelconques )

  • 3) a|b |a| |b|
  • 4) (a - b) | (an - bn)
  • 5) si n est impair alors (a + b) | (an + bn)



5) Congruence modulo n :       retour



    5.1) Définition:
Soit n un entier naturel non nul .
Considérons dans la relation notée telle que pour tous entiers relatifs x et y :

x y   (n)  x - y est un multiple de n dans
          k tel que  x - y = kn

On démontre facilement que cette relation est une relation d'équivalence et on appelle cette relation congruence modulo n dans .

Remarque:

       x y   (n) se lit : " x est congru à y modulo n ".




    5.2) Classe modulo n:

On appelle classe modulo n d'un élément x de , l'ensemble des y qui sont congrus à x modulo n.
Sachant que deux nombres x et y sont congrus modulo n si et seulement si, ils ont le même reste dans la division par n, les n-1 restes possibles permettent de définir les n - 1 classes modulo n.


Classes modulo 2:

Dans la division par 2, il y a deux restes possibles : 0 ou 1 , il y a donc deux classes modulo n : la classe des entiers naturels dont le reste est 0 dans la division par 2 et la classe des entiers naturels dont le reste est 1 dans la division par 2, notons (0) la première classe et (1) la seconde, on a :
(0) = {0 ; 2 ; 4 ; 6 ; 8 ; 10 ; 12 ; .....}
(1) = {1 ; 3 ; 5 ; 7 ; 9 ; 11 ; 13 ; .....}

On remarque que = (0) (1)

Classes modulo 3:

on a 3 restes possibles 0, 1 ; 2 donc trois classes :
(0) = {0 ; 3; 6 ; 9 ; 12 ; .......}
(1) = {1; 4 ; 7 ; 10 ; 13 ; ....}
(2) = {2; 5 ; 8 ; 11; 14; .....}
on remarque que = (0) (1) (2)

Classes modulo 4:

(0) = {0 ; 4; 8 ; 12 ; 16 ; ...}
(1) = {1 ; 5; 9; 13; 17 ; ...}
(2) = {2 ; 6 ; 10; 14; 18 ; ...}
(3) = {3 ; 7 ; 11; 15 ; 19 ; ....}

On remarque que = (0) (1) (2) (3)

Plus généralement, il y a (n - 1) classes modulo n qui forment une partition de





    5.3) Propriétés:

Pour que deux entiers relatifs x et y soient congrus modulo n dans il faut et il suffit qu'ils aient le même reste dans la division euclidienne par n.

  a-t-on ( ) ?




Propriétés de la congruence modulo n dans

Pour pour entiers relatifs x1, x2, y1, y2 et tout entier naturel non nul l on a : 





Conséquence : caractères de divisibilité d'un nombre

Soit a un entier naturel dont la représentation symbolique dans le système décimal est : a = ap ....a3a2a1a0 .


En utilisant les propriétés précédentes on obtient :



    5.4) Tables de congruence:
de la division de par
pour n allant de à par pas de




    5.5) Addition modulo n:

Soient a et b deux entiers naturels et (a) et (b) leurs classes modulo n respectives. On définit la somme module n de a et b comme étant la classe (a + b) de leur somme arithmétique a + b .

Exemple:

7 + 11 = 18 (somme arithmétique )
18 0 modulo 3
La somme modulo 3 de 7 et 11 est égale à 0 .

Addition modulo 2

(0) = {0 ; 2 ; 4 ; 6 ; .......}
(1) = {1; 3; 5 ; 7 ; ........}


On peut dresser une table d'addition modulo 2 :




6) Caractère de divisibilité:       retour

  • Pour qu'un entier soit divisible par 2, il faut et il suffit que le dernier chiffre de sa représentation décimale soit 0, 2, 4, 6, 8.

  • Pour qu'un entier soit divisible par 5, il faut et il suffit que le chiffre des unités de sa représentation décimale soit 0 ou 5.

  • Pour qu'un entier soit divisible par 4, il faut et il suffit que le nombre formé par les deux derniers chiffres soit divisible par 4.

  • Pour qu'un entier soit divisible par 25, il faut et il suffit que le nombre formé par les deux derniers chiffres soit divisible par 25.

  • Pour qu'un entier soit divisible par 8, il faut et il suffit que le nombre formé par les trois derniers chiffres soit divisible par 8.

  • Pour qu'un entier soit divisible par 125, il faut et il suffit que le nombre formé par les trois derniers chiffres soit divisible par 125.

  • Pour qu'un entier soit divisible par 3 , il faut et il suffit que la somme des chiffres qui le composent soit divisible par 3.

  • Pour qu'un entier soit divisible par 9 , il faut et il suffit que la somme des chiffres qui le composent soit divisible par 9.

  • Pour qu'un entier soit divisible par 11,il faut et il suffit que la différence de la somme des chiffres de rang impair et de la somme des chiffres de rangs pair ( en partant  partant de la droite ) soit divisible par 11.






7) PPCM et PGCD :       retour



    7.1) Définition:
Pour comprendre la définition de diviseurs, multiples  dans , prendre deux entiers naturels strictement positifs et puis la liste des diviseurs de ces deux nombres et la listes des premiers multiples :

  • Le Pgcd de nombres, c'est le plus grand diviseur commun de ces nombres.
  • Le Ppcm de nombres, c'est le plus petit multiple commun de ces nombres.



    7.2) Algorithme d' Euclide de recherche du PGCD:
Soient a = et b = deux nombres entiers.
On veut déterminer en utilisant l'algorithme d'Euclide, le PGCD de a et de b.

Principe:

Cet algorithme permet de déterminer le PGCD de 2 nombres a et b en effectuant plusieurs divisions euclidiennes ( division avec reste ) à chaque étape le diviseur est remplacé par le reste et le dividende par le diviseur.
On arrête les divisions quand le reste est nul, le dernier diviseur est le PGCD.









8) Nombres premiers :       retour



    8.1) Définition:
Par définition, est premier tout entier naturel qui admet deux diviseurs positifs distincts exactement : 1 et lui-même .


    8.2) Propriété:
  • Tout entier naturel n au moins égal à 2 admet un diviseur premier.
  • Si n n'est pas premier alors il admet un diviseur premier compris entre 2 et

Le crible d'Eratosthène permet de dresser la liste des nombres premiers inférieurs à un entier naturel n donné.

des nombres premiers jusqu'à .






    8.3) Le crible d' Eratosthène:
On veut déterminer avec le crible d'Erathosthène les nombres premiers inférieurs ou égaux à .
Choisir un nombre de préférence supérieur à 10, et cliquer sur étapes pour obtenir les étapes suivantes,
quand plus rien ne se produit, vous avez déterminer tous les nombres premiers. Pour choisir un autre nombre il faut impérativement .

Clique sur :





    8.4) Nombres premiers entre eux :

Deux entiers sont premiers entre eux si et seulement si leurs seuls diviseurs communs sont 1 et -1 :

Exemple:
  • 45 et 26 sont premiers entre eux.
  • 12 et 35 sont premiers entre eux.
  • 45 et 35 ne sont pas premiers entre eux. En effet : 5 divise 45 et 35.

Attention:
Deux nombres premiers distincts sont premiers entre eux, mais la réciproque est fausse.





    8.5) Décomposition d'un nombre entier en un produit de facteurs premiers:

Théorème fondamental:

Tout entier naturel supérieur ou égal à 2 est décomposable en un produit de facteurs premiers. Cette décomposition est unique.

Exemple:

Choisir un nombre , on obtient sa décomposition en produit de facteurs premiers :
Clique sur :






9) Théorème de Bezout :       retour



    9.1) Identité de Bezout:
Soient a et b deux entiers relatifs et d leur pgcd alors il existe deux entiers u et v tels que : au + bv = d.



    9.2) Résolution d'une équation diophantienne:

Soient a, b et c des entiers, et d le pgcd de a et b, alors:
l'équation au + bv = c admet des solutions entières si et seulement si c est un multiple de d



    9.3) Théorème de Bezout:

Soient a et b deux entiers relatifs non nuls.
a et b sont premiers entre eux si, et seulement si, il existe deux entiers u et v tels que au + bv = 1.


Exemples de résolutions:

On veut déterminer les couple(s) éventuels (u, v) solutions  de l'équation :
au + bv = c ( avec a > b )
et a = , b = et c =

   






10°) Théorème de Gauss :       retour



    10.1°) Le Théorème:
Soient a, b et c 3 entiers relatifs non nuls.
Si a divise le produit bc et si a est premier avec b, alors a divise c.



    10.2°) Conséquences:

  • Si deux entiers a et b premiers entre eux divisent un entier c, alors ab divise c.
  • Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.



    10.3) Application à la résolution d'une équation au + bv = c :
avec 
a = , b = et c =
On connaît une solution particulière de cette équation :
        (u0 ; v0 ) =( ; ) .
On cherche toutes les solutions .





11°) Cryptologie :       retour



    11.1°) Définitions:



    11.1°) Classification des systèmes de chiffrements: