# coprime divisibility: is $ax-1$ divisible by $n$? [duplicate]

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?

## marked as duplicate by Bill Dubuque, N. S. elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 4 at 23:42

• Immediate consequence of the Bezout identity for $\,\gcd(a,n)= 1.\,$ Write it down and isolate the $\,ny\,$ term on one side of the equation and observe what that implies about divisibility by $\,n\ \$ – Bill Dubuque Mar 4 at 22:43
• – Bill Dubuque Mar 4 at 23:23

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