How to caculate the summation of successive modular inverses? $p$ is a big prime. $p&gt;2^{2048}$.
So how to caculate the summation of successive modular inverses over $p$?
$$
\sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p
$$
As to $p$ is a big prime, it's impossible to caculate the modular inverses one by one and sum them at last.
I found someone give a formula which approximates the result, but I couldn't prove it.
$$
p - \frac{2^{p}\pmod {p^2}-1}{p} \pmod p
$$
Can you help me prove the formula, or give your answers to calculate the summation? Thanks sincerely!
The sum you are inquiring about is pretty much the right side of the Fermat quotient identity discovered by Eisenstein (proof here):
$$
-2q_p(2) = \sum_{i=1}^{(p-1)/2} 1/i \pmod{p}\,,
$$
where $q_p(a) = \frac{a^{p-1} - 1}{p}$.
Thus the sum can be computed as $-2 \frac{2^{p-1} - 1}{p} \bmod p$. Because computing $2^{p-1}$ is not feasible for very large $p$, and because one only requires the result divided by $p$ and then reduced again by $p$, computing $\frac{2^{p-1} - 1}{p}$ can be performed as $\frac{(2^{p-1} \bmod p^2) - 1}{p}$ without any precision loss. And to absorb that factor of $2$, one can compute instead $-\frac{(2^{p} \bmod p^2) - 1}{p} \bmod p$, which is exactly the formula you found.