{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons.\n\n Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"},{"metadata":{},"cell_type":"markdown","source":"
\n\n"},{"metadata":{},"cell_type":"markdown","source":"Un spectateur annonce $328$ et en quelques secondes, le magicien déclare : \"Votre anniversaire tombe le 17 avril !\".\nLors d’une représentation, un magicien mentaliste annonce aux spectateurs :
\n
\n« Prenez le numéro de votre jour de naissance et multipliez-le par 12. Prenez le rang de votre mois de naissance et multipliez-le par 31. Ajoutez les deux nombres obtenus et donnez moi le résultat. Je pourrai alors vous donner la date de votre anniversaire ».
$\\quad\\;\\;$a. Écrire une fonction Python TestE qui :\n
$\\quad\\;\\;$b. Écrire une fonction Python Resolution qui :\n
$\\quad\\;\\;$c. Effectuer un appel à la fonction Python Resolution pour retrouver le résultat de la question 2.4.\n
$m$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|
$7m\\equiv ...[12]$ |
\nDéfinition : Équation diophantienne dans $\\mathbb{Z}$.\n\n
\nSoit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$.
\nL'équation $ax+by=c$ dont l'inconnue est le couple $(x;y) \\in \\mathbb{Z}^2$ est appelée équation diophantienne.\n
\nPropriété : Existence de solutions d'une équation diophantienne\n\n
\nSoit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\nL'équation diophantienne $ax+by=c$ admet des solutions si et seulement si $c$ est un multiple de $PGCD(a;b)$.\n
\nMéthode : Méthode générale de résolution d'une équation diophantienne\n\nAnnexe :\n
\nSoit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\nPour résoudre l'équation diophantienne $ax+by=c$ d'inconnue $(x;y) \\in \\mathbb{Z}^2$ :\n\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
\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
\n (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)
\n
\n- Rechercher une condition nécessaire pour qu'un couple $(x;y)$ soit solution :
\n
\n\n
\n- La solution particulière permet de transformer l'équation diophantienne :
\n
\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- On en déduit les valeurs possibles pour $x$ :
\n
\n $\\begin{Bmatrix} b\\;' \\text{ divise } a\\;'(x-x_0) \\\\ a\\;' \\text{ et } b\\;' \\text{ sont premiers entre eux} \\end{Bmatrix}$ donc d'après le 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- On en déduit les valeurs correspondantes possibles pour $y$ :
\n
\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- Vérifier que la condition trouvée est suffisante
\n
\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}_{= c}+akb\\;'-bka\\;'$
\n $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=c+k(ab\\;'-ba\\;')$
\n $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=c+k(da\\;'b\\;'-db\\;'a\\;')$
\n $\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;=c$\n- Conclure :
\n
\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 L'ensemble des solutions de l'équation est donc $S=\\left\\{ (x_0+kb\\;';y_0-ka\\;') \\; / \\; k\\in\\mathbb{Z} \\right\\}$.\n
\nThéorème : Théorème de Gauss."},{"metadata":{},"cell_type":"markdown","source":"![Diophante](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Diophante_ouvrage.jpg)\n\n
\nSoit $a \\in \\mathbb{Z}^*$ ; $b \\in \\mathbb{Z}^*$ et $c \\in \\mathbb{Z}^*$
\n
\nSi $\\begin{Bmatrix} a \\text{ et } b \\text{ sont premiers entre eux} \\\\ a \\text{ divise } bc \\end{Bmatrix}$ alors $a$ divise $c$.\n