Why do the modular multiplicative inverse of an integer $a$ always exists when it is coprime with the modulus? In other words how can we say that for coprime numbers $a$ and $m$, the Diophantine equation $ax-my=1$ is always solvable? 
I would like to have some intuitive understanding too in addition to proof. Eg- if $a$ is one of the factors of $m$ then we are sure that the solution doesn't exists because for some $x=t$, $at$ becomes equal to $m$. So, it always lie in the residual class in which 0 is contained and hence can never belong to the one in which 1 is contained.
 A: Let phi be Euler's totient function. Since gcd(a, m)=1, we can use (Z/mZ)* to help us answer your question. If we move things around, ax-1 has to be divisible by m (since ax-1=my). Letting x=a^(phi(m)-1), we get a^(phi(m))-1=m*y. Both sides are divisible by m. (a^(phi(m))-1)/m is also an integer. So far, at least one solution to the Diophante equation exists; (x, y)=(a^(phi(m)-1), (a^(phi(m))-1)/m). 
Lets prove now there are infinitely many solutions. To do this, a change of variables for simplification is much nicer; p=a and q=m. since gcd(p, q)=1, p= p'+nq, where p' is p reduced mod q. We have 
(p'+nq)x-qy=1
(p')x+q(nx-y)=1.
Substitute x-> x'+(p')^(-1) 
[(p')^(-1) is the inverse of (p') in (Z/qZ); (p')(p')^(-1)=kq+1]
(p')x'+kq+1+q(nx'+n(p')^(-1)-y)=1
(p')x'+q(nx'+n(p')^(-1)+k-y)=0
Substitute y->y'+k+n(p')^(-1)
(p')x'+q(nx'-y')=0
(p'+qn)x'=q*y'
Aka
px'=qy'
Since we have gcd(p, q)=1, the ordered pair solution (x', y') must be (zq, zp), for integers z. Working our way back to find the original x and y solution, we get 
x=zq-(p')^(-1), 
y=zp-((p')*(p')^(-1)-1)/q-n(p')^(-1)
So it happens that there is not only one but infinitely many solutions!
