4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – reuns Nov 24 '16 at 17:54
6
$\begingroup$

"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^+}$.

$\endgroup$
  • 1
    $\begingroup$ Please note that (for $b > 0$, say) $a = b c + r$ and $0 \le r < b$ implies $a\ \text{mod}\ b = r$. $\endgroup$ – Andreas Caranti Jan 8 '17 at 9:18
  • 2
    $\begingroup$ 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$”. $\endgroup$ – Lubin Jan 9 '17 at 0:28
  • $\begingroup$ Your statement "$a$= $b$ * $c$ + $r$(where b ≠ 0 and r ≥ 0) implies $a$ mod $b$ = $r$" is still incorrect as it stands. $\endgroup$ – Andreas Caranti Jan 9 '17 at 7:21
  • $\begingroup$ @AndreasCaranti why? $\endgroup$ – MrAP Jan 9 '17 at 7:30
  • $\begingroup$ 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$. $\endgroup$ – Andreas Caranti Jan 9 '17 at 8:11
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

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.