Modular Arithmetic and Congruences

Question

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.

You are running into two distinct uses of "mod". As a relation, it means your first definition. As an operator, $a\bmod n = b$ means the latter. — Arturo Magidin, Mar 01 '12 at 05:49
The video has an equation x ≡ b (mod n) and they say x is a number that when divided by n gives you a remainder of b? Is this wrong? — rubixibuc, Mar 01 '12 at 06:00
If $0\leq b \lt n$, then they are correct; they are not giving you the definition of $a\equiv b\pmod{n}$, they are telling you something else about the numbers in question. — Arturo Magidin, Mar 01 '12 at 16:11

Edison · Accepted Answer · 2012-03-01T06:09:34.147

1

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.

edited Mar 01 '12 at 06:09

answered Mar 01 '12 at 05:47

Edison

3,508

\pmod{n} produces $\pmod{n}$; it's the correct $\LaTeX$ code to use for the parenthetical one; for the binary operator, use \bmod. – Arturo Magidin Mar 01 '12 at 05:53
@ArturoMagidin, I am just learning latex, so thanks for the comment. What is the code for writing latex in the fancy font? – Edison Mar 01 '12 at 05:55
Why do people say a divided by n gives you a remainder of b though? – rubixibuc Mar 01 '12 at 05:58
@rubixibuc in the video, the b value is less than or equal to the n value, this is not the case with your example. – Edison Mar 01 '12 at 06:04
I assumed it was a rule, so it's just an exception in this case? – rubixibuc Mar 01 '12 at 06:05
@rubixibuc, if the b value is not less than the n value, then you can reduce the b value by multiples of n until you have the appropriate value – Edison Mar 01 '12 at 06:07
Thank you, I didn't know that :-) – rubixibuc Mar 01 '12 at 06:09
@Edison: There are several math fonts: caligraphic, with \mathcal: $\mathcal{ABCDEFG}$; script, with \mathscr: $\mathscr{ABCDEFG}$; and others. – Arturo Magidin Mar 01 '12 at 16:10

score 1 · Answer 2 · answered Mar 01 '12 at 06:46

$\rm\: a\equiv b\pmod n\iff n\ |\ a-b \iff a-b\: =\: nk\:$ for some $\rm\:k\in \mathbb Z$.

$\rm\: a\ mod\ n\: =\: b\iff a\equiv b\pmod n\:$ and $\rm\:0\le b < n.\:$ Therefore $\rm\:a\ mod\ n\:$ is the remainder upon dividing $\rm\:a\:$ by $\rm\:m,\:$ i.e. the least positive element of the equivalence class $\rm\:a + n\:\mathbb Z\:$ of all integers congruent to $\rm\:a,\:$ modulo $\rm\:n,\:$ i.e. the unique element equivalent to $\rm\:a\:$ from the complete system of representatives $\rm\:\{0,1,2,\ldots,n-1\}$ of congruence classes modulo $\rm\:n.\:$ This is the use in the video.

Modular Arithmetic and Congruences

2 Answers2