Can one always convert from Rand5 to Rand7 in finitely many iterations? Suppose that there is a machine (called Rand5) that randomly chooses member of the set $\\{1,2,3,4,5\\}$ with uniform distribution. The objective is to use this machine, as many times as we like, to create a new machine (called Rand7) that randomly choose a member of the set $\\{1,2,3,4,5,6,7\\}$ with uniform distribution. There only solution I can think of is to use some form of rejection sampling. For example, you could use the Rand5 machine twice, yielding $25$ equally likely outcomes. Map $21$ of them to evenly select among the numbers from $1$ to $7$, and then repeat the process if the outcome is not one of these $21$ mapped outcomes. This solution has the problem that it is not guaranteed to terminate. Is there a solution to the Rand5 to Rand7 problem that is guaranteed to terminate in finitely many steps? If not, can it proven that there is no such solution?

Assume there is a solution that is guaranteed to terminate. Then there exists some $n$ such that at most $n$ samples of Rand5 are taken (use König's lemma to be precise). Then every path the algorithm takes is taken with a probability a multiple of $\frac1{5^n}$. No sum of such numbers equals $\frac17$ because $7$ does not divide $5^n$, hence there is no proceudre that terminates _for sure_. The best we can get is that it terminates _almost surely_ (i.e. with probability $1$); for example by rejection sampling as you describe it; or by interpreting the sequence of Rand5 outputs as the base 5 expansion of a real numbre in $[0,1)$ and stop as soon as it becomes clear in which interval $[\frac k7,\frac{k+1}7)$ we end up.