Théorème de Paoli

dans Arithmétique
Bonjour/Bonsoir
J'ai beaucoup cherché la démonstration du théorème (Paoli Theorem), mais en vain, si quelqu'un à la démonstration je le remercie vivement de la faire partager.
NB. Je fais allusion au fameux résultat de Paoli sur la résolution de l'équation ax + by = c où a, b, c sont des entiers naturels, a et b non nuls et premiers entre eux.
J'ai beaucoup cherché la démonstration du théorème (Paoli Theorem), mais en vain, si quelqu'un à la démonstration je le remercie vivement de la faire partager.
NB. Je fais allusion au fameux résultat de Paoli sur la résolution de l'équation ax + by = c où a, b, c sont des entiers naturels, a et b non nuls et premiers entre eux.
Réponses
-
Soient $a,b \in \mathbb{N}^*$ tels que $(a,b)=1$. D'après Bachet-Bézout, il existe $u,v \in \mathbb{N}$ tels que $-au+bv = 1$. La méthode de résolution habituelle des équations diophantiennes linéaires $ax+by=c$ donne les solutions dans $\mathbb{Z}^2$
$$x = -uc + bk \quad \textrm{et} \quad y = vc-ak \quad \left( k \in \mathbb{Z} \right).$$
On impose $x,y \geqslant 0$, ce qui implique que le nombre $\mathcal{D}$ de solutions dans $\mathbb{N}^2$ de l'équation $ax+by=c$ est égal au nombre d'entiers de l'intervalle $\left [uc/b, vc/a \right]$ (notons que l'on a trivialement $au \leqslant bv$ par définition de $u$ et $v$), et donc
$$\mathcal{D} = \left \lfloor \frac{vc}{a} \right \rfloor + \left \lfloor 1 - \frac{uc}{b} \right \rfloor.$$
Notons déjà que, si $r$ est le reste de la division euclidienne de $c$ par $ab$, alors ceci permet de montrer que le nombre de solutions dans $\mathbb{N}^2$ de l'équation $ax+by=r$ est $\leqslant \frac{vr}{a} + 1 - \frac{ur}{b} = 1 + \frac{r}{ab} < 2$ et donc est égal à $0$ ou $1$.
Si l'équation $ax+by=r$ n'a pas de solution dans $\mathbb{N}^2$, alors l'intervalle $\left [ur/b, vr/a \right]$ ne contient pas d'entier, de sorte que $\left \lfloor ur/b \right \rfloor = \left \lfloor vr/a \right \rfloor$, et donc
\begin{eqnarray*}
\mathcal{D} &=& \left \lfloor \frac{vr}{a} \right \rfloor + bv \left \lfloor \frac{c}{ab} \right \rfloor + 1 + \left \lfloor -\frac{ur}{b} \right \rfloor -au \left \lfloor \frac{c}{ab} \right \rfloor \\
&=& \left \lfloor \frac{vr}{a} \right \rfloor + bv \left \lfloor \frac{c}{ab} \right \rfloor + 1 -1- \left \lfloor \frac{ur}{b} \right \rfloor -au \left \lfloor \frac{c}{ab} \right \rfloor \\
&=& (bv-au) \left \lfloor \frac{c}{ab} \right \rfloor = \left \lfloor \frac{c}{ab} \right \rfloor .
\end{eqnarray*}
Le raisonnement est identique lorsque l'équation $ax+by=r$ a une solution dans $\mathbb{N}^2$, sauf qu'ici l'intervalle $\left [ur/b, vr/a \right]$ contient un seul entier, de sorte que $\left \lfloor ur/b \right \rfloor = \left \lfloor vr/a \right \rfloor - 1$. -
On a donc montré la propositions suivante :
Soient $a,b \in \mathbb{N}^*$ tels que $(a,b)=1$, $c \in \mathbb{N}$, et on désigne par $r$ le reste de la division euclidienne de $c$ par $ab$. Pour $n \in \{c,r\}$, on note $\mathcal{D}(n)$ le nombre de solutions dans $\mathbb{N}^2$ de l'équation $ax+by=n$ ($\mathcal{D}(n)$ s'appelle le dénumérant de l'équation $ax+by=n$). Alors $\mathcal{D}(r) = 0$ ou $1$ et
$$\mathcal{D}(c) = \left \lfloor \frac{c}{ab} \right \rfloor + \mathcal{D}(r).$$ -
Merci .
-
De rien !
Merci à Jandri pour sa relecture attentive et efficace. (tu) -
Bonjour à tous,
je "réactive" ce fil car il y a un point que je ne comprends pas.
En regardant les solutions dans $\mathbb{N}$ de l'équation $3x + 7y = 42$, si je ne me trompe pas, le théorème indique que le nombre de solutions est 2 puisque le reste de la division de 42 par 21 est 0.
Or, je trouve les solutions suivantes de (x;y) : (14;0), (7;3) et (0;6)
Si les solutions étaient à prendre dans $\mathbb{N}^*$, je n'en aurais qu'une et dans $\mathbb{N}$, j'en ai 3.
Qu'est-ce que je n'ai pas vu/compris ?
Je vous en remercie par avance
DZE -
Avec les notations ci-dessus, $r=0$, donc $\mathcal{D}(r) = 1$ car l'équation $3x+7y=0$ a pour solution le couple $(0,0)$ dans $\mathbb{N}^2$, et comme $\lfloor c/(ab) \rfloor = 2$, on en déduit que le nombre de solutions dans $\mathbb{N}^2$ de l'équation $3x+7y=42$ est égal à $2+1=3$.
-
Ici, le reste $r$ de la division euclidienne de $c=42$ par $ab=21$ vaut $0$, et l'équation $ax+by=0$ possède une solution dans $\N^2$ qui vaut $(0,0)$ donc on trouve que \[\mathcal{D}(c)=\left\lfloor\frac{c}{ab}\right\rfloor+\mathcal{D}(0)=2+1=3\]
-
Dans ce cas de figure, cela ne fait-il pas 4 solutions : (14;0), (7;3), (0;6) et (0;0) ?
Supposant que (0;0) est solution de $\mathcal{D}(0)$, ça me laisse perplexe.
-
(0;0) n’est pas une solution.
The real danger is not that computers will begin to think like men, but that men will begin to think like computers.
-- Harris, Sidney J. -
Dans ce cas, quels sont les valeurs de $x$ et $y$ qui correspondent à $\mathcal{D}(0)$ ?
-
Bonjour.C'est dit juste au dessus par Noixdetoto et Bisam. Nicolas te dit que (0,0) n'est pas une solution de 3x+7y=42.Cordialement.
-
Je vous remercie tous beaucoup de vos réponses.
J'ai compris que je faisais l'amalgame entre "Nombre de solutions" et solutions elles-mêmes. ;-)
Bonne journée à tous
DZE
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 65 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 344 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 805 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres