1

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.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
fahrbach
  • 1,783
  • 1
  • 13
  • 15

1 Answers1

2

Hint $\rm\ \ h/5\ mod \ m\ =\ ((\color{#0a0}{1/5\ mod\ m})\ (h\ mod\ m))\ mod\ m$

Computing $\rm\ \color{#0a0}{1/5\ mod\ m},\, $ for $\, m = 5n\!+\!2\,$ is easy mentally, e.g. by Inverse Reciprocity we find

$$\!\bmod m\!:\ \ \dfrac{1}5 \equiv \dfrac{1+m\overbrace{\left[\dfrac{-1}{m}\bmod 5\right]}^{\large -1/2\ \equiv\ 4/2\ \equiv\ \color{#c00}2}}{5^{\phantom 1}}\!\equiv\dfrac{\overbrace{1+m\,[\color{#c00}2]}^{\large 10n+5}}{5}\equiv 2n\!+\!1\qquad\qquad $$

So $\rm\:m = 10\cdot 10^k\! + 7\, =\, 5\,(\overbrace{2\cdot 10^k\!+1}^{\Large n}) + 2\,$ $\rm\,\Rightarrow\, 1/5\,\equiv\, 2\,(\overbrace{2\cdot 10^k+1}^{\Large n}) + 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$

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • See also [this answer](http://math.stackexchange.com/a/191201/242) which computes $\rm\: 1/5\ mod\ m\:$ for all $\rm\,m\,$ coprime to $5.\ $ – Bill Dubuque Sep 10 '12 at 14:58
  • https://math.stackexchange.com/questions/25390/how-to-find-the-inverse-modulo-m – Max Mar 08 '19 at 21:28
  • @Max The point is to give a *closed form* so we don't need to resort to general algorithms. – Bill Dubuque Mar 08 '19 at 21:46
  • The point is that the general algorithm gives closed form answer in direct way with no ingenuity required: $1000000007=5\times 200000001+2$ and $5=2\times 2 +1$, so $5= 2 (1000000007-5\times 200000001)+1$ and $1=5(200000001\times2+1) \mod 1000000007$, i.e. $1=5\times 400000003 \mod 1000000007$ – Max Mar 08 '19 at 22:36
  • @Max But no ingenuity is required above. I computed the inverse using *inverse reciprocity* (a special case of extended euclidean algorithm inversion that is convenient for simple inversions). I added that omitted step above. Note: a link lacking any explanation what purpose it serves may prove perplexing. Even I was not sure precisely what the link was intended to mean (and I know these topics like the back of my hand. – Bill Dubuque Mar 09 '19 at 00:18
  • I'm glad you've edited your answer clarifying this, and added a link to a general discussion. It seems that this type of question comes up fairly often, and it seems to me it would be a good thing if every time it comes up there was a clear link to both the extended Euclidean algorithm and Gauss algorithm (which I now see is quite neat indeed), perhaps after the specific example is handled. Perhaps there was such a link before and I missed it, but now it is more clear. – Max Mar 09 '19 at 08:00
  • @Max Almost always I do provide such links (above was an oversight). When critiques on such occur, usually they are about too *many* links, not too *few* (e.g. one reader expressed frustration after getting lost in a complex link graph!). – Bill Dubuque Mar 09 '19 at 14:52