Z et Bézout et python

noelfred · January 2019

Bonjour
J'ai trouvé cette démonstration dans un livre de spécialité actuelle en terminale scientifique, est-ce une démonstration correcte ?

Questions :
Pourquoi commencer par "Soient" ? Ne serait-il pas plus adéquat de mettre "Pour tous" à la ligne 1 de la preuve.
Puis si d divise c et c divise alors d n'est pas forcément égale a c, 3 divise -3 et -3 divise 3.

Texte :
Identité de Bézout :Soient a et b deux entiers relatifs non tous les deux nuls et d = PGCD(a,b) alors ils existent u et v entiers relatifs tels que au + bv = d

Soit E l'ensemble des entiers naturels non nuls qui s'écrivent de la forme a*u + b*v, où u et v sont deux entiers relatifs non tous les deux nuls.
E n'est pas vide, il contient a = a*1 + b* 0 et b = a*0 + b*1.
Soit c le plus petit élément de E ( c s'écrit sous la forme a*u0 + b*v0, avec u0 et v0 étant deux entiers relatifs ) et d le PGCD de a et de b. On va montrer que c = d, et pour cela montrer que d divise c et c divise d.
- d/a et d/ b donc d divise c = au0 + bv0.
- Pour montrer que c divise d, on montre qu'il divise a et b. On effectue la division euclidienne de a par c : a = cq + r où q et r sont des entiers tels que 0<= r < c.
On a alors r = a - cq = a -(au0 + bv0)q = a(1-u0q) - b(v0q), donc nécessairement r = 0 ( si r> 0 alors r appartient à E et r < c d'où la contradiction), par conséquent c divise a. On montre de même que c divise d. On a montré que d = c = au0 + dv0)
'''
PS.
Puis dans Z, la division euclidienne le reste peut être négatif ? Par exemple :
i) La division euclidienne de 15 par 4 donne 15 = 3 * 4 + 3 ssi 15 = 3 [4]
ii) La division euclidienne de -15 par -4 donne -15 = 3 * -4 - 3 ssi -15 = -3 [-4] et python3 donne -15//-4 = 3 et -15%-4 = -3
iii) La division euclidienne de -15 par 4 donne -15 = -4 * 4 + 1 ssi -15 = 1 [4] et python3 donne -15//4 = -4 et -15%4 = 1
iv) La division euclidienne de 15 par -4 donne 15 = -3 * -4 + 3 ssi 15 = 3 [-4] et python3 donne 15//-4 = -4 et 15%-4 = -1

La i) Ok r positif
La ii) semble plutôt correct en effet a,b,c relatifs et n naturel a = b [n] => ca = cb [cn] en particulier pour c = -1, même si le reste est négatif.
La iii) Ok r positif
La iv) Mathématiquement : a, b entiers a = b [n] <=> a = b [-n] donc cela semble Ok mais niveau machine je ne vois rien qui justifie, et même cela ne fausse-t-il pas tous les programmes tel que Euclide étendu ?

PS bis.
24 et -17 sont premiers entre eux ? pgcd(24,-17) = -1 ou 1
Je sais juste que Z muni de la relation d'ordre divise, 0 est le plus grand élément et 1 le plus petit.
Je vous remercie.

[Même dans le titre Étienne Bézout (1730-1783) prend toujours une majuscule. AD]

GaBuZoMeu · January 2019

Bonjour,

Ce n'est pas la ligne 1 de la preuve : c'est l'énoncé.
Dans les textes mathématique, le "Soit $A$" est souvent utilisé dans le sens de "Pour tout $A$". Notamment quand ce "Soit" commence une phrase complète décrivant les propriétés de l'objet $A$. La phrase suivante commence souvent par un "Alors".
Il y a aussi des cas où le "Soit $A$" introduit une définition de l'objet $A$ en fonction d'autres objets précédemment introduits.

Pour l'histoire de $c$ et $d$ : il s'agit de deux entiers naturels, et donc c'est bien vrai que si $c$ divise $d$ et $d$ divise $c$, alors $c=d$.

Le reste dans la division euclidienne classique de $a$ par $b$ (y compris d'entiers relatifs) est toujours supérieur ou égal à $0$ et strictement inférieur à $|b|$.
On peut aussi faire des divisions euclidiennes où le reste est supérieur ou égal à $-|b|/2$ et strictement inférieur à $|b|/2$ (ça peut accélérer un peu l'algorithme d'Euclide).

michael · January 2019

Salut,

pour ta première question : ce n'est pas la preuve mais l'énoncé du résultat que l'on veut démontrer.
Cela dit, on veut montrer un résultat pour tous nombres $a$ et $b$ entiers relatifs non tous les deux nuls.
Pour cela, il suffit d'en prendre deux quelconques : en disant "soient $a$ et $b$ deux entiers relatifs non tous les deux nuls", on n'impose rien sur $a$ et $b$ sinon qu'ils soient entiers relatifs et non tous les deux nuls. Ce que l'on va faire pour la suite, marchera donc pour n'importe quelle paire de nombres entiers relatifs non tous les deux nuls.
L'avantage de commencer par "soient ..." plutôt que par "pour tout ..." est qu'on n'aura pas à quantifier chaque fois qu'interviennent $a$ ou $b$. Dans le cas contraire, c'est un peu lourd à rédiger :

Pour tous $a$ et $b$ entiers relatifs non tous les deux nuls, on note $E_{a,b}$ l'ensemble des entiers naturels non nuls qui s'écrivent de la forme $au + bv$, où $u$ et $v$ sont deux entiers relatifs non tous les deux nuls.
Pour tous $a$ et $b$ entiers relatifs non tous les deux nuls, $E_{a,b}$ n'est pas vide, il contient $a = a \times 1 + b \times 0$ et $b = a \times 0 + b \times 1$.
etc.

Concernant ta deuxième question : $d$ est le PGCD de $a$ et $b$, c'est donc un nombre positif par définition.
$c$ appartient à $E$ donc, par définition de $E$, $c$ est également un nombre positif.
Par conséquent, si $c$ divise $d$ et si $d$ divise $c$, on a bien $c=d$.
Si $c$ et $d$ étaient des entiers relatifs, alors, tu as raison, on aurait $c=d$ ou $c=-d$.

Au sujet de tes questions sur la division euclidienne : le théorème de la division euclidienne dans $\mathbb{Z}$ (le seul que je connaissance, en tout cas) dit que pour tous nombres entiers relatifs $a$ et $b$ avec $b$ non nul, il existe un unique entier relatif $q$ et un unique entier naturel $r$ tels que $a=bq+r$ avec $0 \leq r < |b|$.
$r$ doit donc être positif.
Si on choisit $r$ tel que $|r| < |b|$, on perd l'unicité :
$17 = 3 \times 5 + 2$ avec $2

$
$17 = 3 \times 6 - 1$ avec $|-1| < 3$.

Edit : grillé par GaBuZoMeu.

Philippe Malot · January 2019

Bonsoir,
Attention, $a$ et $b$ ne sont pas forcément dans $E$ (s'ils sont négatifs).

brian · January 2019

Bonjour noelfred, et bienvenue sur le forum !

Une dernière précision : comme tu l'as remarqué, les opérateurs // et % de Python ne donnent pas le quotient et le reste de la division euclidienne classique dans $\Z$. La définition précise de ces opérateurs est ici. On peut obtenir la division euclidienne classique dans $\Z$ de cette manière :

def divEucl(a, b):
    if b > 0:
        return divmod(a, b)
    elif b < 0:
        return (-(a//-b), a % -b)
    else:
        raise ZeroDivisionError("division by zero")

Test rapide de cette fonction (syntaxe supportée à partir de Python 3.6 ; pour les versions 3.x antérieures, utiliser str.format() au lieu de la f-string) :

for a, b in [(10, 4), (-10, 4), (10, -4), (-10, -4)]:
    print(f"divEucl({a}, {b}) =", divEucl(a, b))

->

divEucl(10, 4) = (2, 2)
divEucl(-10, 4) = (-3, 2)
divEucl(10, -4) = (-2, 2)
divEucl(-10, -4) = (3, 2)

Z et Bézout et python

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 7