TD10 : Constante de Frobenius

EX 1

$G_{a,b} ≝ ⟨a,b⟩$

1.

M1 :

$aℤ + bℤ$ est clairement un groupe, et tout groupe contenant $a,b$ le contient.

M2 :

Une inclusion est triviale, l’autre vient du fait que $(ℤ, +)$ : l’ensemble des mots $(a+b)^*$ (où la concaténation est l’addition) vaut donc

\[aℤ + bℤ\]

2.

L’inclusion $G_{a, b-a} ⊆ G_{a,b}$ est triviale.

Réciproquement, si $xa + yb ∈ G_{a,b}$,

\[xa + yb = (x-y)a + y(b-a) ∈ G_{a,b-a}\]

3.

Sans perte de généralité : $b>a$.

On note $r(b,a)$ (resp. $q(b,a)$) le reste (resp. le quotient) de la div. eucl. de $b$ par $a$.

On pose

• $b_0 ≝ b, a_0 ≝ a$
• $∀n∈ℕ^\ast, b_n ≝ a_{n-1}, a_n ≝ r(b_{n-1}, a_{n-1})$

\[G_{a_0,b_0} = G_{a_0,b_0-q(b_0,a_0)a_0} = G_{b_1,a_1} = G_{a_1,b_1}\]

(par une récurrence immédiate)

Donc par une récurrence immédiate :

\[G_{a_0,b_0} = G_{a_n,b_n}\]

où $a_n = 0$

Un tel indice $n$ existe, car la suite d’entiers $(a_k)_{k}$ est telle que :

\[a_k > 0 ⟹ a_{k+1}<a_k\]

donc cette suite stationne en $0$.

Or, on vérifie aisément que l’ensemble des diviseurs communs $div(a_0, b_0)$ de $a_0, b_0$ vaut $div(a_1, b_1) = div(a_2, b_2) = ⋯ = div(a_n, b_n)$ (par une récurrence immédiate).

Donc

\[a_0∧b_0 = ⋯ = a_n ∧b_n\]

Il vient donc que :

\[G_{a_0,b_0} = G_{0,b_n} \\ = G_{b_n} = G_{a_n ∧b_n} \\ = G_{a_0 ∧b_0} ≝ G_d\]

4.

\[\begin{align*} & xa + yb = d \\ ⟺ & xa + yb = ua + bv \\ ⟺ & (x-u)a = b(v-y) \\ ⟺ & (x-u)a' = b'(v-y) \\ \end{align*}\]

⟹ :

Si $(x-u)a’ = b’(v-y) \hspace{1em} ⊛$, alors

\[a' \mid b'(v-y)\\ ⟺ a' \mid (v-y)\]

(par le lemme de Gauss)

et de même :

\[b' \mid (u-x)\]

Or :

\[(y-v)/a' = (u-x)/b'\]

(en divisant $⊛$ par $-a’b’$)

donc

\[∃k∈ℤ; \begin{cases} x = u - kb' \\ y = v + ka' \end{cases}\]

Réciproquement :

Si \(∃k∈ℤ; \begin{cases} x = u - kb' \hspace{1em} (1)\\ y = v + ka' \hspace{1em} (2) \end{cases}\)

alors

\[a×(1) + b×(2) ⟺ xa + yb = d\]

5.

a).

$aℕ + bℕ$ est un monoïde, et tout monoïde contenant $a, b$ le contient.

b).

$aℤ + bℤ = ℤ$

i.e :

il existe $u, v∈ℤ$ tels que :

\[au + bv =1\]

M1 :

On veut trouver un $N∈ℕ$ tq $∀n≥N, n∈M_{a,b}$.

Soit $N∈ℕ$, $n∈aℤ + bℤ = ℤ$ tel que

\[n>N\]

On va montrer que pour $N$ assez grand, $n∈aℕ + bℕ$

$∀k∈ℤ, n = (u-kb)a + (v+ka)b$

Donc en notant $u’$ le reste de la div eucl de $a$ par $b$ :

\[n=au'+v'b\]

avec $0≤u’<b$

Donc

$n-u’a = v’b$

et si $n≥ba$, alors $v’b ≥0$, donc $v’≥0$

et $N= ba-1$ convient.

M2 :

Si $b>a$ :

$a$ est un générateur de $ℤ/bℤ$, donc pour tout $n ≥ ba$, si

\[n = r = ak \mod b\]

$n ∈ aℕ + bℕ$

c).

Idée de Maher :

\[F_{a,b} = a(b-1)-b = ab - a -b ∉ M_{a,b}\]

c’est le plus grand entier qui n’est pas dans $M_{a,b}$, i.e le plus petit élément de la classe $a(b-1) \mod b = a(b-1) + bℤ$ qui n’est pas dans $M_{a,b}$ : c’est $a(b-1)-b$.