Il n'y a pas unicité du couple de coefficients de Bézout.
Par exemple, $PGCD(12;42)=6$ et on peut écrire différentes décompositions de $6$ comme combinaison linéaire de $12$ et $42$:
$12 \\times (-3) + 42 \\times 1 =6$
$12 \\times 4 + 42 \\times (-1) =6$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - A l'aide de l'algorithme d'Euclide, déterminer le PGCD de $420$ et $637$, puis exprimer ce PGCD comme combinaison linéaire de ces deux nombres.
\n",
" - Même question pour $152$ et $184$.
\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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 :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Théorème : Théorème de Bézout.
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$
\n",
"Alors :
\n",
" $a$ et $b$ sont premiers entre eux si et seulement si $\\exists(u;v) \\in \\mathbb{Z}^2 \\;/\\; au+bv=1$\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Démontrer le théorème de Bézout, par double-implication.
\n",
" - Dans le manuel : Exercice n°18,19,22 p149.
\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Théorème : Théorème de Gauss.
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\n",
"
\n",
"Si $\\begin{Bmatrix} a \\text{ et } b \\text{ sont premiers entre eux} \\\\ a \\text{ divise } bc \\end{Bmatrix}$ alors $a$ divise $c$.\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Dans le manuel : Démontrer le théorème de Gauss : \"Rédiger une démonstration\" n°1 p144
\n",
" - Dans le manuel : Exercice n°26,27 p149.
\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On en déduit la propriété suivante, conséquence du théorème de Gauss :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Propriété : diviseurs premiers entre eux
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\n",
"
\n",
"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$.\n",
"
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Dans le manuel : Démontrer la propriété ci-dessus : \"Rédiger une démonstration\" n°2 p144
\n",
" - Dans le manuel : Exercice n°31 p149.
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"5. Résolution d'équations diophantiennes
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Définition : Équation diophantienne $\\mathbb{Z}$.
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$.
\n",
"L'équation $ax+by=c$ dont l'inconnue est le couple $(x;y) \\in \\mathbb{Z}^2$ est appelée équation diophantienne.\n",
"
\n",
"\n",
"\n",
"Propriété : Existence de solution d'une équation diophantienne
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\n",
"L'équation diophantienne $ax+by=c$ admet des solutions si et seulement si $c$ est un multiple de $PGCD(a;b)$.\n",
"
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Dans le manuel : Démontrer la propriété ci-dessus : \"Rédiger une démonstration\" n°4 p145
\n",
" - Dans le manuel : Exercice n°33; 34; 32 p150.
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Méthode : Méthode générale de résolution d'une équation diophantienne
\n",
"Soit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\n",
"Pour résoudre l'équation diophantienne $ax+by=c$ d'inconnue $(x;y) \\in \\mathbb{Z}^2$ :\n",
"\n",
" - Rechercher un couple particulier $(x_0;y_0)$ tel que $ax_0+by_0=c$.
\n",
" Pour cela, essayer dans l'ordre :
\n",
" \n",
" - Si une solution particulière est proposée dans l'énoncé, vérifier qu'elle convient.
\n",
" - Si possible, déterminer directement une solution particulière \"évidente\".
\n",
" - Sinon: \n",
"
\n",
" - L'algorithme d'Euclide donne $d=PGCD(a;b)$ et un couple de coefficients de Bézout $(u;v)$ tel que $au+bv=d$
\n",
" - La valeur $d=PGCD(a;b)$ permet de vérifier que l'équation admet des solutions
\n",
" (c'est le cas si et seulement si $d$ divise $c$ d'après la propriété précédente) \n",
" - Si c'est le cas, l'égalité $au+bv=d$ permet d'obtenir une solution $ax_0+by_0=c$ (en multipliant)
\n",
"
\n",
"
\n",
" - Rechercher une condition nécessaire pour qu'un couple $(x;y)$ soit solution :
\n",
" \n",
" - La solution particulière permet de transformer l'équation diophantienne :
\n",
" $ax+by=c \\Longleftrightarrow ax+by=ax_0+by_0$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\Longleftrightarrow a(x-x_0)=b(y_0-y)$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\Longleftrightarrow a\\;'(x-x_0)=b\\;'(y_0-y)$ en divisant par $d=PGCD(a;b)$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$(où $a=da\\;'$ et $b=db\\;'$ avec $a\\;'$ et $b\\;'$ premiers entre eux)
\n",
" \n",
" - On en déduit les valeurs possibles pour $x$ :
\n",
" $\\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).
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;$donc $\\exists k \\in \\mathbb{Z}$ tel que $x-x_0=kb\\;'$ c'est à dire $x=x_0+k\\;b'$.
\n",
" \n",
" - On en déduit les valeurs correspondantes possibles pour $y$ :
\n",
" $x-x_0=kb\\;'$ donc $a\\;'(x-x_0)=b\\;(y-y_0)$ donne $a\\;'kb\\;'=b\\;'(y_0-y)$
\n",
" $a\\;'k=y_0-y$
\n",
" $y=y_0-ka\\;'$\n",
" \n",
"
\n",
"
\n",
" - Vérifier que la condition trouvée est suffisante
\n",
" On considère $(x;y)=(x_0+kb\\;';y_0-ka\\;')$ où $k \\in \\mathbb{Z}$ que l'on teste dans l'équation diophantienne :
\n",
" $ax+by=a(x_0+kb\\;')+b(y_0-ka\\;')$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=\\underbrace{ax_0+by_0}_{= 0}+akb\\;'-bka\\;'$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=k(ab\\;'-ba\\;')$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=k(da\\;'b\\;'-db\\;'a\\;')$
\n",
" $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=0$\n",
"
\n",
" - Conclure :
\n",
" Les solutions de l'équation diophantienne sont exactement les couples $(x;y)=(x_0+kb\\;';y_0-ka\\;')$ où $k \\in \\mathbb{Z}$.\n",
" \n",
"
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Résoudre l'équation diophantienne $39x+27y=18$ en suivant pas à pas la méthode ci-dessus.
\n",
" - Dans le manuel : Exercices n°35,37,39,42 p150.
\n",
" - TP : Chiffrement affine et chiffrement de Vigenère
\n",
" - TP : Chiffrement de Hill (Attention, nécessite les opérations sur les matrices)
\n",
"
\n",
"\n",
" TP Chiffrement affine et chiffrement de Vigenère :\n",
"
\n",
"\n",
"[](https://mybinder.org/v2/gh/PythonLycee/PyLyc/master?filepath=Chiffrement_affine_Vigenere.ipynb)\n",
"\n",
"\n",
" TP Chiffrement de Hill (avec opérations sur les matrices) :\n",
"
\n",
"\n",
"[](https://mybinder.org/v2/gh/PythonLycee/PyLyc/master?filepath=Chiffrement_Hill.ipynb)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"6. Nombres premiers
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Dans toute cette partie, on ne considèrera que des entiers naturels.
\n",
"Sauf mention expresse du contraire, le terme \" diviseur \" signifiera donc \" diviseur positif \".\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Définition : Nombre premier.
\n",
"Soit $p \\in \\mathbb{N}$.
\n",
" Le nombre $p$ est dit premier s'il a exactement deux diviseurs : 1 et lui-même.\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Lister les nombres premiers inférieurs à 30.
\n",
" - Dans le manuel : Exercices n°2,6,8,7,10 p170.
\n",
" - Démontrer que deux nombres premiers distincts sont forcément premiers entre eux
\n",
" - Dans le manuel : Exercices n°16,24,23 p170,171.
\n",
" - Programmation Python :
\n",
" Écrire une fonction Python premier qui reçoit un entier naturel non nul n en argument, et qui renvoie True si ce nombre est premier et False sinon.
Aide : On peut utiliser la fonction Python diviseurs déjà écrite dans la section de cours 1, sachant que la syntaxe len(L) permet d'obtenir le nombre d'éléments d'une liste L. \n",
"
\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#(Zone Python pour l'exercice 5)\n",
"#Écrire ici la fonction diviseurs_pos\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#(Zone Python pour l'exercice 5)\n",
"#Écrire ici la fonction premier\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Propriété : Existence d'un diviseur premier.
\n",
"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}$.\n",
"
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercice :
\n",
"Dans le manuel : Démonstration de la propriété ci-dessus : \"Rédiger une démonstration\" n°1 p167."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Théorème : Ensemble des nombres premiers.
\n",
"Il existe une infinité de nombres premiers.\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercice :
\n",
"Dans le manuel : Démonstration du théorème ci-dessus : \"Rédiger une démonstration\" n°2 p167."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" TP : Crible d'Ératosthène
\n",
"
\n",
"\n",
"[](https://mybinder.org/v2/gh/PythonLycee/PyLyc/master?filepath=Crible_Eratosthene.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Théorème : Théorème fondamental de l'arithmétique : Décomposition d'un entier en produit de facteurs premiers.
\n",
"Soit $n$ un entier naturel supérieur ou égal à $2$.
\n",
"Alors il existe une décomposition unique de $n$ sous forme d'un produit de facteurs premiers ordonnés :
\n",
"$$n=p_1^{\\alpha_1}p_2^{\\alpha_2}...p_m^{\\alpha_m}$$\n",
"
où $p_1\n",
"et $\\alpha_1;\\alpha_2;...;\\alpha_m$ sont des entiers naturels non nuls.\n",
"
\n",
"Cette écriture s'appelle la décomposition en produit de facteurs premiers de $n$.\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Remarque:
\n",
"Ce théorème peut s'écrire, avec les notations mathématiques :\n",
"\n",
"$$\\forall n \\in \\mathbb{N}\\;,\\; n \\geq 2\\;,\\; \\exists! m \\in \\mathbb{N}^*\\;,\\; \\exists! (p_i)_{1 \\leq i \\leq m} \\in \\mathbb{N}^m\\;,\\; \\exists! (\\alpha_i)_{1 \\leq i \\leq m} \\in (\\mathbb{N}^{*})^m\\; / $$\n",
"\n",
"$$ \\forall 1 \\leq i \\leq m \\;\\;,\\;\\; p_i \\text{ est premier}$$\n",
"$$ \\forall 1 \\leq i \\leq m-1 \\;\\;,\\;\\; p_i < p_{i+1}$$\n",
"$$ n = p_1^{\\alpha_1}p_2^{\\alpha_2}...p_m^{\\alpha_m} = \\prod_{i=1}^m p_i^{\\alpha_i}$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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
\n",
"\n",
" - Existence de la décomposition :
\n",
" Pour tout $n \\geq 2$, on considère la propriété $Q(n): \\;\" \\forall 1 \\leq j \\leq n, \\text{ il existe une décomposition en produit de facteurs premiers de } j \"$
\n",
" Démontrer par récurrence que la propriété $Q(n)$ est vraie pour tout $n \\geq 2$.
\n",
" (On pourra utiliser la propriété qui assure qu'un nombre non premier $n \\geq 2$ admet au moins un diviseur premier)\n",
" \n",
" - Unicité de la décomposition :
\n",
" On souhaite effectuer un raisonnement par l'absurde.
\n",
" On suppose donc qu'il existe un entier $n \\geq 2$ pour lequel il existe deux décompositions différentes en produits de facteurs premiers :
\n",
" $n = p_1^{\\alpha_1}p_2^{\\alpha_2}...p_m^{\\alpha_m} = q_1^{\\;\\beta_1}q_2^{\\;\\beta_2}...q_r^{\\;\\beta_r}$ où les $(p_i)$, $(q_i)$ sont des nombres premiers et les $(\\alpha_i)$, $(\\beta_i)$ sont des entiers naturels non nuls.
\n",
" Comme les deux décompositions sont distinctes, il existe dans une des deux décompositions un facteur premier $p$ qui apparait avec une puissance différente dans l'autre décomposition ou qui n'apparait pas.
\n",
" On peut par exemple supposer que $n=p^{\\;\\alpha} \\times a$ et $n=p^{\\;\\beta} \\times b$ avec $\\alpha > \\beta \\geq 0$\n",
" (où $a$ et $b$ sont des produits de nombres premiers distincts de $p$)
\n",
" NB : le cas $\\beta=0$ correspond au cas où $p$ n'apparait pas dans la deuxième décomposition.\n",
" \n",
" - Justifier que $p$ est premier avec $b$.
\n",
" - Justifier que $p^{\\alpha-\\beta} \\times a = b$ et en déduire une contradiction.
\n",
" - Conclure.
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Propriété : Diviseurs d'un entier.
\n",
"Si $n$ est un entier naturel supérieur ou égal à $2$ dont la décomposition en facteurs premiers est : \n",
"$$n=p_1^{\\alpha_1}p_2^{\\alpha_2}...p_m^{\\alpha_m}$$\n",
"
où $p_1\n",
"et $\\alpha_1;\\alpha_2;...;\\alpha_m$ sont des entiers naturels non nuls.
\n",
"Alors:\n",
"\n",
" - il y a exactement $(\\alpha_1+1)(\\alpha_2+1)...(\\alpha_m+1)$ diviseurs de $n$ ;
\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$. \n",
"
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"\n",
" - Dans le manuel : Exercices n°29,30,31,32,35,37,40,42,43 p171.
\n",
" - Dans le manuel : Exercice n°66,60 p173.
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Théorème : Petit théorème de Fermat.
\n",
"Soit $n \\in \\mathbb{N}$.
\n",
"\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]$.
\n",
" - Si $p$ est premier, alors $n^{\\;p} \\equiv n \\;[p]$
\n",
"
\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercices :\n",
"Dans le manuel : Exercices n°48,49 p172.\n",
"\n",
"\n",
" TP : Chiffrement RSA
\n",
"
\n",
"\n",
"[](https://mybinder.org/v2/gh/PythonLycee/PyLyc/master?filepath=Chiffrement_RSA.ipynb)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}