Wednesday, 27 May 2015

abstract algebra - Why does it follow from ns=1ar that arequiv1modn?



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 Zn 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}...