1
$\begingroup$

I am trying to solve a programming problem but am stuck on some modular algebra. The equation I am trying to solve boils down to $$a \equiv (b + cx)\pmod {10^9+7}$$ where I know a, b, and c and need to solve for x. Is there a way to do this? Sorry if this is a bad question, math has become a little foreign to me. Thanks in advance.

$\endgroup$
  • $\begingroup$ This resolves to $x\equiv c^{-1}(a-b)\pmod{10^9+7}$. The $c^{-1}$ is probably the trickiest part, i.e., finding the integer that when multiplied by $c$ produces $1$ modulo $10^9+7$. $\endgroup$ – abiessu Mar 15 '15 at 5:56
  • $\begingroup$ Thanks @abiessu I will try to grasp this $\endgroup$ – Michael Harvey Mar 15 '15 at 6:12
3
$\begingroup$

I'm assuming $(c,10^9 + 7) = 1$, so you can ensure a solution exists. Since $10^9 + 7$ is prime, Fermat's little theorem gives $$c^{-1} \equiv c^{10^9 + 5} \pmod{10^9 + 7},$$ so a solution can be given by $$ x = c^{10^9 + 5}(a-b), $$ but this isn't easily computable.

$\endgroup$
  • $\begingroup$ With a computer program? Sure it is. $\endgroup$ – Mike Mar 15 '15 at 6:07
  • $\begingroup$ Yikes I must be taking the wrong approach then. Thanks for your help. $\endgroup$ – Michael Harvey Mar 15 '15 at 6:13
0
$\begingroup$

Taking one step back from my comment, we have $cx\equiv a-b\pmod{10^9+7}$, which by the definition of modular equivalence, means that there exists $y$ such that

$$cx+(10^9+7)y=a-b\tag 1$$

In terms of computation, the extended Euclidean Algorithm is probably the fastest and cleanest method to find solutions $(x,y)$, assuming they exist. In order for such solutions to exist in $(1)$, the only requirement we have is that GCD$(c,10^9+7)$ divides $a-b$. Using the algorithm described on the Wikipedia page, we might start with some recurrence like this:

$r_0 = 10^9+7,\\ r_1 = c\\ s_0 = 1,\ t_0 = 0,\ s_1 = 0,\ t_1 = 1\\ q_n=\text{floor}(r_{n-1}/r_n)\\ r_{n+1} = r_{n-1} - q_n\cdot r_n\\ s_{n+1} = s_{n-1} - q_n\cdot s_n\\ t_{n+1} = t_{n-1} - q_n\cdot t_n$

The process of finding $q_n,r_{n+1},s_{n+1},t_{n+1}$ should be repeated until one of the following happens:

  • $r_{n+1} = 0$
  • $r_{n+1}$ divides $a-b$

If we reach the point where $r_{n+1} = 0$, it can be assumed that $r_n$ does not divide $a-b$ since we would have stopped at that point. Assuming that we got $r_{n+1}\mid a-b$, we must then have a solution; one solution will be

$$r_{n+1}=(10^9+7)s_{n+1}+ct_{n+1}$$ $$a-b=(10^9+7)\frac{a-b}{r_{n+1}}s_{n+1}+c\frac{a-b}{r_{n+1}}t_{n+1}$$

$$x=\frac{a-b}{r_{n+1}}t_{n+1}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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