# Function with a Modular Inverse

For a combinatorics problem I have a function, $h(x)$ that is always divisible by five, but it is calculated in pieces, e.g. $h(1) = 43 + 7$.

The final function that I need is $f(x) = (h(x) / 5) \bmod 1000000007$, where $(h(x) / 5)$ is always integral.

I can calculate $h(x) \bmod 1000000007$. However, I'm unsure if it's possible to obtain $f(x)$ from $h(x) \bmod 1000000007$.

I would appreciate any suggestions.

SOLVED: Wow, thank you. Everything was very helpful, and this solution works.

-

All you need to do is multiply by the multiplicative inverse of $5 \text{ mod } 1000000007$. Since $1000000007$ is prime, Fermat's little theorem says that inverse is $5^{1000000005} \text{ mod } 1000000007$ which Wolfram Alpha calculates as $400000003$. So your answer is $((h(x) \text{ mod } 1000000007)*400000003) \text{ mod } 1000000007$.

-

Hint $\rm\ \ h/5\ mod \ m\ =\ ((1/5\ mod\ m)\ (h\ mod\ m))\ mod\ m.\:$

But computing $\rm\ 1/5\ mod\ m\$ is easy for $\rm\,m = 5n+2$

$$\rm\ mod\ 5n+2\!:\ \ \frac{1}5\,\equiv\, \frac{1+2(5n+2)}5 \,\equiv\, \frac{10n+5}{5}\,\equiv\, 2n+1$$

For $\rm\:m = 10\cdot 10^k\! + 7\, =\, 5\,(2\cdot 10^k\!+1) + 2,\,$ we get $\rm\:1/5\,\equiv\, 2\,(2\cdot 10^k+1) + 1 \,\equiv\, 4\cdot 10^k + 3.$

e.g. $\rm\ \ 1/5\equiv 43\pmod{107},\ \ 1/5\equiv 403\pmod{1007},\ \ 1/5\equiv 4003\pmod{10007},\,\ldots$

-
See also this answer which computes $\rm\: 1/5\ mod\ m\:$ for all $\rm\,m\,$ coprime to $5.\$ –  Bill Dubuque Sep 10 '12 at 14:58