[Maths] [L1] Arithmétique sur les entiers 2

doryphore · 28/10/2005 - 20h52

Soient a et b $\geq$ 2 deux entiers naturels non nuls premiers entre eux.

1/ Montrer que $\exists ! (u_0,v_0) \in \mathbb{N}^2, \, u_0a-v_0b=1$ , avec $u_0<b$ et $v_0<a$ et exprimer en fonction de $u_0, \, v_0$ , a et b tous les couples $(u,v) \in \mathbb{Z}^2$ solutions de $ua-vb=1$ .

2/ Déterminer deux entiers u et v vérifiant $47u+111v=1$

iwio · 28/10/2005 - 23h56

Pour la 2
Alors on trouve u=26 et v=-11
Pour les détailles, je les écrirais demain. En attendant je vous laisse réfléchir.

AriesSith · 29/10/2005 - 01h12

Alors, une solution un peu abracadabrante :
a et b $\geq$ 2 sont deux entiers naturels premiers entre eux

D'après le théorème de Bezout $\exist (u,v) \in \mathbb{Z}^2$ tel que $au + bv = 1$

Donc il existe $(u,v)$ vérifiant $au-bv = 1$ (cf théorème de Bézout en remplaçant v par -v)

De plus,
$\exists ! (q_1,r_1) \in \mathbb{N}^2, \, u=bq_1 +r_1$ , avec $r_1<b$
$\exists ! (q_2,r_2) \in \mathbb{N}^2, \, v=aq_2 +r_2$ , avec $r_2<a$

En posant $(u_0;v_0) = (r_1;r_2)$ on obtient :

$u=bq_1 +u_0$
$v=aq_2 +v_0$

Ce qui équivaut à,
$u-bq_1 = u_0$
$v-aq_2 = v_0$

D'où, $a u_0 - bv_0 = 1-ab(q_1-q_2)$

Mais là je bloque ...

iwio · 29/10/2005 - 09h27

Pour la 2

111 = 47*2 + 17
47 = 17*2 + 13
17 = 13*1 + 4
13 = 4*3 + 1

=> 1=13 - 4*3
1 = 13 - 3(17-13) = 4*13 - 3*17
1 = 4(47-2*17) - 3*17 = 4*47 - 11 * 17
1 = 4*47 - 11(111-2*47)
1 = 26*47 - 11*111

finalement : u=26 et v=-11

iwio · 29/10/2005 - 10h02

Pour la 1

$\( au-bv = 1 \\ au_0-bv_0 = 1$

Donc
$au-bv = au_0-bv_0$
$a(u-u_0) = b(-v-v_0)$

$b | a(u-u_0)$ or a et b sont premiers entre eux, alors

$b \mid (u-u_0)$

on fait pareil pour a, on trouve $a | (-v-v_0)$

On obtient : $(k \in Z)$

$\( kb=u-u_0 \\ ka = -v-v_0$

$\( u=kb+u_0 \\ v = -ka - v_0$

AriesSith · 29/10/2005 - 11h31

Envoyé par iwio

Pour la 1

$\( au-bv = 1 \\ au_0-bv_0 = 1$

Donc
$au-bv = au_0-bv_0$
$a(u-u_0) = b(-v-v_0)$

$b | a(u-u_0)$ or a et b sont premiers entre eux, alors

$b \mid (u-u_0)$

on fait pareil pour a, on trouve $a | (-v-v_0)$

Jusque là je suis d'accord à condition de prouver l'existence de u et de v tel que $au-bv = 1$

On obtient : $(k \in Z)$

$\{ kb=u-u_0 \\ ka = -v-v_0$

$\{ u=kb+u_0 \\ v = -ka - v_0$

C'est ce qui me manquait dans ma démo !

Bravo !

Peut-on en avoir d'autres des exercices ?

iwio · 29/10/2005 - 11h43

Envoyé par AriesSith

Jusque là je suis d'accord à condition de prouver l'existence de u et de v tel que $au-bv = 1$

Je comprend pas trop ce que tu veux dire. Tu veux que je dise que si a et b, sont premiers entre eux, alors "Théorème de Bezout", il existe une infinité de couple $(u,v) \in N²$ tel que aU+bV = 1. avec ici $\{ V=-v \\ U=u$
=> au - bv = 1

C'est ça ?

AriesSith · 29/10/2005 - 12h10

par exemple ... oui

iwio · 29/10/2005 - 12h37

Envoyé par AriesSith

par exemple ... oui

Donc je comprend pas trop, mais j'ai réussi à répondre ^^

AriesSith · 29/10/2005 - 15h59

Et bien dans la question posée il me semble qu'il est demandé l'existence et l'unicité c'est juste un point de détail... mais je suis d'accord, tu as trouvé le résultat.

iwio · 29/10/2005 - 19h24

Je ne crois pas que l'on demande l'unicité. Il demande pas tous les couples (u,v) $\in$ Z² ?

AriesSith · 29/10/2005 - 19h37

Bonsoir !
Je parle de l'existence et de l'unicité de $(u_0;v_0)$ c'est la première partie de la question 1.

iwio · 29/10/2005 - 20h14

Oui j'avais pas vu. $\exists ! (u_0,v_0) \in \mathbb{N}^2$
Mais, je sais pas comment démontrer l'unicité.
Sauf peut être, en disant d'après le théorème de Bezout...