La fonction β de Gödel

Soit $s = \max(n, k_0, \dots, k_n) + 1$, $b = s!$, et $m_i = 1 + (i + 1)b$ pour $i \leqslant n$. On a $m_i > b \geqslant s > k_i$.

Les $m_i$ sont premiers entre eux deux à deux. Soit $i < j \leqslant n$ et $p$ un nombre premier qui divise $m_i$ et $m_j$. Il divise $m_j - m_i = (j - i)b$. Il ne divise pas $b$, sinon il diviserait $m_i - (i + 1)b = 1$ ; par le lemme d'Euclide (Nombres premiers, (i)), il divise donc $j - i$. Mais $1 \leqslant j - i \leqslant n < s$, donc $j - i$ divise $s! = b$, et $p$ diviserait $b$.

Ainsi $m_i$ et $m_j$ n'ont aucun diviseur premier commun ; comme tout entier $d \geqslant 2$ a un diviseur premier, $m_i \wedge m_j = 1$.

Restes chinois. Montrons par récurrence sur $l \leqslant n$ qu'il existe $a_l \in {\mathbb Z}$ tel que $a_l \equiv k_i$ modulo $m_i$, c'est-à-dire que $m_i$ divise $a_l - k_i$, pour tout $i \leqslant l$. On prend $a_0 = k_0$.

Supposons $a_l$ construit, avec $l < n$, et soit $M = m_0 \cdots m_l$. Un diviseur premier commun à $M$ et à $m_{l+1}$ diviserait l'un des $m_i$, par le lemme d'Euclide ; donc $M \wedge m_{l+1} = 1$, et Bézout (PGCD, Bézout, (ii)) donne $u, v \in \mathbb Z$ tels que $uM + vm_{l+1} = 1$. On pose $$a_{l+1} = a_l + (k_{l+1} - a_l)\, uM.$$ Modulo chaque $m_i$, $i \leqslant l$, on a $a_{l+1} \equiv a_l$ ; modulo $m_{l+1}$, $uM \equiv 1$ et $a_{l+1} \equiv k_{l+1}$.

Soit enfin $a \in {\mathbb N}$ le reste de la division de $a_n$ par $m_0 \cdots m_n$. Pour chaque $i$, $a \equiv k_i$ modulo $m_i$ et $0 \leqslant k_i < m_i$ : par unicité de la division euclidienne, $k_i$ est le reste de $a$ par $m_i$, c'est-à-dire $\beta(a, b, i)$.