# Prove or Disprove $xa \equiv 1 \pmod{ n}$

If $a\in\mathbb{Z}, n\in\mathbb{N}$, then the equation $xa\equiv1\pmod {n}$ has a solution for some $x\in\mathbb{Z}$.

I'm not quite sure where to start. I know that $n|(xa-1)$, so $ns=xa-1$ for some integer $s$.

Should I start plugging in numbers to find one that makes it possible for a to divide $(ns+1)$?

$(xa-1)\equiv0 \pmod {n}$, so this means that $xa=\pm 1$?

I feel so dumb when it comes to proofs, so please go easy on me.

Thank you.

-
I think you need a little more. $2x\equiv 1 (\mod 4)$ has no solutions. Throw in a coprime somewhere. – Robert Mastragostino Jul 16 '12 at 19:08
Edited the math . I think you should rewrite it again in good terms. If $n|(xa-1) \implies ns=xa-1$ for some $s$. – Iyengar Jul 16 '12 at 19:15
You wrote $x,a= \pm 1$ is it $(x,a)=\pm 1$ or $xa= \pm 1$ ? – Iyengar Jul 16 '12 at 19:20
I meant x or a = ±1 – laser295 Jul 16 '12 at 21:29

If your question means $\forall a\in\mathbb Z.\forall n\in\mathbb N.\exists x\in\mathbb Z.xa\equiv 1\pmod n$, then we have many counter-examples, e.g. $a = 4$, $n = 6$, then $4x \equiv 0, 2 \text{ or } 4 \pmod 6$ for any $x$.
Hint  If so, then for $\rm\,a=2=n\:$ we have $\rm\:2x\equiv 1\pmod{2},\:$ i.e. $\rm\:2x\:$ is even and odd, contradiction.
Generally $\rm\:a\,x\equiv b\pmod n\:$ is solvable iff $\rm\:gcd(a,n)\:|\:b,\:$ see Bezout's identity.