I understand that $a \equiv b \pmod n$ means when you divide each $a$ and $b$ by $n$ you get the same remainder. But why do people say: "$a$ divided by $n$ gives you remainder $b$"?
They say that in the first 30 seconds of this video lecture http://www.youtube.com/watch?v=QXIlkq06Ct0&feature=youtube_gdata_player
Example
$12 \equiv 17 \pmod 5$
$12$ divided $5$ has remainder of $2$
17 divided by 5 has remainder of 2
Neither has the latter relation, so why do people sometimes say this.
Answer
12 is the same as 2 $\bmod{5}$ and
17 is the same as 2 $\bmod{5}$
Lets say you have $a\equiv b\bmod{n}$. Then the numbers you are working with are basically from the set {0,1,2,3,...,n-1}, the number n=0 (mod n), n+1=1 (mod n), n+2=2 (mod n), ect.
If two numbers, a and b are related by $a\equiv b\bmod{n}$, then (a-b)=nc,for $c\in \mathbb{N}$, that is (a-b) is a multiple of n. So in your case above, $2\equiv2+5\equiv2+10\equiv2+15\equiv ect.\bmod{5}$. So 2 is the same as 12 which is the same as 15 $\bmod{5}$
When you have $a\equiv b \bmod{n}$, with $a>b$ and $b\in\{0,1,\cdots ,n-1 \}$, then in fact a divided by n is b, this is the case in the video. When this is not the case, it causes for confusion, as in your example. It would make sense to write $17\equiv 2 \bmod{5}$ however.
No comments:
Post a Comment