Skip to main content
2 of 4
Thank you fgrieu for notation correction.

Get bit i when modulo n

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:

$29 \equiv \textbf{1}$ (mod 2)

$29* (2^{-1}$ mod $143)^1$ mod $143$ $ \equiv 29*72^1$ mod $143 =86\equiv\textbf{0}$ (mod $2$)

$29* (2^{-1}$ mod $143)^2$ mod $143$ $ \equiv 29*72^2$ mod $143 =43\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^3$ mod $143$ $ \equiv 29*72^3$ mod $143 =93\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^4$ mod $143$ $ \equiv 29*72^4$ mod $143 =118\equiv\textbf{0}$ (mod $2$)

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