© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Cette activité est inspirée d'un exercice de Bac S Spécialité (Polynésie, 2014).
1. Présentation du tour
2. Résolution algorithmique
3. Résolution par tableau
4. Compléments : Éléments de cours et méthode de résolution d'une équation diophantienne
Situation étudiée :
Lors d’une représentation, un magicien mentaliste annonce aux spectateurs :
« 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 ».
Un spectateur annonce $328$ et en quelques secondes, le magicien déclare : "Votre anniversaire tombe le 17 avril !".
# Écrire ici la fonction Calcul
def Calcul(j,m):
return j*12+m*31
# Effectuer ici l'appel à la fonction Calcul
Calcul(17,4)
328
Dans cette partie, on considère le cas d'un spectateur qui annonce la valeur $242$.
Pour les questions 2.2 et 2.3, on pourra utiliser la méthode de résolution détaillée dans la section 4.
$\quad\;\;$a. Écrire une fonction Python TestE qui :
# Écrire ici la fonction TestE
def TestE(x,y,c):
return 12*x+31*y==c
$\quad\;\;$b. Écrire une fonction Python Resolution qui :
# Écrire ici la fonction Resolution
def Resolution(c):
for x in range(1,32):
for y in range(1,13):
if TestE(x,y,c):
return (x,y)
return None
$\quad\;\;$c. Effectuer un appel à la fonction Python Resolution pour retrouver le résultat de la question 2.4.
# Effectuer ici l'appel à la fonction Resolution
Resolution(242)
(15, 2)
On souhaite retrouver la date d'anniversaire d'un spectateur avec une autre méthode.
On note respectivement $j$ et $m$ le numéro du jour et le rang du mois de naissance du spectateur, et on pose $p=12j+31m$.
# Effectuer ici les saisies nécessaires pour remplir le tableau
def tableau():
"fonction permettant le remplissage du tableau des congruences de 7m modulo 12"
L=[]
for m in range(1,13):
L.append( (m,7*m %12) )
return L
tableau()
[(1, 7), (2, 2), (3, 9), (4, 4), (5, 11), (6, 6), (7, 1), (8, 8), (9, 3), (10, 10), (11, 5), (12, 0)]
Définition : Équation diophantienne dans $\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 solutions 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 d'après le 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}_{= c}+akb\;'-bka\;'$
$\;\;\;\;\;\;\;\;\;\;\;=c+k(ab\;'-ba\;')$
$\;\;\;\;\;\;\;\;\;\;\;=c+k(da\;'b\;'-db\;'a\;')$
$\;\;\;\;\;\;\;\;\;\;\;=c$- Conclure :
Les solutions de l'équation diophantienne sont exactement les couples $(x;y)=(x_0+kb\;';y_0-ka\;')$ où $k \in \mathbb{Z}$.
L'ensemble des solutions de l'équation est donc $S=\left\{ (x_0+kb\;';y_0-ka\;') \; / \; k\in\mathbb{Z} \right\}$.
Annexe :
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$.
© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Dernière modification de l'activité : Juillet 2022