Comment transformer une divisibilité en preuve ?

Pour des entiers a et b, a est multiple de b s’il existe un entier k tel que a = bk. La même égalité dit que b divise a, noté b ∣ a. Ainsi 12 = $\text{4×3}$ prouve à la fois que 12 est multiple de 4 et que 4 divise 12. Le nombre k est le témoin.

Ne permute pas les rôles : 3 divise 12, mais 12 ne divise pas 3. Zéro est multiple de tout entier car 0 = $\text{b×0}$ ; tout entier non nul divise 0. Écrire une division exige en revanche un diviseur non nul. Dans $\text{ℕ}$, les multiples de b se listent $\text{b×0}$, $\text{b×1}$, $\text{b×2}$, … ; dans $\text{ℤ}$, les témoins peuvent aussi être négatifs.

Pour a > 0 et une borne b, la division euclidienne donne b = $\text{aq+r}$ avec 0 ≤ r < a. Le plus grand multiple de a inférieur ou égal à b est aq = $\text{b−r}$. Par exemple 53 = $\text{7×7+4}$ : le résultat est 49.

Un balayage ajoute a jusqu’à dépasser b ; le quotient q = ⌊b/a⌋ donne directement la réponse. Compare les deux méthodes et contrôle trois propriétés : le résultat est divisible par a, il ne dépasse pas b, et le multiple suivant dépasse b. Si les données peuvent être négatives, annonce les conventions et utilise la partie entière plutôt qu’une troncature vers zéro.

Un nombre premier est un naturel supérieur à 1 qui possède exactement deux diviseurs positifs : 1 et lui-même. Donc 1 n’est pas premier. Si n = uv est composé et u > $\text{√n}$ ainsi que v > $\text{√n}$, alors uv > n, contradiction : au moins un facteur est inférieur ou égal à $\text{√n}$.

Pour tester n, élimine 2 puis essaie les nombres premiers jusqu’à $\text{√n}$. Pour 97, $\text{√97}$ < 10 : il suffit de tester 2, 3, 5 et 7. Aucun ne divise 97, donc 97 est premier. Essayer seulement quelques nombres sans annoncer la borne ne constitue pas une preuve.

Un entier n est pair s’il existe k ∈ $\text{ℤ}$ tel que n = 2k. Il est impair s’il existe k ∈ $\text{ℤ}$ tel que n = $\text{2k+1}$. Ces formes valent aussi pour les négatifs : $\text{−3}$ = $\text{2×(−2)+1}$.

La variable représente tous les cas à la fois. Deux impairs consécutifs s’écrivent $\text{2k+1}$ et $\text{2k+3}$ ; un entier et son suivant s’écrivent n et $\text{n+1}$. Avant de résoudre, vérifie que la forme décrit exactement les objets demandés et qu’elle n’oublie aucun entier possible.

Si x et y sont multiples de a, il existe des entiers k et ℓ tels que x = ak et y = aℓ. Alors $\text{x+y}$ = $\text{ak+aℓ}$ = $\text{a(k+ℓ)}$. Comme $\text{k+ℓ}$ est entier, $\text{x+y}$ est multiple de a. Le dernier facteur fournit le nouveau témoin.

Si n est impair, n = $\text{2k+1}$. Alors $n^2$ = ${\text{(2k+1)}}^2$ = $\text{4}{k}^2\text{+4k+1}$ = $\text{2(2}{k}^2\text{+2k)+1}$. Le nombre entre parenthèses est entier : $n^2$ est impair. Tester 3, 5 et 7 peut suggérer la propriété, mais seule la variable arbitraire prouve tous les cas.

Une fraction $\frac{p}{q}$ avec q ≠ 0 est irréductible lorsque p et q n’ont aucun diviseur positif commun autre que 1, donc $\text{PGCD(|p|,|q|)=1}$. Pour $\frac{20}{45}$, le PGCD vaut 5 et $\frac{20}{45}$ = $\frac{4}{9}$. On place habituellement le signe au numérateur et on garde le dénominateur positif.

L’algorithme d’Euclide répète les restes : 45 = $\text{2×20+5}$ puis 20 = $\text{4×5+0}$, donc le dernier reste non nul est 5. Divise numérateur et dénominateur par le même nombre : la valeur ne change pas. Contrôle ensuite que le nouveau PGCD vaut 1 et que le dénominateur n’est jamais devenu nul.