Spécialité / Arithmetique

En arithmétique, la science des nombres, on travaille toujours avec des entiers relatifs dans $\mathbb{Z}$.

Divisibilité

Diviseurs

• a est divisible par b
• a est un multiple de b
• b est un diviseur de a
• b divise a, noté $\;b\,|\,a\;$ (le nombre le plus grand est toujours à droite)

Division euclidienne

• Le couple (q ; r) est unique
• q est le quotient de la division euclidienne de a par b
• r est le reste de la division euclidienne de a par b

PGCD (Plus Grand Commun Diviseur)

p divise a et b, et c’est le plus grand des diviseurs communs

Il existe a’ et b’ premiers entre eux tels que : $a=pa'$ et $b=pb'$

Exemple: PGCD(10 ; 12) = 2

Notation Base 10

$\overline{a0b} \to a.10^2+b$

$\overline{a00b} \to a.10^3+b$

$\overline{4003} \to 4.10^3+3$

Nombres premiers

Les nombres premiers ont exactement deux diviseurs positifs : 1 et eux-mêmes.

1 n’est pas premier, car il n’a qu’un diviseur (1).

Liste des premiers nombre premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, etc.

Décomposition

a, entier naturel, peut se décomposer en un produit de nombre premiers.

Exemple de décomposition progressive :
$48 = 6 \times 8$
$48 = 2 \times 3 \times 2^3$
$48 = 2^4 \times 3$

Nombres premiers entre eux

Exemple : 27 et 8 sont premiers entre eux

Théorème de Gauss

Si $a \, | \, bc$ et a et b premiers entre eux alors $a\,|\,c$

Théorème de Bezout

a et b sont premiers entre eux ssi $\exists (u,v) \in \mathbb{Z}$ tel que $au+bv=1$

Congruence

Modulo

• a est congru à b modulo n
• $a=kn+b$
• a-b est multiple de n
• a et b ont le même reste dans la division euclidienne par n

Opérations avec $\equiv$

Pour $a \equiv b \; [n]$, on a les mêmes opérations qu’avec égalité (k entier) :

• $a+k \equiv b+k \; [n]$
• $ka \equiv kb \; [n]$
• $a^k \equiv b^k \; [n]$

Pour $a \equiv b \; [n]$ et $a' \equiv b' \; [n]$ :

• $a+a' \equiv b+b' \; [n]$
• $aa' \equiv bb' \; [n]$
• $a^k \equiv b^k \; [n]$