3

question $\frac{a}{b}$=Q (remainder) R why is A mod B = R

i just dont understand how modulo arithmetic work in general after researching about it.

It seems as if the function (mod) only spits out the remainder but when i looked at $x^5 = 11 \mod (35)$

as taken by fleablood (a user) " $x^5 \equiv 11 \mod 35$ means

$x^5 \equiv 11 \equiv 1 \mod 5$ and $x^5 \equiv 11 \equiv 4 \mod 7$

$0^5, 1^5, 2^5, 3^5, 4^5 \equiv 0^5, 1^5, 2^5, -2^5, -1^5 \mod 5 \equiv 0, 1, 32, -32, -1 \equiv 0, 1, 2, 3, 4 \mod 5$.

So $x \equiv 1 \mod 5$.

$0^5, 1^5, 2^5, 3^5, 4^5, 6^5, 6^7 \mod 7 \equiv 0^5, 1^5, 2^5, 3^5, -3^5, -2^5, -1^7 \mod 7 \equiv 0,1,4, 9*9*3, -9*9*3, -4, -1 \equiv 0, 1, 4, 2*2*3, -2*2*3, -4,-1 \equiv 0,1,4, 12, -12, -4, -1 \mod 7 \equiv 0,1,4,5,2,3,6 \mod 7$.

So $x \equiv 1 \mod 5$ and $x \equiv 2 \mod 7$. So $x \in \{1,6,11,16,21,26,31\} \cap \{2, 9, 16, 23, 30\} = \{16\}$. So $x \equiv 16 \mod 35$.

And indeed $16^5 = 2^{20} = 32^4 = (35 - 3)^4 = 35^4 -4*3*35^3 + 6*3^2*35^2 - 4*3^3*35 + 3^4 = 35*[35^3 - 4*3*35^2 + 6*3^2*35 - 4*3^3] + 81 = 35\{[35^3 - 4*3*35^2 + 6*3^2*35 - 4*3^3] + 2\} + 11 \equiv 11 \mod 35$."

But I dont understand his explanation nor do i understand what $\equiv$ symbol represents

rschwieb
  • 153,510
John Rawls
  • 2,685
  • You should write it $%$ it is the remainder of the Euclidean division $a \ %\ b = a -b \lfloor a/b \rfloor$. Note that in many programming languages $/$ is the integer division operator so that $a = bq+r$ with $q =a\ /\ b$ and $r= a \ % \ b$ – reuns Nov 24 '16 at 17:54

3 Answers3

5

"modulo" or "mod" is a binary operator.

In general, $a$ mod $b$ gives the remainder $r$ obtained on dividing $a$ by $b$, that is,

$a=b \times c + r$ implies $a$ mod $b$ = $r$, where $a,c \in \mathbb{Z}$, $b\in \mathbb{Z^+}, r\in \mathbb{W}$ with $0≤r<b$.

When $a$ and $b$ leave the same remainder on dividing by $c$, we say that $a$ and $b$ are equivalent or congruent in the world or more appropriately the system of $c$, that is,

$a \equiv b \pmod c$ iff $a$ mod $c=b$ mod $c$, where $a, b\in\mathbb{Z}$ and $c\in\mathbb{Z^+}$.

MrAP
  • 3,003
  • 1
    Please note that (for $b > 0$, say) $a = b c + r$ *and $0 \le r < b$* implies $a\ \text{mod}\ b = r$. – Andreas Caranti Jan 08 '17 at 09:18
  • 2
    This is an unusually concise (and correct!) answer, showing the distinction between the binary operator “mod” and the equivalence relation “blah$\equiv$wudge $\pmod m$”. My strong impression is that the latter was originally meant as “blah is equivalent to wudge with respect to the modulus (i.e. block) $m$”. – Lubin Jan 09 '17 at 00:28
  • Your statement "$a$= $b$ * $c$ + $r$(where b ≠ 0 and r ≥ 0) implies $a$ mod $b$ = $r$" is still incorrect as it stands. – Andreas Caranti Jan 09 '17 at 07:21
  • @AndreasCaranti why? – MrAP Jan 09 '17 at 07:30
  • You try and say it in other parts of you answer, but the correct statement is "for $b \ne 0$, if $a = b q + r$ and $0 \le r < \lvert b \rvert$, then $r = a \bmod b$". It might seem finicky, but a mathematical statement should be complete in itself. If you just say "$a$= $b$ * $c$ + $r$(where b ≠ 0 and r ≥ 0) implies $a$ mod $b$ = $r$", then it is not true, consider $a = 12$, $b = 5$, and $12 = 5 \cdot 1 + 7$, $12 = 5 \cdot 2 + 2$. – Andreas Caranti Jan 09 '17 at 08:11
  • @AndreasCaranti, i was wrong in saying that. I have edited and corrected my answer. – MrAP Jan 11 '17 at 03:26
0

For non-zero integer $c,$ and integers $a,a',b,b':$

$a\equiv b \pmod c$ means there exist integer $x$ with $a=b+xc.$ Equivalently, that $(a-b)/c\in \mathbb Z.$ From this we have

(i). $a\equiv a \pmod c .$

(ii). $a \equiv b \pmod c \iff b\equiv a \pmod c.$

(iii). $(a\equiv b \pmod c \land a\equiv b' \pmod c)\iff (b\equiv b' \pmod c).$

(iv). $(a\equiv b \pmod c \land a'\equiv b' \pmod c)\implies (a+a'\equiv b+b' \pmod c).$

(v). $(a\equiv b \pmod c \land a'\equiv b'\pmod c)\implies (aa'\equiv bb' \pmod c).$

These are confirmed directly from the def'n. For example for (v) let $a=a'+xc $ and $b=b'+yc$ with integers $x,y.$ Then $ab=a'b'+zc,$ where $z=a'y+b'x+xyc$ is an integer.

DanielWainfleet
  • 57,985
-1

Modulo Arithmetic is just basically the remainder.let's say that we do 7mod3, it is 4 because 7/4 has a remainder of 3. its really simple