MathWiki - modular

Divisibility

Anonymous (anonymous@undisclosed.example.com) — 2014-01-31T22:35:29+00:00

Divisibility In the following, $\mathbb Z$ will denote the set of all integers, i.e. $\mathbb Z = \{\dots, -3, -2, -1, 0, 1, 2, 3, 4, \dots\}$, and $\mathbb N$ will denote the set of all natural numbers (aka positive integers), $\mathbb N = \{1, 2, 3, 4, 5, \dots\}$. 1. Division with remainder Let $b$ be an integer and $a$ be a natural number. Then there exists a unique pair of integers $(q, r)$$b = qa + r$$0 \leq r < a$$q$$r$$b$$a$$r$$b \operatorname{mod} a$$q$$r$$b/a$$0 ≤ r < a$$6/3$$2$$…

Greatest common divisor and least common multiple

Anonymous (anonymous@undisclosed.example.com) — 2014-01-31T22:00:38+00:00

Greatest common divisor and least common multiple Let $a,b\in\mathbb{Z}$. An integer $c$ is common divisor of $a$ and $b$, if $c \mid a$ and $c \mid b$, i.e., $c$ divides both $a$ and $c$. For example, a common divisor of $30$ and $20$ is $10$, but also $5$, $2$ and $1$. Find all common divisors of $18$ and $24$. Answer $6,\ 3,\ 2,\ 1$++ $c$$a$$b$$c$$a$$b$$d$$a$$b$$d\leq c$$c$$20$$30$$10,\ 5,\ 2,\ 1$$10$$\gcd(20,30)=10$$36$$78$$\gcd(36,78)=6$$n = p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$$m = …

Primes and divisibility

Anonymous (anonymous@undisclosed.example.com) — 2014-01-31T21:59:08+00:00

Primes and divisibility A natural number $n$ is a prime number if it has exactly two divisors in $\mathbb N$. These divisors are $1$, which divides all natural numbers, and the number $n$ itself. Anyone can easily recall some smallest prime numbers, e.g., $2,3,5,7,11,13,17$ etc. Although in general, determining whether a given (large) number is prime can be a very resource consuming. Also, the location of primes among integers can not be easily computed, however there are many interesting pat…

Modular arithmetics

Anonymous (anonymous@undisclosed.example.com) — 2015-03-19T17:57:08+00:00

Modular arithmetics $\renewcommand{\mod}{\operatorname{mod}}$ Sometimes when you want to calculate something you might only require the remainder of the answer when divided by some natural number $n$. With help of modular arithmetics finding the required remainder usually happens to be much easier than evaluating the original expression.$a, b$$n$$a \equiv b \ (\mod n)$$a$$b$$n$$a \mod n = b \mod n$$5638 \times 7891 + 2731 \times 3124$$17$$5638 \times 7891 + 2731 \times 3124 = 44489458 + 853164…

Ordered sets

Anonymous (anonymous@undisclosed.example.com) — 2014-01-30T23:07:14+00:00

$\newcommand{\divby}{\mathrel{\vdots}}$ Ordered sets A lattice is actually a special type of a partially ordered set. A relation $\prec$ on a set $X$ is a partial order if * $x \prec x$ for all $x \in X$ (i.e., $\prec$ is reflexive), * $x \prec y$ and $y \prec z$ imply $x \prec z$ for all $x,y,z \in X$ (i.e., $\prec$ is transitive), * $x \prec y$ and $y \prec x$ imply $x = y$ for all $x,y \in X$ (i.e., $\prec$ is antisymmetric$\mathbb Z$$\mathbb N$$\mathbb R$$\le$$\ge$$\subset$$\{\{1\}, …

Residue classes

Anonymous (anonymous@undisclosed.example.com) — 2015-03-19T18:00:27+00:00

Residue classes Modular arithmetics as a way of calculating modulo some number $n$ is a powerful tool. However, it can be made simpler, and thus even more effective. First, recall that numbers having the same remainder when divided by $n$ behave in exactly the same way in such a calculation and yield exactly the same results. $8 * 4 + 11 \equiv 3*(-1) + 6 \equiv 3 (\mod 5)$$n$$n$$n$$n$$a \in \mathbb Z$$n \in \mathbb N$$\overline a = \{b \in \mathbb Z \mid a \equiv b \ (\mod n)\} = \{a + kn \mi…