Boolos and Jeffrey in Computability and Logic (3rd ed.) give a proof of the Beta-function Lemma (14.2, pp. 162-3) that makes use of the idea that any finite sequence of natural numbers: $i_0, ..., i_k$ (for any $k$) can be "encoded" into (and then "decoded" from) some ordered pair of natural numbers <p, q> such that:
$p$ is prime and ($p-1$) > $i_0, ..., i_k, k$;
$q = (p-1) *_p 0 *_p i_0 *_p (p-1) *_p 1 *_p i_1 *_p ... *_p (p-1) *_p k *_p i_k$,
where 'a $*_p$ b' is the result (denoted in base-$p$ notation) of concatenating $a$ and $b$ numerals in base-$p$ notation ('$*_p$' associates to the left).
[Then, any $j$-th (for 0 $\leq j \leq k$) member of the sequence can be "decoded" from <p, q> by an appropriately defined Beta-function.]
Question(s): Is the use of primes necessary in this case? What if $p$ were any number such that ($p-1$) > $i_0, ..., i_k, k$?