# Why does it follow from $ns = 1 - ar$ that $ar \equiv 1 \mod n$?

I'm reading through Prof. Tom Judson's online textbook "Abstract Algebra: Theory and Applications". Proposition 3.4 (under the heading The Integers mod n) states:

"Let $\Bbb Z_n$ be the set of equivalence classes of the integers $\mod n$ and $a,b,c∈\Bbb Z_n$."

and, under (6):

"Let $a$ be a nonzero integer. Then $\gcd(a,n)=1$ if and only if there exists a multiplicative inverse $b$ for $a \mod n$; that is, a nonzero integer $b$ such that $ab \equiv 1 \mod n$."

The first part of the proof for this states:

"Suppose that $\gcd(a,n)=1$. Then there exist integers $r$ and $s$ such that $ar+ns=1$. Since $ns=1−ar$, it must be the case that $ar≡1 \mod n$. Letting $b$ be the equivalence class of $r$, $ab \equiv 1 \mod n$."

I'm following everything just fine except for this one sentence from the preceding paragraph:

"Since $ns=1-ar$, it must be the case that $ar \equiv 1 \mod n$."

As in the title to this question, why does it follow from $ns = 1 - ar$ that $ar \equiv 1 \mod n$? It's obvious to me that $ns = 1 - ar$, but not that this implies $ar \equiv 1 \mod n$. The entire rest of the proof (including the second part not copied here) makes perfect sense to me. Just that one sentence eludes me.

What am I missing?

Thank you in advance for you help.

• Sep 14, 2018 at 18:17
• Thank you. Working on it. Sep 14, 2018 at 18:20
• @LordSharktheUnknown how's that? Sep 14, 2018 at 18:32
• For a lot of people, that is the definition of what it means for two things to be equal in modular arithmetic. What definition are you using, then? Sep 14, 2018 at 18:44
• @rschwieb IIRC, the definition presented in the book was that if $a \equiv b \mod n$ then $a-b=kn$ for some integer $k$. I see now that these are equivalent. I think the order in which the author wrote the terms may have confused me. I haven't been in a math lecture in about a decade and a half. I recently brushed up on some topics I hadn't touched in years (like linear algebra) and decided it might be fun to go further than I did in school. Challenging so far. Sep 14, 2018 at 18:48

We say that $a \equiv b \text{ mod } n$ if we can write $a = b + kn$ for some integer $k$.
In your example, we have $1 = ar + ns$.
• So, $ar = 1 - ns$ and therefore $ar$ is equal to $1$ plus some (in this case, negative) multiple of $n$? Am I following you? Sep 14, 2018 at 18:40
• In other words, this could be written as $ar = 1 + (-s)n$. Sep 14, 2018 at 18:42
• @burfl Yes, that's also correct. I see that in your source $a \equiv m \text{ mod } n$ is defined as $n|(a-b)$. This is in fact equivalent to the definition I gave. Sep 14, 2018 at 18:48