Exact uniform sampling from the nonzero residue representatives

Input. An integer $N\ge 3$. The random tape is a countable sequence of independent bits, each taking $0$ and $1$ with probability $1\mathrm{/}2$. Its countable product law is supplied by Assuming countable and dependent choice, countable products of arbitrary probability spaces under countable choice and dependent choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$), The axiom of dependent choice: a relation in which every element is related to something admits an $\mathbb{N}$-indexed chain).

Set $M=N-1$ and let $h$ be the binary length of $M-1$, equivalently the least integer with $M\le 2^h$. For each block, read its bits in order as ${\beta }_0,\dots ,{\beta }_{h-1}$, with the first bit most significant, and set $b={\sum }_{j=0}^{h-1}{2}^{h-1-j}{\beta }_j\in \{0,\dots ,2^h-1\}$. If $b\ge M$, discard this block and read the next $h$ bits. Otherwise output $a=b+1$ and halt.

Whenever it halts, the procedure returns an element of $\{1,\dots ,N-1\}$ because an accepted block has $0\le b<M=N-1$ and the output is $b+1$.