1

If the notation $$a \equiv b \pmod{n}$$ means (a%n) = b, then why don't we just use $(a\%b) = b$ as the notation instead of using $a \equiv b \pmod{n}$ ?

hmakholm left over Monica
  • 286,031
Utkal Sinha
  • 167
  • 1
    It doesn't mean "$(a% n)=b$". – Angina Seng May 19 '17 at 17:13
  • Does $a%n=b$ mean that $b$ is the remainder of the division of $a$ by $n$? This would be wrong. – Wuestenfux May 19 '17 at 17:16
  • Thanks for posting. I was expecting this reply because as of now this is so confusing to me. Some online videos say that this is $a %n=b$ whereas some other texts say it is not. Though I am not yet getting any simple text explaining the real meaning of it and why do we call this as "equivalence" rather than equal. – Utkal Sinha May 19 '17 at 17:17
  • While $17\neq 26$, nevertheless $17 \equiv 26 \bmod 3$. – hardmath May 19 '17 at 17:21

4 Answers4

2

Actually meaning of the equation is when you will divide 'a' by n and if reminder is what exactly if you divide 'b' by n then these two numbers are equivalent.

Rodriguez J.
  • 79
  • That's not necessarily true for negative $a$ and $b$, at least if "remainder" means what most people seem to take it to mean. – hmakholm left over Monica May 19 '17 at 17:24
  • 1
    @HenningMakholm In number theory the remainder is taken to be between $0$ and the divisor, in which case this answer is correct. – kccu May 19 '17 at 17:33
1

$a \%n = b$ means that $b$ is the remainder of the division of $a$ by $n$ (at least when $a,b,n$ are positive). But $a=b \pmod n$ does not mean that.

Rather, $a=b \pmod n$ means $a$ and $b$ have the same remainder upon division by $n$. For instance, $-1 = 15 \pmod 7$, but $15$ is certainly not the remainder of $-1$ on division by $7$. The notation $a \equiv_n b$ might make it more clear that this is an equivalence relation, not an operator mapping $(a,n)$ to $b$.

kccu
  • 20,808
  • 1
  • 22
  • 41
1

The definition of $$a\equiv b \pmod n$$ you will find in most textbooks is $$ n \mid (a-b) $$ that is, $a-b$ is an integer multiple of $n$.

If you have a well-behaved binary modulus operation this is equivalent to $$ (a\bmod n) = (b\bmod n) $$ but this does not work really well as a definition, because the usual way to define the binary $\bmod$ is

$x\bmod n$ means the number $y$ with $0\le y< n$ such that $x\equiv y\pmod n$.

so everything would be circular.

Note that this is not the same as $$ a\mathbin{\%}n = b $$ and also not the same as $$ a\mathbin{\%}n = b\mathbin{\%}n $$ if $\%$ is taken to be a remainder operator that works like % does in many programming languages -- because the way % works on negative arguments leads to wrong results; for example, such a definition would fail to make $(-4)\equiv 6\pmod{10}$ true.

One reason why that $\equiv$ notation is particularly useful is that it makes it easy to write an entire chain of congruences, such as: $$ (a+kp)^2 \equiv a^2+(kp)^2+2akp \equiv a^2+p(k^2p+2a) \equiv a^2 \pmod p $$ Note that the $\pmod p$ morally applies to each of the $\equiv$ signs. It is not something that modifies the thing on the right of $\equiv$.

hmakholm left over Monica
  • 286,031
1

I'd define $a\equiv b\;{mod}\; n$ as $n$ divides $a-b$. Then its easy to show that this relation is an equivalence/congruence relation on the ring of integers.

Wuestenfux
  • 20,964