Câu hỏi dường như nhằm mục đích tìm một cái gì đó như: biểu diễn bit của một số nguyên $a$ khi làm việc modulo $m$. Điều này không được xác định rõ. Chúng ta sẽ giả sử rằng thay vào đó, nó muốn biểu diễn bit của số nguyên $a\bmod m$.
Theo định nghĩa, số nguyên $a\bmod m$ là số nguyên $r$ với $0\le r<m$ và $a-r$ bội số của $m$. Khi nào $a\ge 0$, cái này $r$ là phần còn lại của phép chia cổ tức Euclide $a$ theo số chia $m$, mang lại thương số nguyên $q$ và phần còn lại $r$, như vậy mà $0\le r<m$ và $a=m\cdot q+r$.
Để có được biểu diễn của một số nguyên không âm trong cơ số $b\ge2$ (với $b=2$ đối với biểu diễn bit), một phương pháp tiêu chuẩn là phép chia Euclide liên tiếp cho số chia $b$, với số bị chia đầu tiên là số nguyên không âm đã nói, sau đó (các) số bị chia tiếp theo là thương thu được từ phép chia Euclide trước đó, lặp lại cho đến khi thương là $0$. Các phần còn lại liên tiếp là các chữ số mong muốn của biểu diễn, với Chữ số có nghĩa nhỏ nhất được lấy trước và thường được viết ở bên phải.
Vì vậy, khi chúng ta muốn biểu diễn bit của $29\bmod 143$, đầu tiên chúng tôi lưu ý rằng $0\le29<143$, do đó $29\bmod 143=29$. Chúng tôi không còn cần $143$. Chúng tôi chỉ muốn đại diện của $29$ ở cơ sở $2$. Chúng tôi viết
29 = 2 * 14 + 1
14 = 2 * 7 + 0
7 = 2 * 3 + 1
3 = 2 * 1 + 1
1 = 2 * 0 + 1
Phần còn lại thu được là các số nguyên cuối cùng trên mỗi dòng và đưa ra biểu thức nhị phân của $29$, đó là 11101, với cái đầu tiên thu được ở bên phải.
Bit tại chỉ mục $i$ từ bên phải (bắt đầu từ chỉ số $i=0$, đó là ${i+1}^\text{th}$ chút) của $a\bmod m$ có thể thu được như
$$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$
Phương pháp trong câu hỏi thay vì sử dụng
$$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$
được định nghĩa cho số lẻ $m$ chỉ, và khi như vậy có thể được viết lại (với phần mở rộng của$\bmod$ký hiệu để bao gồm các phân số)
$$\left(\frac a{2^i}\bmod m\right)\bmod2$$
tương tự như \eqref{fgrieueq1}, nhưng không hoạt động đáng tin cậy ngoài $i=0$. Ví dụ nó thất bại bất cứ khi nào $i=1$, $m=2^k+1$ với $k>1$, và lẻ $a$ với $0<a<m$. Vì phương pháp đó không cần biện minh nên nó không cần bác bỏ ngoài một phản ví dụ.
