How to implement modular division? I want to calculate do calculate $\frac{a}{b} \pmod{P}$ where $a$ is an integer less $P$ and $P$ is a large prime, $b=5$, a fixed integer.
How can I implement it? Any algorithm which will work well?
 A: First calculate an inverse $k$ of $5$ modulo $p$, and store it as a constant. 
We want  $k$ such that $5k\equiv 1\pmod{p}$. So just look at $p+1$, $2p+1$, $3p+1$, $4p+1$. One of them will be a multiple of $5$, if $p\gt 5$.  Divide by $5$ to get $k$.
Now given any $a$, calculate $ka\bmod{p}$. 
Remark: The procedure took advantage of the smallness of the constant $5$. The way we produced $k$ would be quite unsuitable for large $b$. Then we would want to use the Extended Euclidean Algorithm to find $k$.
A: Hint $\ $ Below are closed forms for $\rm\:1/5\pmod m\,$ computed by Inverse Reciprocity, e.g. as here.
$\rm(1)\ \ \ \  mod\,\ 5k\pm1\!:\ \ 5 k\,\equiv\, \mp1\:\Rightarrow\: 1/5\, \equiv\, \mp k, $ 
$\rm\qquad\ \,e.g.\ \ mod\ 501 = 5\cdot\color{#C00}{100}\color{#0A0}{+1}\!:\,\ 1/5\, \equiv\, \color{#0A0}{-}\color{#C00}{100}$
$\rm\qquad\ \,e.g.\ \ mod\ 499 = 5\cdot\color{#C00}{100}\color{#0A0}{-1}\!:\,\ 1/5\, \equiv\, \color{#0A0}{+}\color{#C00}{100}$
$\rm(2)\ \ \ \  mod\,\ 5k\pm 2\!:\ \  5(1\!\pm\!2k)\, =\,  2(2\pm5k)+1\, \equiv\, 1\:\Rightarrow\:1/5\, \equiv\, 1\pm2k$ 
$\rm\qquad\ \,e.g.\ \ mod\ 502=5\cdot\color{#C00}{100}\color{#0A0}{+2}\!:\,\ 1/5\,\equiv\, 1 \color{#0A0}{+ 2}\cdot\color{#C00}{100}\,\equiv\ 201 $
$\rm\qquad\ \,e.g.\ \ mod\ 498=5\cdot\color{#C00}{100}\color{#0A0}{-2}\!:\,\ 1/5\,\equiv\, 1 \color{#0A0}{- 2}\cdot\color{#C00}{100}\,\equiv -199 $
A: I only know of the Euclidean algorithm. I think it works well.
A: If $a$ were divisible by $5$, we could just do ordinary exact integer divison.
All of $a, a+p, a+2p, a+3p, a+4p$ have the same value modulo $p$. As one of them is guaranteed to be divisible by $5$, we can pick that one and divide it by $5$.
For added optimization, divide $a$ by $5$ with remainder, to obtain $a = 5q + r$. Now, if I haven't made an off by one error, you can compute:
$$ \frac{a}{5} \equiv q + \left\lceil \frac{rp}{5} \right\rceil \pmod p $$
You can, of course, store a lookup table of the four non-zero values of the second term.
