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.

  • $\begingroup$ Please see math.meta.stackexchange.com/questions/5020 $\endgroup$ – Angina Seng Sep 14 '18 at 18:17
  • $\begingroup$ Thank you. Working on it. $\endgroup$ – burfl Sep 14 '18 at 18:20
  • $\begingroup$ @LordSharktheUnknown how's that? $\endgroup$ – burfl Sep 14 '18 at 18:32
  • $\begingroup$ 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? $\endgroup$ – rschwieb Sep 14 '18 at 18:44
  • $\begingroup$ @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. $\endgroup$ – burfl Sep 14 '18 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$.

  • $\begingroup$ So, $ar = 1 - ns$ and therefore $ar$ is equal to $1$ plus some (in this case, negative) multiple of $n$? Am I following you? $\endgroup$ – burfl Sep 14 '18 at 18:40
  • $\begingroup$ In other words, this could be written as $ar = 1 + (-s)n$. $\endgroup$ – burfl Sep 14 '18 at 18:42
  • $\begingroup$ @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. $\endgroup$ – Daniel Mroz Sep 14 '18 at 18:48
  • $\begingroup$ Yes, I see that now. I'm feeling rather silly that this eluded me. But your nudge is greatly appreciated! Thank you. $\endgroup$ – burfl Sep 14 '18 at 18:51

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.