Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.