# Modular Arithmetic and Congruences

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 1 '12 at 5: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 1 '12 at 6: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 1 '12 at 16:11

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.

• \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 1 '12 at 5: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 1 '12 at 5:55
• Why do people say a divided by n gives you a remainder of b though? – rubixibuc Mar 1 '12 at 5: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 1 '12 at 6:04
• I assumed it was a rule, so it's just an exception in this case? – rubixibuc Mar 1 '12 at 6:05

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