Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 0 down vote accepted

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$.

share|cite|improve this answer

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$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.