Find inverse of $a \mod p$

Question

If we want to find the inverse of $a$ mod $p$, $p$ not prime, then we can write $$ax \equiv 1 \mod p$$ $$ax+py\equiv 1 \mod p$$ and use the extended euclidean algorithm to solve for $x$, which is the inverse mod $p$

My Question How do we find $x$ if $\gcd(a,p)\neq 1$

Answer 1

We are in the situation where $a$ and $p$ are both multiples of some $d>1$.

Two numbers which are multiples of same $d$ (by positive or negative integers it is immaterial) will differ by at least $d$.

Getting an inverse for $a$ mod $p$ means finding $x,y $ such that $ax - (-yp)=1$. As both $ax$ and $-yp$ are multiples of $d$ the difference of $1$ is not possible to achieve (as $d>1$ by hypothesis). Hence inverse does not exist.

Answer 2

$ax+py=1$ must be true for some integer $y$... but this means $\gcd (a,p)=1$