1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$

$\endgroup$
7
  • $\begingroup$ See also this answer which computes $\rm\: 1/5\ mod\ m\:$ for all $\rm\,m\,$ coprime to $5.\ $ $\endgroup$ Sep 10, 2012 at 14:58
  • $\begingroup$ math.stackexchange.com/questions/25390/… $\endgroup$
    – Max
    Mar 8, 2019 at 21:28
  • $\begingroup$ @Max The point is to give a closed form so we don't need to resort to general algorithms. $\endgroup$ Mar 8, 2019 at 21:46
  • $\begingroup$ 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$ $\endgroup$
    – Max
    Mar 8, 2019 at 22:36
  • $\begingroup$ @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. $\endgroup$ Mar 9, 2019 at 0:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .