Întrebarea se pare că urmărește să găsească ceva de genul: reprezentarea pe biți a unui număr întreg $a$ când se lucrează modulo $m$. Acest lucru nu este bine definit. Vom presupune că, în schimb, se dorește reprezentarea pe biți a întregului $a\bmod m$.
Prin definiție, numărul întreg $a\bmod m$ este numărul întreg $r$ cu $0\le r<m$ și $a-r$ un multiplu de $m$. Când $a\ge 0$, acest $r$ este restul diviziunii euclidiene a dividendelor $a$ prin divizor $m$, rezultând un coeficient întreg $q$ si restul $r$, astfel încât $0\le r<m$ și $a=m\cdot q+r$.
Pentru a obține reprezentarea unui număr întreg nenegativ în bază $b\ge2$ (cu $b=2$ pentru reprezentarea biților), o metodă standard este împărțirea euclidiană succesivă cu divizor $b$, cu primul dividend numitul întreg nenegativ, apoi dividende ulterioare, câtul obținut prin diviziunea euclidiană anterioară, repetându-se până când câtul este $0$. Resturile succesive sunt cifrele dorite ale reprezentării, cu cifra cea mai puțin semnificativă obținută prima și, de obicei, scrisă în dreapta.
Deci, când vrem reprezentarea biților a 29$\bmod 143$, mai întâi observăm că $0\le29<143$, prin urmare $29\bmod 143=29$. Nu mai avem nevoie de $143$. Vrem doar reprezentarea lui $29$ în bază $2$. Noi scriem
29 = 2 * 14 + 1
14 = 2 * 7 + 0
7 = 2 * 3 + 1
3 = 2 * 1 + 1
1 = 2 * 0 + 1
Resturile obținute sunt ultimele numere întregi de pe fiecare linie și dau expresia binară a $29$, acesta este 11101, cu prima obtinuta in dreapta.
Bitul la index $i$ din dreapta (începând cu index $i=0$, asta este ${i+1}^\text{th}$ un pic de $a\bmod m$ poate fi obtinut ca
$$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$
Metoda din întrebare folosește în schimb
$$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$
care este definit pentru impar $m$ numai și, atunci când este așa, poate fi rescris (cu o extensie a$\bmod$notație pentru a acoperi fracții)
$$\left(\frac a{2^i}\bmod m\right)\bmod2$$
care este oarecum similar cu \eqref{fgrieueq1}, dar nu funcționează în mod fiabil dincolo de $i=0$. De exemplu, eșuează oricând $i=1$, $m=2^k+1$ cu $k>1$, și ciudat $a$ cu $0<a<m$. Deoarece această metodă nu are nicio justificare, nu are nevoie de o respingere dincolo de un contraexemplu.
