Q: simple modular arithmetic 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.
 A: 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.
A: 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}$$

