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

-

2
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

## 2 Answers

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
show 3 more comments

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9359458684921265, "perplexity_flag": "head"}