0
$\begingroup$

Suppose that $a$ and $n$ are integers, $n>1$. Prove that the equation $ax\equiv1(\mod n)$ has a solution if and only if $a$ and $n$ are relatively prime. How to solving this problem?

$\endgroup$
  • $\begingroup$ sorry. I made a mistake. $\endgroup$ – K.C.S. Apr 9 '14 at 7:36
  • 1
    $\begingroup$ Have you any thoughts of your own on this? $\endgroup$ – Mark Bennet Apr 9 '14 at 7:39
1
$\begingroup$

Suppose $ax \equiv 1(\mod n)$, then $ax - 1 = bn$ for some $b \in \mathbb{Z}$. So $1 = ax - bn$. So if $gcd(a,n) > 1$, then $gcd(a,n) | ax$, and $gcd(a,n) | bn$. So $gcd(a,n) | ax - bn = 1$, a contradiction. So $gcd(a,n) = 1$. Conversely, if $gcd(a,n) = 1$, then there are $x, b \in \mathbb{Z}$ such that $ax + bn = 1$. This means $ax \equiv 1(\mod n)$.

$\endgroup$
0
$\begingroup$

So $n \cdot y = a \cdot x - 1$ for some $y$. Rearrange this equation into the definition of $(a,n)=1$.

$\endgroup$
0
$\begingroup$

Consider the set of numbers $pa+qn$. If $M,N$ are numbers of this form so are the numbers $cM+dN$.

Now suppose $d$ is the least positive integer expressible in this form, and that $e$ is any positive integer represented in this way. Then $e=sd+r$ with $0\le r \lt d$ and $r=e-sd$ is represented. Since $d$ was the least positive integer and $r\lt d$ we must have $f=0$ and $e=sd$.

Hence any representable positive integer is divisible by $d$. So $a=1\cdot a+0 \cdot n$ is divisible by $d$ and so is $n$. Since $a$ and $n$ are relatively prime, and both are multiples of $d$, we must have $d=1$.

Now if $pa+qn=1$ we have $pa\equiv 1$ mod $n$.

Note this also can be used to show that the hcf $(a,n)=d$ can be represented in the form $pa+qn=d$ in the case that $a$ and $n$ are not relatively prime.

$\endgroup$
0
$\begingroup$

$\exists x\in\Bbb Z\!:\ ax\equiv c\pmod n\!\iff\! \exists x,y\in\Bbb Z\!:\ ax+ny = c\!\overset{\rm\ Bezout}\iff\!\gcd(a,n)\mid c.\ $ Let $\ c = 1.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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