Before the function it self, there are some auxiliary functions that need to be defined.

First we come up with the quotient and remainder functions. For all $𝑚,𝑛\in 𝜔$, let $\text{quo}\left(𝑚,𝑛\right)$ and $\text{rem}\left(𝑚,𝑛\right)$ be the quotient and remainder of $𝑚$ divided by $𝑛$, respectively, if $𝑛\ne 0$, and $0$ otherwise.

Then follows the (floored) square root and exceedence functions. For all $𝑛\in 𝜔$, let $\left[\sqrt{𝑛}\right]$ be the largest number $𝑘$ that ${𝑘}^2\le 𝑛$, and $\mathrm{K}\left(𝑛\right)=𝑛-{\left[\sqrt{𝑛}\right]}^2$.

Now comes the $\mathrm{J}$ and $\mathrm{L}$ functions, named after what Gödel named them. Let $\mathrm{J}\left(𝑚,𝑛\right)={\left({\left(𝑚+𝑛\right)}^2+𝑛\right)}^2+𝑚$, and $\mathrm{L}\left(𝑛\right)=\mathrm{K}\left(\left[\sqrt{𝑛}\right]\right)$. The definitions may seems weird at first glance, but they would soon show their power. And they have great properties: for all $𝑚,𝑛\in 𝜔$, $\mathrm{K}\left(\mathrm{J}\left(𝑚,𝑛\right)\right)=𝑚$ and $\mathrm{L}\left(\mathrm{J}\left(𝑚,𝑛\right)\right)=𝑛$. The proof goes as follows.

For that property of $\mathrm{K}$ and $\mathrm{J}$, it suffices to show that $\left[\sqrt{\mathrm{J}\left(𝑚,𝑛\right)}\right]={\left(𝑚+𝑛\right)}^2+𝑛$, and this can be brought out by the fact that

That property of $\mathrm{L}$ and $\mathrm{J}$ is also easy following similar approach. These two properties means that the arguments of $\mathrm{J}$ can be extracted from the result of it, and that means $\mathrm{J}$ is an 1-1 function.

Finally, the Gödel’s β function is defined by $𝛽\left(𝑚,𝑖\right)=\text{rem}\left(\mathrm{K}\left(𝑚\right),1+\left(𝑖+1\right)·\mathrm{L}\left(𝑚\right)\right)$. (Note that this is not the original definition (3-ary) but a simplified 2-ary one.) The definition is also a bit of complicated, but the following lemma tells us about why it is amazing.

For all ${𝑚}_0,\dots ,{𝑚}_{𝑛-1}\in 𝜔$, there exists a $𝑚\in 𝜔$ such that

for all $𝑖<𝑛$.

And the the proof entails an algorithm to calculate such an $𝑚$.

Before the proof, we need to prove two preliminary propositions.

(Note that this lemma is a weaken version of the original theorem.)

If $𝑚,𝑛\in 𝜔$ and they are coprime, then $𝑎𝑚+𝑏𝑛=1$ for some integers $𝑎$ and $𝑏$.

Proof: Let $𝑆=\left\{𝑎𝑚+𝑏𝑛\mid 𝑎𝑚+𝑏𝑛\in 𝜔\right\}$, i.e. the set of all positive (integral) linear composition of $𝑚$ and $𝑛$. Thus there must be a minimum value $𝑝\in 𝑆$ for this non-empty set (the non-emptiness is trivial). What this proof wants to show is that $𝑝=1$. We prove this by contradiction. Assume that $𝑝\ne 1$. Take $𝑞\in 𝑆$, let $𝑟=\text{rem}\left(𝑞,𝑝\right)$, we have $0\le 𝑟<𝑝$. And $\text{rem}\left(𝑞,𝑝\right)\in 𝑆$ since $𝑝$ and $𝑞$ are both (integral) linear composition of $𝑚$ and $𝑛$, so $\text{rem}\left(𝑞,𝑝\right)$ must be $0$, otherwise it contradicts with the minimality of $𝑝$. Then we have $𝑝\mid 𝑞$ for all $𝑞\in 𝑆$. Note that $𝑚\in 𝑆$ and $𝑛\in 𝑆$, so $𝑝$ is a common divisor of $𝑚$ and $𝑛$, which leads to the contradiction toward the coprimality of $𝑚$ and $𝑛$ if $𝑝\ne 1$.

For all ${𝑘}_0,\dots ,{𝑘}_{𝑛-1}\in 𝜔$, if ${𝑑}_0,\dots ,{𝑑}_{𝑛-1}\in 𝜔$ are pairwise coprime and ${𝑘}_{𝑖}<{𝑑}_{𝑖}$ for all $𝑖<𝑛$, then there exists a $𝑘\in 𝜔$ such that $\text{rem}\left(𝑘,{𝑑}_{𝑖}\right)={𝑘}_{𝑖}$ for all $𝑖<𝑛$.

Proof: For each $𝑖<𝑛$, let ${𝑚}_{𝑖}=\frac{{𝑑}_0\cdots {𝑑}_{𝑛-1}}{{𝑑}_{𝑖}}$. Since ${𝑑}_0,\dots ,{𝑑}_{𝑛-1}$ are pairwise coprime, ${𝑚}_{𝑖}$ and ${𝑑}_{𝑖}$ are coprime. By Bézout’s Lemma, there are integers ${𝑎}_{𝑖}$ and ${𝑏}_{𝑖}$ such that ${𝑎}_{𝑖}{𝑚}_{𝑖}+{𝑏}_{𝑖}{𝑑}_{𝑖}=1$. The insight here is that for each ${𝑑}_{𝑖}$, we construct the number that its remainder divided by ${𝑑}_{𝑖}$ is ${𝑘}_{𝑖}$, and compose these constructed numbers in a way that they won’t affect each other. Note that ${𝑚}_{𝑖}$ cannot be divided by ${𝑑}_{𝑖}$, can be divided by ${𝑑}_{𝑗}$ for any $𝑗<𝑛$ where $𝑗\ne 𝑖$, and there is an $1$ on the right hand side of the equation we got from the Bézout’s Lemma. It is easy to see that, now it suffices to take

where $𝑙$ is any natural number such that $𝑘\ge 0$.

Finally we come to the proof of the lemma. From the definition of $\mathrm{J}$ and $𝛽$, we can see that we only need to find a proper value of $\mathrm{L}\left(𝑚\right)$ such that the numbers $1+\left(𝑖+1\right)·\mathrm{L}\left(𝑚\right)$ for each $𝑖<𝑛$ coprime, then construct the value of $\mathrm{K}\left(𝑚\right)$ by Chinese Remainder Theorem, and calculate the $𝑚=\mathrm{J}\left(\mathrm{K}\left(𝑚\right),\mathrm{L}\left(𝑚\right)\right)$. For convenience, denote $1+\left(𝑖+1\right)·\mathrm{L}\left(𝑚\right)$ by ${𝑑}_{𝑖}$ for each $𝑖<𝑛$.

What conditions should the value of $\mathrm{L}\left(𝑚\right)$ satisfy? First, it must make ${𝑑}_{𝑖}=1+\left(𝑖+1\right)·\mathrm{L}\left(𝑚\right)>{𝑚}_{𝑖}$, which is one of the conditions asked by Chinese Remainder Theorem. Second, it makes those ${𝑑}_{𝑖}$’s pairwise coprime. To prove propositions like ‘there is no prime $𝑝$ such that $𝑝\mid {𝑑}_{𝑖}$ and $𝑝\mid {𝑑}_{𝑗}$ for different $𝑖,𝑗<𝑛$’, consider proof by contradiction. Think about what if there is some prime $𝑝$ such that $𝑝\mid {𝑑}_{𝑖}$ and $𝑝\mid {𝑑}_{𝑗}$ for different $𝑖,𝑗<𝑛$, i.e. $𝑝\mid 1+\left(𝑖+1\right)·\mathrm{L}\left(𝑚\right)$ and $𝑝\mid 1+\left(𝑗+1\right)·\mathrm{L}\left(𝑚\right)$. Assume $𝑖<𝑗$ without loss of generality, we have $𝑝\mid \left(𝑗-𝑖\right)·\mathrm{L}\left(𝑚\right)$. It will be good if we have $𝑝\mid \mathrm{L}\left(𝑚\right)$, which would lead to the contradiction that $𝑝\mid 1$. So things become evident: find a construction of $\mathrm{L}\left(𝑚\right)$ such that $\left(𝑗-𝑖\right)\mid \mathrm{L}\left(𝑚\right)$. This can be achived by making $\mathrm{L}\left(𝑚\right)$ divisible by the product of all the possible values of $𝑗-𝑖$, which ranges from $1$ to $𝑛-1$. This is to say, making $\left(𝑛-1\right)!\mid \mathrm{L}\left(𝑚\right)$ would be a good idea. With the first condition that $\mathrm{L}\left(𝑚\right)$ should satisfy, it suffices to take $\mathrm{L}\left(𝑚\right)=𝑙!$, where $𝑙=max\left\{𝑛,{𝑚}_0,\dots ,{𝑚}_{𝑛-1}\right\}$. I take $𝑛$ instead of $𝑛-1$ there for better elegance with the same effect.

The above is not a strictly stated proof, however it is easy to rewrite it into one.