Wednesday 27 May 2015

abstract algebra - 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.


Answer




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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...