© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com/
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
COURS DE TERMINALE - MATHEMATIQUES EXPERTES
Arithmétique
Programme officiel : Programme Tale Math Expertes
PRÉAMBULE ET AVERTISSEMENT
Ce cours est brut : Il n'est illustré que par quelques exercices et activités, et doit donc - pour être efficace - être utilisé en complément de séries d'exercices. Les quelques exercices contenus dans ce document seront repérés à l'aide des deux icônes ci-contre.
1. Division euclidienne et divisibilité
Notations :
Théorème : Division euclidienne d'un entier naturel par un entier naturel non nul.
Pour tout $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$,
il existe un unique couple $(q;r)$ avec $q \in \mathbb{N}$ et $r \in \mathbb{N}$ tels que : $\begin{Bmatrix} a=bq+r \\ 0 \leq r < b \end{Bmatrix}$.
# Activer cette cellule (SHIFT+Entrée) pour faire apparaître la figure dynamique
from IPython.display import HTML ; HTML("""<iframe scrolling="no" title="Div_eucl_nat" src="https://www.geogebra.org/material/iframe/id/ddfuqnn7/width/913/height/256/border/888888/sfsb/true/smb/false/stb/false/stbh/false/ai/false/asb/false/sri/false/rc/false/ld/false/sdz/false/ctl/false" width="913px" height="256px" style="border:0px;"> </iframe>""")
Théorème : Division euclidienne d'un entier relatif par un entier naturel non nul.
Pour tout $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$,
il existe un unique couple $(q;r)$ avec $q \in \mathbb{Z}$ et $r \in \mathbb{N}$ tels que : $\begin{Bmatrix} a=bq+r \\ 0 \leq r < b \end{Bmatrix}$.
Remarque :
Ce théorème peut s'écrire :
$\forall (a;b) \in \mathbb{Z} \times \mathbb{N}^* \;\; ; \;\; \exists! (q;r) \in \mathbb{Z} \times \mathbb{N} \;\; / \;\; \begin{Bmatrix} a=bq+r \\ 0 \leq r < b \end{Bmatrix}$
Illustration graphique :
# Activer cette cellule (SHIFT+Entrée) pour faire apparaître la figure dynamique
from IPython.display import HTML ; HTML("""<iframe scrolling="no" title="Div_eucl_rel" src="https://www.geogebra.org/material/iframe/id/awanfanj/width/913/height/256/border/888888/sfsb/true/smb/false/stb/false/stbh/false/ai/false/asb/false/sri/false/rc/false/ld/false/sdz/false/ctl/false" width="913px" height="256px" style="border:0px;"> </iframe>""")
Syntaxe Python :
a = -25 ; b = 7
q = a//b # Syntaxe de calcul du quotient de la division euclidienne de a par b
r = a%b # Syntaxe de calcul du reste de la division euclidienne de a par b
q,r # Affichage de q et r
# Écrire ici la fonction div_euclidienne
# Tester ici la fonction div_euclidienne
Définition : Divisibilité dans $\mathbb{Z}$.
Soit $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$.
On dit que $b$ divise $a$ s'il existe $q \in \mathbb{Z}$ tel que $a=bq$.
Remarque :
# Écrire ici la fonction diviseurs
# Tester ici la fonction diviseurs
Notation :
Pour tout $a \in \mathbb{Z}$, on note $D(a)$ l'ensemble des diviseurs de $a$.
Ainsi $b \in D(a)$ se lit " $b$ divise $a$ ".
Propriétés : Ensemble des diviseurs d'un entier.
Soit $a \in \mathbb{Z}$ ; $b \in \mathbb{Z}$ et $c \in \mathbb{Z}$.
- $\;\;$ Si $a \ne 0$, les éléments de $D(a)$ sont compris entre $-a$ et $a$, et par conséquent $D(a)$ est un ensemble fini.
- $\;\;$ $b \in D(a) \Longleftrightarrow -b \in D(a) \Longleftrightarrow b \in D(-a) \Longleftrightarrow -b \in D(-a)$
- $\;\;$ Si $a \in D(b)$ et $b \in D(c)$ alors $a \in D(c)$.
- $\;\;$ Si $a \in D(b)$ et $a \in D(c)$ alors $a \in D(bu+cv)$ pour tout couple $(u;v) \in \mathbb{Z}^2$.
$\;\;$NB : Un nombre de la forme $bu+cv$ avec $(u;v) \in \mathbb{Z}^2$ s'appelle une combinaison linéaire de $b$ et $c$.
Exemples :
$D(10)=\left\{-10;-5;-2;-1;1;2;5;10\right\}$
Remarque :
La propriété 2. justifie qu'on ramène la recherche des diviseurs d'un nombre à la recherche des diviseurs positifs de sa valeur absolue (on cherche donc des diviseurs positifs d'un entier positif).
2. Congruence dans $\mathbb{Z}$
Définition et notation : Congruence dans $\mathbb{Z}$.
Soit $(a;b) \in \mathbb{Z}^2$ et $n \in \mathbb{N}^*$.
On dit que $a$ est congru à $b$ modulo $n$ si $n$ divise $a-b$.
Dans ce cas, on note $a \equiv b \;[n]$.
Remarques :
Propriété : Classes de congruences.
Soit $(a;b) \in \mathbb{Z}^2$ et $n \in \mathbb{N}^*$.
$a \equiv b \;[n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
Conséquence :
Illustration graphique pour $n=7$ :
# Activer cette cellule (SHIFT+Entrée) pour faire apparaître la figure dynamique
from IPython.display import HTML ; HTML("""<iframe scrolling="no" title="modulo_7" src="https://www.geogebra.org/material/iframe/id/vb5w62p5/width/786/height/700/border/888888/sfsb/true/smb/false/stb/false/stbh/false/ai/false/asb/false/sri/false/rc/false/ld/false/sdz/false/ctl/false" width="786px" height="700px" style="border:0px;"> </iframe>""")
Propriétés : Opérations et congruences.
Soit $a\;;b\;;c\;;d$ des élements de $\mathbb{Z}$ et $n \in \mathbb{N}^*$.
Somme $$ \text{Si } a \equiv b \;[n] \text{ alors } a+c \equiv b+c \;[n]$$ $\;\;\;$ $$\text{Si }\begin{Bmatrix} a \equiv b\;[n] \\ c \equiv d\;[n] \end{Bmatrix} \text{ alors } a+c \equiv b+d \;[n]$$ Produit $$\text{Si }a \equiv b \;[n] \text{ alors } ac \equiv bc \;[n]$$ $\;\;\;$ $$\text{Si }\begin{Bmatrix}a\equiv b\;[n]\\c\equiv d\;[n] \end{Bmatrix}\text{ alors }ac\equiv bd\;[n]$$ Puissance $$\text{Si } a \equiv b \;[n] \text{ alors } \forall p \in \mathbb{N}, a^p \equiv b^p \;[n]$$
Exercice/TD : Critères de divisibilité
Dans cet exercice, on considère $a \in \mathbb{N}$ dont l'écriture décimale est de la forme $a=\overline{a_ma_{m-1}...a_1a_0}$, où les $(a_i)_{0 \leq i \leq m}$ sont les chiffres de sa décomposition décimale.NB : Les méthodes détaillées dans ce TD permettent non seulement de caractériser la divisibilité par $2$ ; $3$ ; $5$ ; $7$ ; $9$ ; $10$ ; $11$ et $13$, mais également de déterminer les restes des divisions euclidiennes par ces nombres.
- Critères de divisibilité par $2$ ; $5$ et $10$.
- Étudier les congruences modulo $2$ des puissances de $10$ de la forme $10^k$ où $k \in \mathbb{N}$.
- En déduire que $a \equiv a_0 \;[2]$. Quel critère de divisibilité par $2$ peut-on énoncer ?
- Démontrer de la même façon des critères de divisibilité par $5$ et par $10$.
- Critères de divisibilité par $3$ et $9$.
- Étudier les congruences modulo $3$ des puissances de $10$ de la forme $10^k$ où $k \in \mathbb{N}$.
- En déduire que $a \equiv a_m+a_{m-1}+...+a_0\;[3]$.
Quel critère de divisibilité par $3$ peut-on énoncer ?- Démontrer de la même façon un critère de divisibilité par $9$.
- Le nombre $12\;504\;237$ est-il divisible par $3$ ? par $9$ ?
- Critère de divisibilité par $11$.
- Établir que $\forall k \in \mathbb{N}, \; 10^k \equiv (-1)^k \;[11]$.
- En déduire que $a \equiv (a_0+a_2+...)-(a_1+a_3+...)\;[11]$.
Quel critère de divisibilité par $11$ peut-on énoncer ?- Le nombre $51\;114\;239$ est-il divisible par $11$ ?
- Critères de divisibilité par $7$ et $13$.
- Établir que $\forall k \in \mathbb{N}, \;10^{3k} \equiv (-1)^k \;[13]$.
- On considère $a=17\;725\;864$. Justifier que $a \equiv 17-725+864 \;[13]$.
$a$ est-il divisible par $13$ ?- Les nombres $80\;501\;551$ et $10^{13}$ sont-ils divisibles par $13$ ?
- Justifier que la même méthode permet d'étudier la divisibilité par $7$.
Exercice/TD : Clé de vérification d'un numéro INSEE
Sur une carte vitale figure le n° INSEE à 13 chiffres de son propriétaire, suivi d'une clé de vérification à 2 chiffres :
- Le premier chiffre désigne le sexe de la personne (1 pour un homme, 2 pour une femme) ;
- Les deux chiffres suivants désignent les deux derniers chiffres de l’année de naissance ;
- Les deux chiffres suivants désignent les deux chiffres du mois de naissance ;
- Les deux chiffres suivants désignent le département de naissance ;
- Les trois chiffres suivants précisent la commune de naissance ;
- Les trois chiffres suivants correspondent au rang de naissance.
Pour calculer la clé de vérification $K$, on commence par calculer le reste $r$ de la division euclidienne par 97 du nombre formé par les 13 chiffres du n° INSEE, et on obtient $K$ à l'aide de la formule $K=97-r$.
- Certaines calculatrices permettent de calculer directement une clé de n° INSEE... d'autres pas.
Tester le calcul de la clé sur la carte vitale fournie et sur votre propre n° INSEE.
Votre calculatrice permet-elle d'effectuer ce calcul ? (préciser le modèle utilisé)
Afin de permettre le calcul de la clé sur tout appareil, on souhaite mettre en place une stratégie de calcul de cette clé utilisant des nombres de taille plus raisonnable.- On note $A$ le numéro INSEE.
On note $x$ le nombre formé par les $7$ premiers chiffres de $A$ et $y$ le nombre formé par les $6$ derniers chiffres de $A$.
- Exprimer $A$ en fonction de $x$ et $y$.
- Déterminer la classe de congruence de $10^2$ modulo $97$ et en déduire celle de $10^6$.
(classe de congruence de $n$ modulo $m$ signifie ici reste de la division euclidienne de $n$ par $m$)- En déduire que $A \equiv 27x+y \;[97]$
- En déduire une méthode de calcul de la clé de n°INSEE et tester cette méthode en reprenant les calculs de la question 1.
- Votre voisin vous fournit son numéro INSEE sans la clé. Pouvez vous retrouver la clé manquante ?
- Écrire deux fonctions Python qui reçoivent en argument le n° INSEE $A$ et qui renvoient la clé $K$ :
- directement avec sa définition ;
- à l'aide de la méthode vue à la question 2.
#Zone pour écrire la fonction Python du TD (calcul de la clé INSEE avec la méthode directe)
#Zone pour écrire la fonction Python du TD (calcul de la clé INSEE avec le 2ème méthode)
3. PGCD et algorithme d'Euclide
Notation :
Pour tout $a \in \mathbb{Z}^*$ et $b \in \mathbb{Z}^*$, on note $D(a;b)$ l'ensemble des diviseurs communs de $a$ et de $b$.
Remarque :
$D(a;b) = D(a) \cap D(b)$ est fini car $D(a)$ et $D(b)$ sont finis pour $a \ne 0$ et $b \ne 0$.
De plus, $1 \in D(a;b)$.
Comme $D(a;b)$ est un ensemble fini non vide d'entiers, il possède un plus grand élément. Ceci justifie la définition suivante :
Définition : PGCD de deux entiers $\mathbb{Z}$.
Soit $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$.
$D(a;b)$ possède un plus grand élément appelé plus grand commun diviseur (PGCD) de $a$ et $b$.
On note cet entier $PGCD(a;b)$.
Remarques :
Bilan des parties I et II du TP :
Propriété : Méthode de recherche du PGCD par l'algorithme d'Euclide
On considère $a \in \mathbb{N}^*$ et $b \in \mathbb{N}^*$.
On pose $\color{red}{a_0=a}$ et $\color{blue}{b_0=b}$ puis on considère la succession des divisions euclidiennes suivantes, réitérées tant que le reste $r_n$ n'est pas nul.
\begin{array}{} \color{red}{a_0} &=& \color{blue}{b_0} q_0 & + & \color{green}{r_0} \\ \; & \color{blue}\swarrow & \; & \color{green}\swarrow \\ \color{blue}{a_1} &=& \color{green}{b_1} q_1 & + & \color{magenta}{r_1} \\ \; & \color{green}\swarrow & \; & \color{magenta}\swarrow \\ \color{green}{a_2} &=& \color{magenta}{b_2} q_1 & + & \color{brown}{r_2} \\ \; & \color{magenta}\swarrow & \; & \color{brown}\swarrow \\ ... & \; & \;... & & ... \\ ... & \; & \;... & & ... \\ \; & \color{blue}\swarrow & \; & \color{green}\swarrow \\ \color{blue}{a_{N-1}} &=& \color{green}{b_{N-1}} q_{N-1} & + & \color{magenta}{r_{N-1}} \\ \; & \color{green}\swarrow & \; & \color{magenta}\swarrow \\ \color{green}{a_N} &=& \color{magenta}{b_N} q_N & + & \color{red}0 \\ \end{array}
Alors:On retient :
- Il existe un rang $N$ tel que $r_N=0$.
- $b_N=PGCD(a;b)$ et si $r_{N-1}$ existe alors $r_{N-1}=PGCD(a;b)$.
Le PGCD de $a$ et de $b$ est le dernier reste non nul obtenu en appliquant l'algorithme d'Euclide.
Propriété : Ensemble des diviseurs communs à deux nombres
Soit $a \in \mathbb{Z}^*$ et $b \in \mathbb{Z}^*$.
Si $d=PGCD(a;b)$ alors $D(a;b)=D(d).$
4. Nombres premiers entre eux, théorème de Bézout, théorème de Gauss
Définition : Entiers premiers entre eux $\mathbb{Z}$.
Soit $a \in \mathbb{Z}^*$ et $b \in \mathbb{Z}^*$.
On dit que $a$ et $b$ sont premiers entre eux si $PGCD(a;b)=1$.
Remarques :
Propriété : Ensemble des diviseurs communs à deux nombres
Soit $a \in \mathbb{Z}^*$ et $b \in \mathbb{Z}^*$.
Si $d=PGCD(a;b)$ alors $\exists a\;' \in \mathbb{Z}^*, \; \exists b\;' \in \mathbb{Z}^* \;/ \begin{Bmatrix} a=da\;' \\ b=db\;' \\ PGCD(a\;';b\;')=1 \end{Bmatrix}.$
Bilan de la partie III du TP :
Propriété : Existence des coefficients de Bézout : décomposition d'un PGCD de deux nombres comme combinaison linéaire de ces nombres
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $d=PGCD(a;b)$
Alors $\exists(u;v) \in \mathbb{Z}^2 \;/\; au+bv=d$
Remarque :
Dans le cas où $a$ et $b$ sont premiers entre eux, le résultat précédent peut s'écrire sous la forme d'une équivalence :
Théorème : Théorème de Bézout.
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$
Alors :
$a$ et $b$ sont premiers entre eux si et seulement si $\exists(u;v) \in \mathbb{Z}^2 \;/\; au+bv=1$
Théorème : Théorème de Gauss.
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}^*$
Si $\begin{Bmatrix} a \text{ et } b \text{ sont premiers entre eux} \\ a \text{ divise } bc \end{Bmatrix}$ alors $a$ divise $c$.
On en déduit la propriété suivante, conséquence du théorème de Gauss :
Propriété : diviseurs premiers entre eux
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}^*$
Si $\begin{Bmatrix} a \text{ et } b \text{ sont premiers entre eux} \\ a \text{ divise } c \\ b \text{ divise } c \end{Bmatrix}$ alors $ab$ divise $c$.
5. Résolution d'équations diophantiennes
Définition : Équation diophantienne $\mathbb{Z}$.
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}^*$.
L'équation $ax+by=c$ dont l'inconnue est le couple $(x;y) \in \mathbb{Z}^2$ est appelée équation diophantienne.
Propriété : Existence de solution d'une équation diophantienne
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}^*$
L'équation diophantienne $ax+by=c$ admet des solutions si et seulement si $c$ est un multiple de $PGCD(a;b)$.
Méthode : Méthode générale de résolution d'une équation diophantienne
Soit $a \in \mathbb{Z}^*$ ; $b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}^*$
Pour résoudre l'équation diophantienne $ax+by=c$ d'inconnue $(x;y) \in \mathbb{Z}^2$ :
- Rechercher un couple particulier $(x_0;y_0)$ tel que $ax_0+by_0=c$.
Pour cela, essayer dans l'ordre :
- Si une solution particulière est proposée dans l'énoncé, vérifier qu'elle convient.
- Si possible, déterminer directement une solution particulière "évidente".
- Sinon:
- L'algorithme d'Euclide donne $d=PGCD(a;b)$ et un couple de coefficients de Bézout $(u;v)$ tel que $au+bv=d$
- La valeur $d=PGCD(a;b)$ permet de vérifier que l'équation admet des solutions
(c'est le cas si et seulement si $d$ divise $c$ d'après la propriété précédente)- Si c'est le cas, l'égalité $au+bv=d$ permet d'obtenir une solution $ax_0+by_0=c$ (en multipliant)
- Rechercher une condition nécessaire pour qu'un couple $(x;y)$ soit solution :
- La solution particulière permet de transformer l'équation diophantienne :
$ax+by=c \Longleftrightarrow ax+by=ax_0+by_0$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Longleftrightarrow a(x-x_0)=b(y_0-y)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Longleftrightarrow a\;'(x-x_0)=b\;'(y_0-y)$ en divisant par $d=PGCD(a;b)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$(où $a=da\;'$ et $b=db\;'$ avec $a\;'$ et $b\;'$ premiers entre eux)
- On en déduit les valeurs possibles pour $x$ :
$\begin{Bmatrix} b\;' \text{ divise } a\;'(x-x_0) \\ a\;' \text{ et } b\;' \text{ sont premiers entre eux} \end{Bmatrix}$ donc (théorème de Gauss) $b\;'$ divise (x-x_0).
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$donc $\exists k \in \mathbb{Z}$ tel que $x-x_0=kb\;'$ c'est à dire $x=x_0+k\;b'$.
- On en déduit les valeurs correspondantes possibles pour $y$ :
$x-x_0=kb\;'$ donc $a\;'(x-x_0)=b\;(y-y_0)$ donne $a\;'kb\;'=b\;'(y_0-y)$
$a\;'k=y_0-y$
$y=y_0-ka\;'$- Vérifier que la condition trouvée est suffisante
On considère $(x;y)=(x_0+kb\;';y_0-ka\;')$ où $k \in \mathbb{Z}$ que l'on teste dans l'équation diophantienne :
$ax+by=a(x_0+kb\;')+b(y_0-ka\;')$
$\;\;\;\;\;\;\;\;\;\;\;=\underbrace{ax_0+by_0}_{= 0}+akb\;'-bka\;'$
$\;\;\;\;\;\;\;\;\;\;\;=k(ab\;'-ba\;')$
$\;\;\;\;\;\;\;\;\;\;\;=k(da\;'b\;'-db\;'a\;')$
$\;\;\;\;\;\;\;\;\;\;\;=0$- Conclure :
Les solutions de l'équation diophantienne sont exactement les couples $(x;y)=(x_0+kb\;';y_0-ka\;')$ où $k \in \mathbb{Z}$.
6. Nombres premiers
Dans toute cette partie, on ne considèrera que des entiers naturels.
Sauf mention expresse du contraire, le terme " diviseur " signifiera donc " diviseur positif ".
Définition : Nombre premier.
Soit $p \in \mathbb{N}$.
Le nombre $p$ est dit premier s'il a exactement deux diviseurs : 1 et lui-même.
#Écrire ici la fonction premier
Propriété : Existence d'un diviseur premier.
Si $n$ est un entier naturel supérieur à $2$ non premier, alors $n$ admet (au moins) un diviseur premier inférieur ou égal à $\sqrt{n}$.
Théorème : Ensemble des nombres premiers.
Il existe une infinité de nombres premiers.
Théorème : Théorème fondamental de l'arithmétique : Décomposition d'un entier en produit de facteurs premiers.
Soit $n$ un entier naturel supérieur ou égal à $2$.
Alors il existe une décomposition unique de $n$ sous forme d'un produit de facteurs premiers ordonnés :
$$n=p_1^{\alpha_1}p_2^{\alpha_2}...p_m^{\alpha_m}$$
où $p_1et $\alpha_1;\alpha_2;...;\alpha_m$ sont des entiers naturels non nuls.
Cette écriture s'appelle la décomposition en produit de facteurs premiers de $n$.
Remarque:
Ce théorème peut s'écrire, avec les notations mathématiques :
Exercice de démonstration :
Démonstration du théorème énonçant l'existence et l'unicité de la décomposition en produit de facteurs premiers
Propriété : Diviseurs d'un entier.
Si $n$ est un entier naturel supérieur ou égal à $2$ dont la décomposition en facteurs premiers est : $$n=p_1^{\alpha_1}p_2^{\alpha_2}...p_m^{\alpha_m}$$
où $p_1et $\alpha_1;\alpha_2;...;\alpha_m$ sont des entiers naturels non nuls.
Alors:
- il y a exactement $(\alpha_1+1)(\alpha_2+1)...(\alpha_m+1)$ diviseurs de $n$ ;
- les diviseurs de $n$ sont exactement les nombres $d$ qui s'écrivent $d=p_1^{\;\beta_1}p_2^{\;\beta_2}...p_m^{\;\beta_m}$
où $\beta_1;\beta_2;...;\beta_m$ sont des entiers naturels tels que $\forall 1 \leq i \leq m \;,\;0 \leq \beta_i \leq \alpha_i$.
Théorème : Petit théorème de Fermat.
Soit $n \in \mathbb{N}$.
- Si $\begin{Bmatrix} p \text{ est un nombre premier} \\ p \text{ ne divise pas } n \end{Bmatrix}$ alors $n^{\;p-1} \equiv 1 \;[p]$.
- Si $p$ est premier, alors $n^{\;p} \equiv n \;[p]$
© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.