Get bit i when modulo n

Question

Is there a way to recover the bit sequence of a number ( for example 29 = 0b11101 ) by always dividing it by 2 when in mod 143 for example ?

What I mean by that is recover the number bit by bit by multiplying it by the inverse of 2 mod 143 to simulate the /2 division. for example:
$\begin{array}{} &29\bmod143=&29&\equiv 1 \pmod 2\\ 29\cdot(2^{-1}\bmod143)^1\bmod143=&29\cdot72^1\bmod143=&86&\equiv0\pmod2\\29\cdot(2^{-1}\bmod143)^2\bmod143=&29\cdot72^2\bmod143=&43&\equiv1\pmod2\\ 29\cdot(2^{-1}\bmod143)^3\bmod143=&29\cdot72^3\bmod143=&93&\equiv1\pmod2\\ 29\cdot(2^{-1}\bmod143)^4\bmod143=&29\cdot72^4\bmod143=&118&\equiv0\pmod2\\ \end{array}$

We can see that the sequence I obtain is correct until the fifth bit, which should be $1$. What am I misunderstanding here ?

Answer 1

The question apparently aims to find something like: the bit representation of an integer $a$ when working modulo $m$. This is not well defined. We'll suppose that instead, it's wanted the bit representation of the integer $a\bmod m$.

By definition, the integer $a\bmod m$ is the integer $r$ with $0\le r<m$ and $a-r$ a multiple of $m$. When $a\ge 0$, this $r$ is the remainder of the Euclidean division of dividend $a$ by divisor $m$, yielding integer quotient $q$ and remainder $r$, such that $0\le r<m$ and $a=m\cdot q+r$.

To obtain the representation of a non-negative integer in base $b\ge2$ (with $b=2$ for the bit representation), a standard method is successive Euclidean division by divisor $b$, with first dividend the said non-negative integer, then subsequent dividend(s) the quotient obtained by the previous Euclidean division, repeating until the quotient is $0$. The successive remainders are the desired digits of the representation, with the Least Significant Digit obtained first, and usually written on the right.

So when we want the bit representation of $29\bmod 143$, we first note that $0\le29<143$, thus $29\bmod 143=29$. We no longer need the $143$. We just want the representation of $29$ in base $2$. We write

    29 = 2 * 14 + 1
    14 = 2 *  7 + 0
     7 = 2 *  3 + 1
     3 = 2 *  1 + 1
     1 = 2 *  0 + 1

The remainders obtained are the last integers on each line, and give the binary expression of $29$, that is 11101, with the first obtained on the right.

---

The bit at index $i$ from the right (starting at index $i=0$, that is the ${i+1}^\text{th}$ bit) of $a\bmod m$ can be obtained as $$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$

The method in the question instead uses $$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$ which is defined for odd $m$ only, and when so can be rewritten (with an extension of the$\bmod$notation to cover fractions) $$\left(\frac a{2^i}\bmod m\right)\bmod2$$ which is somewhat similar to \eqref{fgrieueq1}, but does not work reliably beyond $i=0$. For example it fails whenever $i=1$, $m=2^k+1$ with $k>1$, and odd $a$ with $0<a<m$. Since that method comes with no justification, it does not need a refutation beyond a counterexample.