Arithmétique entière.

• La division euclidienne des entiers (comme à l'école primaire): en C on utilise % (modulo) et / (quotient euclidient). Diviseurs d'un entier: $d$ divise $a$ si le reste de $a$ par $d$ est 0.
• Les nombres premiers: ce sont des entiers dont les seuls diviseurs sont 1 et lui-même. Programmation d'un test de primalité trivial.
• PGCD de 2 entiers $a$ et $b$ (plus grand diviseur commun de $a$ et $b$). On dit que $a$ et $b$ sont premiers entre eux si le PGCD de $a$ et $b$ est égal à 1. Propriété: le PGCD de $a$ et $b$ est égal au PGCD de $b$ et de $r$ le reste de la division euclidienne de $a$ par $b$. L'algorithme d'Euclide consiste à calculer la suite des restes successifs, le PGCD est le dernier reste non nul.
  Programmer l'algorithme d'Euclide.
• Résolution de l'équation de Bézout: on cherche $u$ et $v$ entiers tels que $au+bv=d$ où $d$ est le PGCD de $a$ et $b$. L'algorithme est une variante de l'algorithme d'Euclide: on écrit $a$, $b$ et les restes successifs comme combinaison linéaire de $a$ et $b$.
  Notons $[ D \ U \ V ]$ pour signifier que $D=aU+bV$. On a alors $[a \ 1 \ 0]$ et $[b \ 0 \ 1]$. Si la division euclidienne de $a$ par $b$ est $a=bq+r$ alors $a-bq=r$ donc la ligne $[ r \ ? \ ? ]$ s'obtient en retranchant $q$ fois la ligne $[b \ 0 \ 1]$ à la ligne $[a \ 1 \ 0]$. On continue jusqu'à obtenir la ligne $[d \ u \ v ]$.
  Exemple: le pgcd de 25 et 15 est 5. Les deux premières lignes sont ici $[25 \ 0 \ 1]$ et $[15 \ 1 \ 0]$. On a $25=15\times 1+10$ donc $q=1$, on retranche donc à a ligne $[25 \ 1 \ 0]$ 1 fois la ligne $[15 \ 0 \ 1]$ ce qui donne $[10 \ 1 \ -1]$. Puis on divise 15 par 10: $15=10 \times 1 + 5$ donc $q=1$ à nouveau et la ligne obtenue est $[5 \ -1 \ 2]$ donc $u=-1$ et $v=2$.
  Programmation de l'algorithme de Bézout.