Si on prend deux nombres \(a,b\in \mathbb{Z}\text{,}\) on peut les additionner, les soustraire et les multiplier et le résultat sera encore un entier. La division est la seule des quatre opérations élémentaires qui n’est pas garantie de rester un entier. C’est peut-être ce qui en fait une opération si riche et si intéressante. Quand est-ce que la division de deux nombres va produire un entier? Comment le vérifier?
Dans cette section, on rappelle la notion de division entière, quotient et reste, on définit le plus grand commun diviseur et le plus petit commun multiple de deux nombres naturels, on montre l’algorithme d’Euclide pour calculer le plus grand commun diviseur.
Soit \(a,b\) deux entiers. Si on divise \(a\) par \(b\text{,}\) le résultat peut être un entier, comme par exemple avec \(8/4=2\text{,}\) un rationnel, avec en exemple \(1/2\) ou même non défini, si on divise par \(0\text{.}\) On expliquera prochainement la raison pour laquelle le fait que la division par \(0\) est non définie est une bonne chose. Dans le cas où \(a/b\in \mathbb{Z}\text{,}\) donc où le résultat de la division produit un entier, on dit que \(b\) divise \(a\text{,}\) et on écrit \(b| a\) (la barre étant verticale et non pas oblique comme pour l’opérateur de division).
Soit \(a,b\in \mathbb{Z}\) avec \(b\neq 0\text{.}\) On dit que “\(b\) divise \(a\)” et on écrit \(b| a\) si le résultat \(a/b\) est un entier. On note que les quatre conditions suivantes sont équivalentes:
Quand on écrit \(b| a\text{,}\) c’est soit vrai, soit faux selon \(a,b\text{.}\) On a donc une proposition. Pour écrire la négation de cette proposition, on peut utiliser la notation \(b\nmid a\) pour dire que \(b\) me divise pas \(a\text{.}\)
Le fait que le nombre est négatif ne pose pas de problème. On peut utiliser n’importe quelle des définitions équivalentes, par exemple \(48\) est un multiple de \(-6\text{,}\) spécifiquement \(-8\) fois \(-6\) et donc \(-6| 48\) est vraie.
Puisque \(n^2=n\times n\text{,}\) on conclut que \(n\) est un facteur de \(n^2\) et donc que \(n| n^2\) peu importe la valeur de \(n\) non nulle. La proposition est vraie.
Si on peut montrer une valeur de \(n\) qui ne respecte pas la condition, alors la proposition sera fausse. Par exemple, si \(n=2\text{,}\) c’est faux de dire que \(2^2| 2\) puisque \(2/4=1/2\) et ce n’est pas un entier. Donc la proposition est fausse.
Si on arrive à trouver une valeur, la proposition d’existence sera vérifiée. En prenant \(n=1\text{,}\) on observe que \(1^2| 1\) et donc la proposition est vraie.
Les valeurs numériques de l’exemple précédent étaient relativement petites qu’on savait si la relation de divisibilité était vraie assez facilement. Par contre, si on se demande est-ce que \(123\) divise \(881123\text{,}\) alors là ce n’est plus aussi évident. Comment peut-on procéder? On veut trouver un multiple de \(123\) qui donne \(881123\) ou montrer que c’est impossible. On peut essayer de procéder par étranglement. Si on fait \(123\times 10000=1230000\text{,}\) on obtient une valeur trop grande, alors que si on fait \(123\times 1000=123000\text{,}\) on obtient une valeur trop petite. Si un multiple existe, il se trouve nécessairement entre \(1000\) et \(10000\text{.}\) On essaie \(123\times 5000=615000\text{,}\) qui est encore trop petit. Avec \(123\times 7500=922500\text{,}\) on est maintenant trop haut. Le multiple s’il existe se retrouve donc entre \(5000\) et \(7500\text{.}\) On peut continuer de couper la poire en deux comme cela pendant un certain temps et éventuellement, on arrive à \(123\times 7163=881049\) qui est plus petit et \(7164\times 123=881172\) qui est trop grand. On conclut donc que \(881123\) n’est pas un multiple de \(123\) et donc \(123 \nmid 881123\text{.}\)
En prenant \(123\times 7163=881049\text{,}\) on remarque qu’on est à \(74\) entiers de la cible. On peut donc écrire \(881123=123\times 7163+74\text{.}\) Il se trouve qu’on peut généraliser se résultat pour obtenir la notion bien connue de division.
Soit \(a,b\in \mathbb{Z}\) avec \(b\neq 0\text{.}\) Alors il existe une paire d’entiers unique \(q,r\) avec \(0\leq r\leq \lvert b\rvert\) pour lesquels
Pour trouver \(q\) et \(r\text{,}\) on peut procéder comme dans le paragraphe précédant la proposition 3.2.3, ou encore utiliser la méthode pour diviser enseignée au primaire.
Sage est capable de calculer facilement les entiers \(q\) et \(r\) de la proposition 3.2.3 grâce à deux opérateurs spéciaux. Si a/b produit la division usuelle, donnant un nombre rationnel lorsque \(b\nmid a\text{,}\) l’opération a//b elle produit le quotient \(q\) dans l’expression \(a=bq+r\text{.}\) Pour obtenir le reste, il faut utiliser a%b. La cellule ci-dessous illustre ces opérations.
À remarquer que lorsque \(b\) est négatif, Sage retourne un reste négatif alors que dans la proposition 3.2.3, on mentionne que le reste doit satisfaire \(0\leq r< \lvert b \rvert\text{.}\) Il existe tout de même un autre entier qui satisfait cette relation, qui entrainera une valeur du quotient différente.
Sous-section3.2.2Retour sur la conversion à partir de la base dix
Dans la section précédente, on a utilisé une méthode similaire à l’étranglement pour convertir un nombre de la base décimale aux bases binaire et hexadécimale. On peut utiliser l’écriture sous forme quotient et reste pour trouver les chiffres de l’écriture dans la nouvelle base. On montre l’idée générale avec un exemple concret, qu’on pourra généraliser facilement par la suite. On considère l’écriture de \(187\) dans la base deux, établie à l’exemple 3.1.5. On suppose que l’écriture de \(187\) a \(n\) chiffres. On remarque que
Puisque \(q=d_n2^{n-1}+d_{n-2}2^{n-1}+\cdots d_12^0\in \mathbb{Z}\text{,}\) on voit que \(187=2q+d_0\) et donc, selon la proposition 3.2.3, le premier chiffre de l’écriture de \(187\) en binaire correspond au reste de la division de \(187\) par \(2\text{.}\) Ensuite pour trouver \(d_1\text{,}\) on répète avec le quotient \(q\text{.}\) Dans le cas de \(187\text{,}\) on a \(q=93\) et \(d=d_0=1\text{.}\) En continuant,
on peut trouver \(d_1=1\) et le prochain quotient égal à \(46\text{.}\) Avec cela, on obtient \(d_2=0\text{,}\) amenant le quotient suivant à \(23\text{.}\) On obtient \(d_3=1\) et le quotient suivant vaut \(11\text{.}\) On continue avec \(d_4=1\) pour un quotient de \(5\text{,}\) puis d_5=1 pour un quotient de \(2\text{,}\)\(d_6=0\) pour un quotient de \(1\) et finalement, \(d_7=1\) pour un quotient de \(0\text{.}\) On peut donc écrire \(187=10111011_2\text{.}\)
Ce qui est bien avec le binaire, c’est que le reste se déduit facilement avec la parité du nombre divisé. Si celui-ci est pair, le reste est de \(0\) et s’il est impair, le reste est de \(1.\) On peut simplifier la procédure en écrivant les quotients et les restes dans un tableau. La colonne des restes correspond à l’écriture binaire du nombre, les nombres de droite à gauche se trouvant de haut en bas de la colonne. Afin d’illustrer, la conversion du nombre \(101=1100101_2\text{,}\) aussi de l’exemple 3.1.5 est donnée dans la table 3.2.5.
Un concept important en théorie des nombres est celui du plus grand commun diviseur, ou pgcd. Le nom est assez évocateur de ce qu’il représente, mais voici une définition formelle.
Soit \(a,b\in \mathbb{Z}\) avec \(\lvert a\rvert +\lvert b\rvert\neq 0\) (les nombres ne sont pas tous les deux nuls). Le plus grand commun diviseur de \(a,b\text{,}\) noté \(\pgcd{(a,b)}\text{,}\) est un entier \(d\) qui satisfait les trois propriétés suivantes:
On peut trouver le \(\pgcd\) de deux nombres en donnant la liste de tous leurs diviseurs et en prenant le plus grand qu’ils ont en commun. Pour de petits nombres, cette approche est viable, mais pour de plus grands nombres, cela risque d’être inefficace et peu pratique. En fait, factoriser de très grands nombres est une opération difficile. Une grande partie de la sécurité informatique repose sur le fait qu’un même un puissance ordinateur ne peut pas factoriser facilement de très grands nombres. L’algorithme d’Euclide fournit une méthode plus efficace pour calculer le \(\pgcd\) de deux nombres. Avec de très grands nombres, ça peut être long, mais ça utilise des opérations qu’un ordinateur effectue facilement.
L’algorithme suivant retourne un couple \(q,r\) représentant le quotient et le reste de la division \(a/b\text{,}\) mais il est incomplet. Pour chacun des quatre endroits écrits “ÀCOMPLÉTER”, écrire les instructions pour que l’algorithme fonctionne. Il est possible de le tester à même la cellule.
def divisionEuclidienne(a, b):
#Une algorithme qui retourne (q,r) la forme quotient reste de a/b: a=bq+r
if :#ÀCOMPLÉTER1
print('Le quotient est non défini')
elif a == 0:
return #ÀCOMPLÉTER2
else:
s = b / abs(b) # le signe de b
q=0
r =a
if a > 0:
while r - abs(b) >= 0:
q = q + s
r = #ÀCOMPLÉTER3
return q, r
else: #a <0
while r < 0:
q = q - s
r = #ÀCOMPLÉTER4
return q, r
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
Donner une explication intuitive du fait que si \(a,b\in \mathbb{N}\) sont des naturels non nuls et que \(\pgcd{(a,b)}=d\text{,}\) alors \(\pgcd{\left(\frac{a}{d},\frac{b}{d}\right)}=1\text{.}\)
Cela implique que \(a=q_1(dc)\) et \(b=q_2(dc)\text{,}\) c’est-à-dire que \((dc)|a\) et \((dc)|b\text{.}\) Ainsi, \(dc\) divise \(a\) et \(b\text{,}\) et \(dc > d\text{.}\) Or, cela contredit le fait que, \(d=\pgcd{(a,b)} \text{,}\) car \(d\) est le plus grand diviseur commun à \(a\) et \(b\text{.}\)
L’algorithme d’Euclide permet de trouver le \(\pgcd\) d’entiers strictement positifs. On peut toutefois facilement étendre la notion aux entiers quelconques.
Posons \(d=\text{pgcd}(a,0)\text{.}\) On sait que pour tout \(a \in \Z\text{,}\) si \(a\neq 0\text{,}\) alors \(a|0\) et \(a|a\text{.}\) Ainsi, par définition de \(d\text{,}\) on a que \(a\leq d\text{.}\)
Posons \(d_1=\text{pgcd}(a,b)\) et \(d_2=\text{pgcd}(|a|,b)\text{.}\) Ainsi, on sait que \(d_1|a\) et \(d_1|b\text{,}\) alors que \(d_2|(|a|)\) et \(d_2|b\text{.}\)
On a donc \(a=d_1q_1\) et \(|a|=-a=d_2q_2\) pour \(q_1,\ q_2\ \in \Z\text{.}\) En multipliant les deux égalités par \(-1\text{,}\) on obtient \(-a=|a|=d_1(-q_1)\) et \(a=d_2(-q_2)\text{,}\) c’est-à-dire que \(d_1|(|a|)\) et \(d_2|a\text{.}\)
Posons \(d_1=\text{pgcd}(a,b)\text{.}\) Ainsi, on sait que \(d_1|a\) et \(d_1|b\text{.}\) On a donc \(a=d_1q_1\) et \(b=d_1q_2\) pour \(q_1,\ q_2\ \in \Z\text{.}\) En multipliant les deux égalités par \(-1\text{,}\) on obtient \(-a=|a|=d_1(-q_1)\) et \(-b=|b|=d_1(-q_2)\text{,}\) c’est-à-dire que \(d_1|(|a|)\) et \(d_1|(|b|)\text{.}\)
Posons \(d_2=\text{pgcd}(|a|,|b|)\text{.}\) Ainsi, on sait que \(d_2|(|a|)\) et \(d_2|(|b|)\text{.}\) On a donc \(|a|=-a=d_2k_1\) et \(|b|=-b=d_2k_2\) pour \(k_1,\ k_2\ \in \Z\text{.}\) En multipliant les deux égalités par \(-1\text{,}\) on obtient \(a=d_2(-k_1)\) et \(b=d_2(-k_2)\text{,}\) c’est-à-dire que \(d_2|a\) et \(d_2|b\text{.}\)
Cette relation a des conséquences importantes en théorie des nombres. On montre dans cet exercice comment démontrer l’existence des entiers \(x,y\) et on explique comment on peut trouver de tels entiers.
On considère l’ensemble \(S=\{n\in \N~|~ n=ax+by \text{ avec } x,y\in \Z\text{ et } n>0\}\text{.}\) C’est donc l’ensemble des naturels plus grands que zéro qu’il est possible de former avec \(a,b\) en les combinant avec des entiers quelconques.
Il suffit de montrer qu’il existe au moins une paire \((x,y)\in \Z\times \Z\) telle que \(ax+by > 0\text{.}\) Pour cela, on prend \(x=\frac{|a|}{a}\) et \(y=\frac{|b|}{b}\text{.}\) Dans ce cas, on a que \(ax=|a|\) et \(by=|b|\text{.}\) Ainsi, \(ax+by=|a|+|b| \gt 0\text{.}\) En effet, on rappel que \(a\) et \(b\) sont non nuls, et donc \(ax+by=|a|+|b| \neq 0\text{.}\)
Ainsi, si \(r=0\text{,}\) alors \(r=0\in S\cup \{0\}\text{.}\) De l’autre côté, si \(r\neq 0\text{,}\) puisque \(r =ax+by\text{,}\) on sait que \(r\in S\text{.}\) En particulier, \(r\ \in S\cup \{0\}\text{.}\)
Utiliser le fait que dans la forme quotient reste, on a \(0\leq r< d_0\text{,}\) le fait que \(r\in S\cup\{0\}\) et le fait que \(d_0\) est le plus petit élément de \(S\) pour déterminer la valeur de \(r\text{.}\)
On veut montrer que \(r=0\text{.}\) En effet, Puisque \(r\in S\cup\{0\}\text{,}\) si \(r\neq 0\text{,}\) alors \(r\in S\) et \(0\lt r \lt d_0\text{.}\) Or, si \(r\in\ S\text{,}\) alors par définition de \(d_0\text{,}\) on a que \(d_0\leq r\text{,}\) ce qui est impossible si \(0\lt r \lt d_0\text{.}\) On doit donc avoir \(r=0\text{.}\)
Le plus petit élément de \(S\) est donc un diviseur de \(a\) et \(b\text{.}\) On va maintenant montrer que c’est nécessairement le \(\pgcd\) de ces deux nombres.
Soit \(a,b\in \Z\) deux entiers non nuls. On définit le plus petit commun multiple de \(a,b\text{,}\) noté \(\ppcm{(a,b)}\) comme étant le nombre \(m\) qui satisfait les propriétés suivantes:
