Saturday, October 10, 2015

How does Modulo Arithmetic work




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


Answer



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



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...