Prime-Numbers
如何計算連續模逆的總和？
$ p $ 是一個大素數。 $ p>2^{2048} $ . 那麼如何計算連續模逆的總和 $ p $ ? $$ \sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p $$ 至於 $ p $ 是一個大素數，不可能一個一個地計算模逆，最後求和。我發現有人給出了一個近似結果的公式，但我無法證明。 $$ p - \frac{2^{p}\pmod {p^2}-1}{p} \pmod p $$ 你能幫我證明這個公式，或者給出你的答案來計算總和嗎？衷心感謝！
您要查詢的總和幾乎是 Eisenstein 發現的費馬商恆等式的右側（此處為證明）： $$ -2q_p(2) = \sum_{i=1}^{(p-1)/2} 1/i \pmod{p},, $$ 在哪裡 $ q_p(a) = \frac{a^{p-1} - 1}{p} $ .
因此總和可以計算為 $ -2 \frac{2^{p-1} - 1}{p} \bmod p $ . 因為計算 $ 2^{p-1} $ 對於非常大的情況是不可行的 $ p $ ，並且因為只需要結果除以 $ p $ 然後再次減少 $ p $ , 計算 $ \frac{2^{p-1} - 1}{p} $ 可以執行為 $ \frac{(2^{p-1} \bmod p^2) - 1}{p} $ 沒有任何精度損失。並吸收那個因素 $ 2 $ , 可以計算 $ -\frac{(2^{p} \bmod p^2) - 1}{p} \bmod p $ ，這正是您找到的公式。