1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
4
  • $\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, 2018 at 18:40
  • $\begingroup$ In other words, this could be written as $ar = 1 + (-s)n$. $\endgroup$
    – burfl
    Sep 14, 2018 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, 2018 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, 2018 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .