Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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

 
discard

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.