Les équations Diophantiennes

Qui était Diophante ?

Avant de s'attaquer à la méthode de résolution de ces équations géniales, intéressons-nous à l'homme qui les étudia par le passé. Il se nomme Diophante d'Alexandrie, Mathématicien Grecque ayant vécu, suivant les sources, entre le premier et le quatrième siècle avant Jésus-Christ. Il est célèbre dans l'univers des mathématiques pour son ouvrage "Arithmética" qui passe pour avoir inspiré Pierre de Fermat dans son Dernier Théorème :

Il n'existe pas d'entiers x, y, z tels que       $x^n + y^n = z^n$      dès que n > 2

 Si l'on pose une équation Diophantienne telle que $ax + by = c$, que l'on isole le y, on trouve : (c - ax)/b = y soit une fonction affine. A noter que la forme $ax + by + (-c) = 0$ est dite cartésienne. L'ensemble des points de coordonnées entières de cette droite sont solutions de l'équation.


Méthode de résolution

Donner l'ensemble des couples de solutions tels que 5u + 7v = 22

Étape 1

Ramenons dans un premier temps l'équation à  $5u + 7v = 1$
Comme 5 et 7 sont premiers entre eux (car PGCD(7,5)=1) alors, d'après le Théorème de Bézout, cette équation admet des couples (u;v) d'entiers tels que $5u + 7v = 1$

Étape 2

Recherchons un couple de solution de cette équation. Il existe plusieurs méthodes.
  • Utilisation de l'algorithme d'Euclide pour déterminer un couple de solutions.
$7 = 5*1 +2$

$5 = 2*2 + 1$

$2 = 1*2 + 0$

On cherche à obtenir la forme $5u + 7v = 1$

$7-5*1 = 2$ (première ligne)

 $5-2*(7-5*1) = 1$ (deuxième ligne, on remplace 1 par 7-5*1)

 $3*5 + (-2)*7 = 1$ (on regroupe les 5 et les 7)

 Ainsi, un couple de solutions (u;v) de l'équation $5u + 7v=1$ est (3;-2). Par conséquent, un couple de solutions de l'équation $5u + 7v = 22$ est (3*22 ; -2*22) soit (66 ; -44).
  • Utilisation d'un algorithme (Texas-Instrument) 
La méthode algorithmique est plus rapide. Néanmoins, elle reste une solution de dernier recours.

On part du principe que l'équation s'écrit de la façon suivante : au + bv = 1


Input a,b
-15->u
-15->v
While a*u + b*v <> 1 or v>15
u+1->u
If u>15
Then
-15->u
v+1->v
End
Print u,v
Explication de l'algorithme : On rentre les valeurs de a et b (dans notre cas 5 et 7). L'algorithme teste toutes les combinaisons d'entiers u et v jusqu'à 15 au maximum pour trouver un couple de solution. Il s'agit d'une recherche "force brute" qui permet de créer un programme léger. Il n'est bien sûr pas parfait !


Étape 3
  On cherche à établir une forme générale de solutions.

$5u + 7v = 66*5 - 44*7$

$5u - 66*5 = -7*v - 44*7$

$5*(u - 66) = 7*(-v - 44)$

D'après le Théorème de Gauss, comme 5 et 7 sont premiers entre eux, alors 5 divise (-v - 44) et 7 divise (u - 66) et il existe des entiers k et k' tels que :

$5k = -v - 44$

$7k' = u - 66$

 Soit:

 $v = -5k - 44$

$u = 7k' + 66$

 Etape 4

Il ne reste qu'à montrer que k et k' sont identiques. Si ils ne sont pas identiques, les équations trouvées sont fausses.


$5(7k'+66) + 7(-5k'-44) = 22$

$35k' + 330 -35k' -308 = 22$

$35k' + 22 = 22 +35k$

$35k' = 35k$

$k'=k$

 Conclusion

Les solutions de l'équation Diophantienne $5u + 7v = 22$ sont de la forme :

$u = 7k + 66$
$v = -5k - 44$

Articles populaires

Les sommes : la sommation par paquets

Le principe de la sommation par paquet est de séparer une somme initiale en une somme de sommes (je sais, c'est bizarre !). Par exemple, on peut séparer une somme banale avec d'un côté les nombres pairs et de l'autre les nombres impairs. Cela peut-être d'une aide bienvenue en trigonométrie ou avec $(-1)^k$. Exemple : $$\sum_{k=0}^{2n} k = \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n}{2}}\rfloor} 2k + \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1 = \sum_{k=0}^{n} 2k + \sum_{k=0}^{n-1} 2k + 1$$ Le processus pas à pas : Je commence par construire le membre des nombres impairs en soustrayant -1 à droite (j'ajoute donc +1 à gauche). $$\sum_{k=-1}^{2n-1} k + 1$$ Puis, je remplace k par 2k, et donc je divise -1 et 2n par 2. $$\sum_{k=\frac{-1}{2}}^{\frac{2n-1}{2}} 2k + 1$$ Et je termine par les arrondis supérieurs et inférieurs : $$\sum_{k=\lceil{\frac{-1}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1$$ Je pa
Continuer la lecture

Mo et Mb, différences et conséquences

Image
Vous avez probablement déjà remarqué que l'on parlait tantôt de MégaBits (Mb) et tant ôt de MégaOctet (Mo). Pourquoi cette différence et quelles sont les conséquences pour nous, usager d'internet ? Il suffit pour cela de comprendre la différence entre Byte et Bit. En effet, Mb = Mégabit et MB = Mégabyte. Un bit est la plus petite unité du système informatique (celle qui prend alternativement la valeur 0 ou 1 - le ou est important car dans les ordinateurs quantique, il se transforme en et mais c'est une autre histoire...). Une byte vaut 8 bits. Et un byte vaut également un octet. Pour faire simple, quand il y a un B majuscule, on parle de Byte et quand il y a un b minuscule on parle de bit. Par conséquent, il y a 8 fois moins de "quantité de donnée" dans un Mo que dans un Mb. Or, les Mb sont utilisés pour définir le débit internet. Ainsi, la vitesse maximum d'une carte réseau "standard" (id est équipant la majorité des terminaux
Continuer la lecture

Les démonstrations par récurrence

Image
Le raisonnement par récurrence (avec deux r s'il vous plait) est une méthode de démonstration d'une conjecture, c'est à dire d'une supposition. Une fois la récurrence terminée et la conjecture prouvée, elle deviendra une assertion vraie (sachant qu'une assertion peut-être vraie ou fausse mais pas les deux, c'est le principe dit du "tiers-exclu". Toutefois, les différentes définitions des termes de logique mathématique peuvent parfois différer légèrement et sont sujettes à débat. Le "tiers-exclu" en logique mathématique correspond à la disjonction des propositions p / non p. En clair, sur les deux propositions, l'une des deux est forcément vraie (si p est vraie, alors p est vraie et si p est fausse, non p est vraie...) Si la proposition est vraie à un certain point fixe (ex: n= 1) et, sachant qu'elle est vraie pour un n quelconque elle est aussi vraie pour le n suivant, alors la proposition est vraie pour tous les n plus g
Continuer la lecture