0
$\begingroup$

This question already has an answer here:

Suppose that $a,n \in \Bbb Z$ are coprime. Show that there is an integer $x$ such that $ax−1$ is divisible by $n$.

I know that $\gcd(a,n)=1$ and feel like that will be used in the proof of this, but the fact that there are no numbers is making it complicated. Do I have to work out the gcd backwards?

$\endgroup$

marked as duplicate by Bill Dubuque, N. S. elementary-number-theory Mar 4 at 23:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Let $I=a\mathbb{Z}+n\mathbb{Z}$ be an ideal in $\mathbb{Z}$. Now, $\mathbb{Z}$ is a PID; i.e., we have $I=d\mathbb{Z}$ for some $d$. But since $a,n\in I$, we have that $a,n\in d\mathbb{Z}$; i.e., $d$ divides both $a$ and $n$. But $gcd(a,n)=1$, so $d=\pm 1$. This proves that $I=\mathbb{Z}$; in particular, $1\in I$, so $1=ax+ny$ for some $x,y\in\mathbb{Z}$. This is what you wanted to prove.

$\endgroup$
0
$\begingroup$

$\gcd(a, n) = 1 \Longrightarrow \exists x, y \in \Bbb Z, \; ax + ny = 1; \tag 1$

$ax + ny = 1 \Longrightarrow ax - 1 = -ny \Longrightarrow n \mid ax - 1. \tag 2$

$\endgroup$
  • $\begingroup$ thank you! that has really helped $\endgroup$ – harriet Mar 4 at 22:57
  • $\begingroup$ @harriet: glad to be of service. And thanks for the "acceptance"! Cheers! $\endgroup$ – Robert Lewis Mar 4 at 23:18

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