Вопрос, по-видимому, направлен на то, чтобы найти что-то вроде: битовое представление целого числа $а$ при работе по модулю $м$. Это не очень хорошо определено. Мы предположим, что вместо этого требуется битовое представление целого числа. $а\bмод м$.
По определению целое число $а\bмод м$ целое число $г$ с $0\le r<m$ и $а-р$ кратное $м$. Когда $a\ge 0$, это $г$ остаток от евклидова деления дивиденда $а$ по делителю $м$, что дает целочисленное частное $q$ и остаток $г$, такой, что $0\le r<m$ и $a=m\cdotq+r$.
Чтобы получить представление неотрицательного целого числа по основанию $b\ge2$ (с $б=2$ для битового представления) стандартным методом является последовательное евклидово деление на делитель $b$, где первым делимым является указанное неотрицательное целое число, затем последующим делимым(ями) является частное, полученное в результате предыдущего евклидова деления, повторяющееся до тех пор, пока частное не будет $0$. Последовательные остатки - это желаемые цифры представления, причем наименее значащая цифра получается первой и обычно пишется справа.
Итак, когда нам нужно битовое представление $29\bmod 143$, сначала отметим, что $0\le29<143$, таким образом $29\bmod 143=29$. Мы больше не нуждаемся в $143$. Нам просто нужно представление $29$ в базе $2$. Мы пишем
29 = 2 * 14 + 1
14 = 2 * 7 + 0
7 = 2 * 3 + 1
3 = 2 * 1 + 1
1 = 2 * 0 + 1
Полученные остатки являются последними целыми числами в каждой строке и дают двоичное выражение $29$, это 11101, с первым полученным справа.
Бит по индексу $я$ справа (начиная с индекса $я=0$, это ${я+1}^\текст{й}$ немного $а\bмод м$ можно получить как
$$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$
Вместо этого метод в вопросе использует
$$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$
который определен для нечетного $м$ только, и когда это может быть переписано (с расширением$\bmod$обозначение для обозначения дробей)
$$\left(\frac a{2^i}\bmod m\right)\bmod2$$
который чем-то похож на \eqref{fgrieueq1}, но не работает надежно за пределами $я=0$. Например, он терпит неудачу всякий раз, когда $я=1$, $м=2^к+1$ с $к>1$, и нечетный $а$ с $0<a<m$. Поскольку этот метод не имеет оправдания, он не нуждается в опровержении, кроме контрпримера.
