0
$\begingroup$

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.

  • 0
    I meant x or a = ±12012-07-16

2 Answers 2

1

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$.

1

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.