1

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.

ASB
  • 3,999
Michael Harvey
  • 13
  • 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$. – abiessu Mar 15 '15 at 05:56
  • Thanks @abiessu I will try to grasp this – Michael Harvey Mar 15 '15 at 06:12

2 Answers2

3

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.

William Stagner
  • 4,786
0

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

abiessu
  • 8,115