Solve for $c$ in an equation involving modulo operation (remainder after division) I have reduced a part of a programming task to this equation:
$(c*a+1)\%b=1$ where $c\geq 1,0\leq a<b$
For a given $a$ and $b$ I want to find the smallest value of $c$ such that the equation is satisfied.
Right now what I have implemented is:
c=1  
i=a+1;
while(i!=1)
{
   i+=a;
   if(i>b)i-=b;
   ++c;
} 

This is an O(n) implementation and is not very efficient. I was looking for a O(1) implementation i.e. if there is any way we can directly find such $c$ without a loop?
 A: Your programming equation $(c*a+1)\%b=1$ would normally be written by mathematicians like
$$ca+1 \equiv 1 \pmod b$$
That simplifies to
$$ca \equiv 0 \pmod b$$
which we can easily prove:
$ca+1 \equiv 1 \pmod b \implies ca+1 = kb + 1$ for some integer $k$.
So $ca = kb$
To find $c$, let $a=gA, b=gB$, where $g$ is the greatest common divisor of $a$ & $b$, $g = \gcd(a, b)$.
Then $cgA = kgB \implies cA = kB$. 
Now $B$ doesn't divide $A$ so it must divide $c$, so the smallest (positive) value for $c$ is $B$ (and hence $k = A$). The proof of that is known as Euclid's lemma.
In other words $c = b / \gcd(a, b)$
Note that $ac = AgB = A(gB) = Ab$, so it's a multiple of both $a$ and $b$.

So how do we find $\gcd(a, b)$?
The usual method is to use Euclid's algorithm which utilizes the fact that for $a < b$,
$$\gcd(a, b) = \gcd(b\mod a, a)$$
Here's an implementation in Python. 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

That function assumes that $a >=b$; it still works if $a<b$, but it takes one extra loop, or you can do a compare and swap before the loop, if you like.
