取模時得到位 i
例如，在 mod 143 中，有沒有辦法通過始終將其除以 2 來恢復數字的位序列（例如 29 = 0b11101）？
我的意思是通過將數字乘以 2 mod 143 的倒數來逐位恢復數字以模擬 /2 除法。例如：
$ \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} $
我們可以看到我得到的序列直到第五位是正確的，應該是 $ 1 $ . 我在這裡誤解了什麼？
這個問題顯然旨在找到類似的東西：整數的位表示 $ a $ 模數工作時 $ m $ . 這沒有很好的定義。我們假設相反，它需要整數的位表示 $ a\bmod m $ .
根據定義，整數 $ a\bmod m $ 是整數 $ r $ 和 $ 0\le r<m $ 和 $ a-r $ 的倍數 $ m $ . 什麼時候 $ a\ge 0 $ ， 這個 $ r $ 是歐幾里得除法的餘數 $ a $ 按除數 $ m $ , 產生整數商 $ q $ 和剩餘的 $ r $ , 這樣 $ 0\le r<m $ 和 $ a=m\cdot q+r $ .
獲取基數中非負整數的表示 $ b\ge2 $ （和 $ b=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，第一個在右邊獲得。索引位 $ i $ 從右邊（從索引開始 $ i=0 $ ， 那就是 $ {i+1}^\text{th} $ 位）的 $ a\bmod m $ 可以得到 $$ \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 $$ 這是為奇數定義的 $ m $ 只有，當這樣可以重寫（與擴展 $ \bmod $ 符號覆蓋分數） $$ \left(\frac a{2^i}\bmod m\right)\bmod2 $$ 這有點類似於 $ \eqref{fgrieueq1} $ ，但不能可靠地工作 $ i=0 $ . 例如，每當它失敗 $ i=1 $ , $ m=2^k+1 $ 和 $ k>1 $ , 和奇數 $ a $ 和 $ 0<a<m $ . 由於該方法沒有任何理由，因此不需要反例之外的反駁。