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$.