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


$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
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Mar 1 '12 at 5:49
  • $\begingroup$ 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? $\endgroup$ – rubixibuc Mar 1 '12 at 6:00
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ \pmod{n} produces $\pmod{n}$; it's the correct $\LaTeX$ code to use for the parenthetical one; for the binary operator, use \bmod. $\endgroup$ – Arturo Magidin Mar 1 '12 at 5:53
  • $\begingroup$ @ArturoMagidin, I am just learning latex, so thanks for the comment. What is the code for writing latex in the fancy font? $\endgroup$ – Edison Mar 1 '12 at 5:55
  • $\begingroup$ Why do people say a divided by n gives you a remainder of b though? $\endgroup$ – rubixibuc Mar 1 '12 at 5:58
  • $\begingroup$ @rubixibuc in the video, the b value is less than or equal to the n value, this is not the case with your example. $\endgroup$ – Edison Mar 1 '12 at 6:04
  • $\begingroup$ I assumed it was a rule, so it's just an exception in this case? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.