Problèmes d'arithmétique sur la divisibilité

Calculatrice interdite !

(sauf pour calculer les racines carrées de l'exercice 2)

Un multiple

On dit que $a$ est un mutliple de $b$ si et seulement si :

$$\exists q \in \mathbb{Z}, \ a = bq $$

Un diviseur

On dit que $b$ est un diviseur de $a$ si et seulement si :

$$\exists q \in \mathbb{Z}, \ \frac{a}{b} = q $$

Ce qui revient à la définition précédente.

Il existe alors ce lien entre les deux :

$a$ est un mutliple de $b$ $\Longleftrightarrow$ $b$ est un diviseur de $a$

Un nombre parfait

Un nombre parfait est la somme de l'ensemble de ces diviseurs (excepté lui-même).

Démontrer que le nombre 28 est parfait.

Les diviseurs de 28 sont :

$$ \mathcal{D} = \Bigl \{ 1, 2 , 4, 7, 14, 28 \Bigr \} $$

Soit leur somme exceptée 28 vaut :

$$ S = 1 + 2 + 4 + 7 + 14 = 28 $$

Déterminer si un nombre est premier

Un nombre premier

Un nombre premier est un entier qui n'a que deux diviseurs, lui-même et 1.

Exemples :2, 13 et 37 sont des nombres premiers.

À l'aide de ce théorème :

Tout entier naturel $n \geqslant 4 $ non premier possède au moins un diviseur strict $d_0 $ tel que $ d_0 \leqslant \sqrt{n} $.

Le nombre 137 est-il premier ?

$$ \sqrt{137} \approx 11.7 $$

Donc au mieux, on cherchera au moins un diviseur inférieur ou égal à 11 pour montrer qu'il ne l'est pas.

Il est impair donc aucun de ces diviseurs n'est un nombre pair.

Ensuite, la somme des chiffres qui le composent n'est pas un multiple de 3, on peut donc éliminer en même temps 6 et 9.

De même, il n'est pas divisible par 5 de manière évidente.

Enfin, en utilisant la méthode des tranches, il n'est pas non plus un multiple de 7 ni de 11.

Il est alors bien un nombre premier.

Divisibilité d'un nombre

Le nombre 327 est-il divisible par 3 ?

Un nombre est divisible par 3 si la somme des chiffres qui le composent est divisible par 3.

$$ 3 + 2 + 7 = 12 $$

Comme 12 est un multiple de 3, le nombre 327 l'est aussi. Donc oui.

Le nombre 476 est-il divisible par 4 ?

On applique la méthode des tranches :

$$ 476 \textcolor{#6187B2}{ - 400} = 76 $$

$$ 476 \textcolor{#6187B2}{ - 40} = 36 $$

Comme 36 est un multiple de 4, alors le nombre 476 aussi. La réponse est oui.

Le nombre 252 est-il divisible par 9 ?

Un nombre est divisible par 9 si la somme des chiffres qui le composent est divisible par 9.

$$ 2 + 5 + 2 = 9 $$

Le nombre 252 est bien divisible par 9.

Le nombre 1189 est-il divisible par 7 ?

On applique la méthode des tranches :

$$ 1189 \textcolor{#6187B2}{ - 700} = 489 $$

Et on peut même dépasser et alors dans les entiers négatifs.

$$ 489 \textcolor{#6187B2}{ - 490} = -1 $$

Comme $-1$ n'est pas un multiple de 7, alors le nombre 1189 ne l'est pas. La réponse est non.

Le nombre 289 est-il divisible par 17 ?

Faisons la division :

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\Large\frown}{28} }9 $$	$$ 17 $$
$$ \hspace{-0.6em } -17 \hspace{0.2em} . $$	$$ \textcolor{#4A8051}{17} $$
$$ \hspace{-0.4em } = \overset{\LARGE\frown}{\textcolor{#A16632}{11}9} $$
$$ \hspace{-0.4em }-119 $$
$$ \hspace{-0.4em } = \hspace{0.8em } \textcolor{#A16632}{0} $$

La division tombe juste, donc oui.

L'algorithme d'Euclide

Le PGCD de deux entiers naturels

Le PGCD de deux nombres est leur diviseur commun le plus élevé.

Et avec l'algorithme d'Euclide, c'est aussi le dernier reste non nul des divisions euclidiennes successives, en démarrant par celle de $a$ par $b$.

Déterminer alors, à l'aide de l'algorithme d'Euclide, les PGCD suivants.

$$ PGCD(360,240) $$

Faisons les divisions successives :

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{360} } $$	$$ 240 $$
$$ \hspace{-0.6em } -240 $$	$$ \textcolor{#4A8051}{1} $$
$$ \hspace{-0.8em } = \textcolor{#A16632}{120} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{240} } $$	$$ 120 $$
$$ \hspace{-0.6em } -240 $$	$$ \textcolor{#4A8051}{2} $$
$$ \hspace{-0.8em } = \hspace{0.8em } \textcolor{#A16632}{0} $$

Alors,

$$ PGCD(360,240) = 120 $$

$$ PGCD(432,252) $$

Faisons les divisions successives :

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{432} } $$	$$ 252 $$
$$ \hspace{-0.6em } -252 $$	$$ \textcolor{#4A8051}{1} $$
$$ \hspace{-0.8em } = \textcolor{#A16632}{180} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{252} } $$	$$ 180 $$
$$ \hspace{-0.6em } -180 $$	$$ \textcolor{#4A8051}{1} $$
$$ \hspace{-0.8em } = \hspace{0.4em } \textcolor{#A16632}{72} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{180} } $$	$$ 72 $$
$$ \hspace{-0.6em } -144 $$	$$ \textcolor{#4A8051}{2} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \textcolor{#A16632}{36} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{72} } $$	$$ 36 $$
$$ \hspace{-0.4em } -72 $$	$$ \textcolor{#4A8051}{2} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \textcolor{#A16632}{0} $$

Alors,

$$ PGCD(432,252) = 36 $$

$$ PGCD(1800,62) $$

Faisons les divisions successives :

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{1 \ 80}0 } $$	$$ 62 $$
$$ \hspace{-0.6em } -1 \ 24 \ . $$	$$ \textcolor{#4A8051}{29} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \overset{\LARGE\frown}{\textcolor{#A16632}{56}0 } $$
$$ \hspace{0em } -558 $$
$$ \hspace{-0.8em } = \hspace{1.6em } \textcolor{#A16632}{2} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{62} } $$	$$ 2 $$
$$ \hspace{-0.6em } -62 $$	$$ \textcolor{#4A8051}{31} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \textcolor{#A16632}{0} $$

Alors,

$$ PGCD(1800,62) = 2 $$

$$ PGCD(137,51) $$

Faisons les divisions successives :

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{137}} $$	$$ 51 $$
$$ \hspace{-0.6em } -102 $$	$$ \textcolor{#4A8051}{2} $$
$$ \hspace{-0.8em } = \hspace{0.4em }\textcolor{#A16632}{35} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{51} } $$	$$ 35 $$
$$ \hspace{-0.4em } -35 $$	$$ \textcolor{#4A8051}{1} $$
$$ \hspace{-0.8em } = \hspace{0.2em } \textcolor{#A16632}{16} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{35} } $$	$$ 16 $$
$$ \hspace{-0.4em } -32 $$	$$ \textcolor{#4A8051}{2} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \textcolor{#A16632}{3} $$

$$ \hspace{0.8em } \textcolor{#6187B2}{ \overset{\LARGE\frown}{16} } $$	$$ 3 $$
$$ \hspace{-0.4em } -15 $$	$$ \textcolor{#4A8051}{5} $$
$$ \hspace{-0.8em } = \hspace{0.6em } \textcolor{#A16632}{1} $$

Alors,

$$ PGCD(137,51) = 1 $$

Dans ce cas, on dit que les nombres sont premiers entre eux (ou "étrangers").

Problèmes

Démontrer les propositions suivantes :

Si $(n + 3)$ est un multiple de 7, alors $(n^2 + 5)$ l'est aussi.

Si $(n + 3)$ est un multiple de 7, alors :

$$ \exists q \in \mathbb{Z}, \enspace n + 3 = 7q $$

$$ n = 7q - 3$$

On peut maintenant mettre $n$ au carré :

$$ n^2 = (7q - 3)^2 $$

$$ n^2 = (7q)^2 - 2 \times 7q \times 3 + 3^2 $$

$$ n^2 = 49q^2 - 42q + 9 $$

On ajoute maintenant 5 de chaque côté, puis :

$$ n^2 \textcolor{#6187B2}{+ 5} = 49q^2 - 42q + 9 \textcolor{#6187B2}{+ 5} $$

$$ n^2 + 5 = 49q^2 - 42q + 14 $$

On peut alors tout factoriser par 7 :

$$ n^2 + 5 = 7 \underbrace{(7q^2 - 6q + 2)} _\text{$A \ \in \ \mathbb{Z}$} $$

Alors, le nombre $(n + 3)$ est bien un multiple de 7.

Si $a$ est un multiple de 2, et $b$ est un multiple de 3, alors $ \Bigl[(a + b)^3 - b^3 \Bigr] $ est un multiple de 2.

Si $a$ est un multiple de 2, et $b$ est un multiple de 3, alors :

$$ \exists (q, p) \in \hspace{0.03em} \mathbb{Z}^2, \enspace \Biggl \{ \begin{gather*} a = 2q \\ b = 3p \end{gather*} $$

Alors,

$$ (a+b)^3 - b^3 = (2q + 3p)^3 - (3p)^3 $$

On utilise la formule :

$$ (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 $$

$$ (a+b)^3 - b^3 = (2q)^3 + 3 \times (2q)^2 \times 3p + 3 \times 2q \times (3p)^2 + (3p)^3 - (3p)^3 $$

$$ (a+b)^3 - b^3 = (2q)^3 + 3 \times (2q)^2 \times 3p + 3 \times 2q \times (3p)^2 $$

$$ (a+b)^3 - b^3 = 8q^3 + 36 q^2p + 54 q p^2 $$

On peut alors tout factoriser par 2 :

$$ (a+b)^3 - b^3 = 2 \underbrace{(4q^3 + 18q^2p + 27qp^2)} _\text{$A \ \in \ \mathbb{Z}$} $$

Alors, le nombre $\Bigl[(a + b)^3 - b^3 \Bigr]$ est bien un multiple de 2.