Number Theory 101
Number theory is basically a set of properties inherent to numbers (in the current chapter we focus on integers), from which you can derive techniques to do neat tricks with really large numbers that would normally be infeasible. Knowing these tricks makes you look like a wizard.
Let's start with a simple definition:
$$a \mathop \backslash b \Leftrightarrow b = ka, \quad k \in \mathbb{Z}$$
In plain English, the statement $a \mathop \backslash b$ means that we can cleanly divide b by a, or that $b/a$ is an integer. We usually say "a divides b". You can visualize it as a backwards divide version of $b/a$ but one that returns 1 if the result is an integer and 0 otherwise. This can be applied to real numbers, but in this post we'll be thinking of this operator exclusively in terms of integers (not that some properties of mod that hold for integers don't hold for all real numbers).
So what's so special about this operation? Well there are a lot of times when you want to factor out a number, but doing so isn't necessarily trivial. If you want to factor some $a$ from some $b$, you need to know first if $a \mathop \backslash b$. We can do this for small queries like if $7 \mathop \backslash 49$ with our grade-school arithmetic training, but most people wouldn't immediately know if $2 \mathop \backslash (3^{77} - 1)/2$, hence we want to develop some concepts and tricks towards answering these questions.
The Modulus Operator
We touched on this last post but now we're giving it a royal treatment. The mod of a number is basically the remainder when you divide it. It's one of the handy life-hacks you want to use when determining divisibility of large numbers.
Mod: The Binary Operator
Thinking with the notion of a remainder, we can define the modulus operation as a component of division.
$$n = m \lfloor n/m \rfloor + n \bmod m$$
Repackaged for the consumer
$$n \bmod m = n - m \lfloor n/m \rfloor$$
We can use our definition of floor to tell us that the value of $n \bmod m$ must be from $[0,m)$
This restriction inverts itself when we use negative values.
$-5 \bmod\ \ \ 3 = -5 - \ \ \ 3 \lfloor -5 / \ \ \ 3 \rfloor = \ \ \ 1$
$\ \ \ 5 \bmod -3 = {-5} - {-3} \lfloor \ \ \ 5 / {-3} \rfloor = -2$
$-5 \bmod -3 = {-5} - {-3} \lfloor {-5} / {-3} \rfloor = -1$
Mod: The Congruence Relation
A quick question: what is the last digit of $10^{1000}$? It should be pretty obvious that it's 0. This fact intuitively clear to us, but why? Congruences.
While the floor division concept of the modulus is fairly intuitive, we want to sort of generalize this a little by thinking of several numbers in a row in terms of the same modulus. The "congruence" means that the numbers are shifted versions of each other. A mod operator with the congruence statement is reflexive in that it applies to the other side. By definition it means:
$$a \equiv b \bmod m \Leftrightarrow m \mathop \backslash (a-b) $$
so a visual representation:
Let's take, for example, $5 \bmod 2$
We notice that any odd number mod 2 will also equal 1, thus any odd number is congruent.
Furthermore, any numbers that are congruent will necessarily have a distance between them that is some multiple of our modulus. In this case, 2.
An alternative but equally valid way to view this repeating property, is by going around a cirlcle with radial coordinates. For example, in our case of $x \bmod 2$, we would get a diagram like this if we traversed our circle and them marked where our number was.
$$a \equiv b \bmod m \Leftrightarrow m \mathop \backslash (a-b) $$
so a visual representation:
Let's take, for example, $5 \bmod 2$
We notice that any odd number mod 2 will also equal 1, thus any odd number is congruent.
Furthermore, any numbers that are congruent will necessarily have a distance between them that is some multiple of our modulus. In this case, 2.
An alternative but equally valid way to view this repeating property, is by going around a cirlcle with radial coordinates. For example, in our case of $x \bmod 2$, we would get a diagram like this if we traversed our circle and them marked where our number was.
another example with $x \bmod 4$
These properties let us rephrase our opening problem as $10^{1000} \equiv 0 \bmod 10$. We can use this to solve less intuitive problems like "what is the last digit $9^{13}$ " by rephrasing it as $9^{13} \bmod 10 \equiv (-1)^{13} \bmod 10 \equiv -1 \bmod 10 \equiv 9$ and this principle works for any number-base, though we're not really focused on numeric base problems.
Here are some properties you should try proving. Hint: try representing some $a \bmod m$ as ${i + km} \bmod m$
$$a \equiv b \bmod m \ \ \text{ and }\ \ c \equiv d \bmod m \\ \ \ \Rightarrow \ \ {a + c} \equiv {b + d} \bmod m \ \ \text{ and } \ \ {a - c} \equiv {b - d} \bmod m$$
$$ba$$
$$a \equiv b \bmod m \Rightarrow {a+k} \equiv {b+k} \bmod m$$
$$a \equiv b \bmod m \Rightarrow {ac} \equiv {bc} \bmod m$$
$$ad \equiv bd \bmod md \Rightarrow {a} \equiv {b} \bmod m$$
$$\text{if }\ \ a \equiv b \bmod m \ \text{&} \ a \equiv b \bmod n \Rightarrow a \equiv b \bmod \frac{mn}{gcd(m,n)}$$
To understand more in-depth number theory, you need to internalize these two functions.
$gcd (m,n) = \{\text{max }k | k \mathop \backslash m,\ k \mathop \backslash n \}$
$lcm (m,n) = \{\text{min }k | m \mathop \backslash k,\ n \mathop \backslash k \}$
A dude named euclid thought of a clever method roughly 2300 years ago. It's often called the world's oldest interesting algorithm. We call this today "Euclid's Algorithm"
$$a \equiv b \bmod m \ \ \text{ and }\ \ c \equiv d \bmod m \\ \ \ \Rightarrow \ \ {a + c} \equiv {b + d} \bmod m \ \ \text{ and } \ \ {a - c} \equiv {b - d} \bmod m$$
$$ba$$
$$a \equiv b \bmod m \Rightarrow {a+k} \equiv {b+k} \bmod m$$
$$a \equiv b \bmod m \Rightarrow {ac} \equiv {bc} \bmod m$$
$$ad \equiv bd \bmod md \Rightarrow {a} \equiv {b} \bmod m$$
$$\text{if }\ \ a \equiv b \bmod m \ \text{&} \ a \equiv b \bmod n \Rightarrow a \equiv b \bmod \frac{mn}{gcd(m,n)}$$
Common Functions: Greatest Common Divisor(GCD) & Least Common Multiple (LCM)
To understand more in-depth number theory, you need to internalize these two functions.
$gcd (m,n) = \{\text{max }k | k \mathop \backslash m,\ k \mathop \backslash n \}$
$lcm (m,n) = \{\text{min }k | m \mathop \backslash k,\ n \mathop \backslash k \}$
A dude named euclid thought of a clever method roughly 2300 years ago. It's often called the world's oldest interesting algorithm. We call this today "Euclid's Algorithm"
Primes
Primes were discovered literally thousands of years ago. The ancient egyptians were aware of them, but the main surviving records are from our man Euclid, who back 300BC proved some important properties about primes.
 |
| This Freaking Guy |
How many primes are there? Euclid proved that there are infinitely many primes (over 2000 years ago lol).
In a sense, primes are the fundamental building blocks of all integers. Every positive integer $n$ can be written uniquely in the form. $n = \prod_{p}p^{n_p},\ \ \text{where}\ 0 \leq n_1 \leq n_1 \leq \dotso \leq n_k $ are all primes
This is called the fundamental theory of arithmetic.
Going back to GCD and LCM, we can observe that, using our prime representation, GCD finds the intersect of two number's prime sets, and LCM finds the union of them.
Numbers are relatively prime if they share no common factors. We notate this with
$$ a \bot b, \ \ \text{ if } \ \ gcd(a,b) = 1$$
This also means that
$$ a \bot b, \ \ \text{ if } \ \ gcd(a,b) = 1$$
We can apply this theorem to test random factors numbers. But surprisingly this also holds for composite numbers using a restriction.
This also means that
$$ a \bot b, \ \ \text{ if } \ \ gcd(a,b) = 1$$
We can apply this theorem to test random factors numbers. But surprisingly this also holds for composite numbers using a restriction.
$$\epsilon_p (n!) = \sum_{k=1} \lfloor \frac{n}{p^k} \rfloor$$
A question you might ask is "how many primes are there"? We can get a rough approximation
A question you might ask is "how many primes are there"? We can get a rough approximation
Fermat's little theorem.
$$n^{p-1} \equiv 1 \bmod p$$
put differently
$$n^{p} \equiv 0 \bmod p$$
Solving a Congruence
So let's think of congruences again, but phrased differently. How do we solve them? Namely,how many solutions does $ax \equiv b \bmod m$ have for $0 \leq x \leq m-1$? My personal approach is to observe think in terms of some basic patterns. (here's a simple R demonstration of what I mean)
We will first notice that when our dividend and divisor are coprime, we nicely iterate between all the integers between 0 and the divisor.
 |
| 2*x mod 3 |
We can prove that this pattern arises due to a pidgeon-hole proof of enumerating through possible answers. That is, if we did have a repeated y value between our modulus range, then our dividend and divisor must share a common factor. In-fact, this common factor is really just an extension of a coprime series.
 |
| 2*x mod 5 |
We can see the same sequence when we factor a new number into the original expression(using the factoring property of modular numbers).
 |
| 4*x mod 10 is the same sequence sequence, but with y*=2 and repeated twice |
We can break this phenomenon into 3 cases:
Case 1: $a \bot m$
-There is 1 solution to $ax \equiv b \bmod m$ in this case as we iterate x in the range $\lbrack 0, m-1 \rbrack$
Case 2: $g = \text{GCD}(a,m) > 1$
-This doesn't reduce to a simpler expression, therefore there is no solution.
Case 3: $g = \text{GCD}(a,m),\ \ g \mathop \backslash b$
-We can factor $g$ out of $a, m, b$ to get the expression
$\frac{a}{g}x \equiv \frac{b}{g} \bmod \frac{m}{g}$, which reduces to case 1, i.e. one of the solvable "intractable" modulus cases we were talking about before. Moreover, since this pattern repeats itself, we know we have $g$ such solutions!
Now, this doesn't tell us how to solve congruences per-se. Rather, it tells us whether a certain problem is solvable. So, given that a problem is solvable(case 1 of our 3 situations), how would we actually solve it?
$$863x \equiv 880 \bmod 2151$$
we can reduce this problem to a simpler problem on a smaller modulus
$$2151y \equiv -880 \bmod 863$$
that is, if we simplify the above statement, we can instead solve
$$425y \equiv 846 \bmod 863$$
Explicitly stated, since $my \equiv -b \bmod a$, then $a \mathop \backslash (my+b)$, which gives us an x where $x = (my+b)/a$, therefore giving us a value that solves the original recurrence.
Let's complete our above example with a full illustration of the process:
$$
863x \equiv 880 \bmod 2151 \\
\Rightarrow \ \ 2151y \equiv -880 \bmod 863 \\
\ \ \ \ \ \ \equiv 425y \equiv 846 \bmod 863 \\
\Rightarrow \ \ 863z \equiv -846 \bmod 425 \\
\ \ \ \ \ \ \equiv 13y \equiv 4 \bmod 425 \\
\Rightarrow \ \ 425w \equiv -4 \bmod 13 \\
\ \ \ \ \ \ \equiv 9w \equiv 9 \bmod 13
$$
The last case is trivial to solve, and we can unwind our solutions to get back to the original statement.
$$
w = 1 \bmod 13 \\
z = (1*425 + 4)/3 = 33 \\
y = (33 * 863 + 846)/425 = 69 \\
x = (2151*69+880)/863 = 173
$$
So, plugging back to the original equation we get
$$863\cdot 173 \equiv 880 \bmod 2151 \\
\Rightarrow 149299 \equiv 880 \bmod 2151$$
which is true since
$$149299 = 69 \cdot 2151 + 880$$
Stern-Brocot Tree
A cool way to enumerate all fractions is with with a simple algorithm known after its creators as a stern-brocot tree. Here are the steps:- Start with ($\frac{0}{1}$,$\frac{1}{0}$)
- Repeatedly insert $\frac{m + m'}{n + n'}$ between two adjacent fractions of $\frac{m}{n}$ and $\frac{m'}{n'}$
So, visually before we do anything we have this
$\frac{0}{1}, \frac{1}{0}$
Then we run one iteration
$\frac{0}{1}, \frac{1}{1}, \frac{1}{0}$
and another
$\frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0}$
and so forth...
$\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0}$
we can visualize this as a binary structure
 |
| stolen from wikipedia |
It has the nice invariant that $m'n - mn' = 1$.
Now, hold this thought for a second as we look at a derived concept of a Farey Series.
$\mathscr{F}_n = \frac{0}{1}, \frac{1}{1}$ with N iterations of our previous algorithm applied, except that at each iteration we discard any fractions whose numberator or divisor exceed $n$.
This is a subtree of the Stern-Brocott tree, and it preserves our invariant.
Back to the original s-b tree. We can think of using the tree as a number system, where LRRL is a descent from the top where you go "left, right, right left" and navigates us to $5/7$. This can be used as an efficient way to compute irrational numbers, and can be done with matrix multiplication.
Factorial Factors
You probably know about the factorial function already, but let's define it for completion
$$n! = n \cdot (n-1) \cdot (n-2) \dotso 3 \cdot 2 \cdot 1 \\
0! = 1$$
Say we want to know the largest power of some prime $p$ that divides $n!$, we can look at a case of this with a table.
The idea here is we want to sum the powers of 2 being contributed from each of the 10 numbers contributing to $10!$. From this table, we get the idea that the answer to our query, which we will call $\epsilon_{p} (n!)$, is equal to $\sum_{k \geq 1} \lfloor \frac{n}{p^k} \rfloor$. This reduces our counting to log(n) computations!
This now gives us the ability to answer a general question: "how large is $\epsilon_p (n!)$ ?"
We can get an upper bound just by using the definition of our floor function
$\epsilon_p (n!) < \frac{n}{p}+\frac{n}{p^2}+ \dotso = \frac{n}{p}(1+\frac{1}{p}+\frac{1}{p^2}+ \dotso ) \\ = \frac{n}{p}(\frac{p}{p-1})\\ = \frac{n}{p-1}$
This also gives us a way to find a bound on $p^{\epsilon_{p} (n!)}$ i.e. $p^{\epsilon_{p} (n!)} < p^{\frac{n}{p-1}}$.
To simplify this, we can add that since $p \leq 2^{p-1}$, then $p^{\frac{n}{p-1}} \leq (2^{p-1})^\frac{n}{p-1} = s^n$ which says that the contribution any prime makes to $n!$ is $< 2^n$.
The limit itself can be used to show there are infinitely many primes(by contradiction), and gives us a rough bound on the number of primes $\pi(n)$, namely $n! < 2^{n \pi(n)}$. If we replace $n!$ with Stirling's approximation, then we get $n\pi(n) > nlg(n/e) + 1/2 lg(2\pi n)$, hence $\pi(n) > lg (n/e)$
$$n! = n \cdot (n-1) \cdot (n-2) \dotso 3 \cdot 2 \cdot 1 \\
0! = 1$$
Say we want to know the largest power of some prime $p$ that divides $n!$, we can look at a case of this with a table.
 |
| p=2, n=10 |
This now gives us the ability to answer a general question: "how large is $\epsilon_p (n!)$ ?"
We can get an upper bound just by using the definition of our floor function
$\epsilon_p (n!) < \frac{n}{p}+\frac{n}{p^2}+ \dotso = \frac{n}{p}(1+\frac{1}{p}+\frac{1}{p^2}+ \dotso ) \\ = \frac{n}{p}(\frac{p}{p-1})\\ = \frac{n}{p-1}$
This also gives us a way to find a bound on $p^{\epsilon_{p} (n!)}$ i.e. $p^{\epsilon_{p} (n!)} < p^{\frac{n}{p-1}}$.
To simplify this, we can add that since $p \leq 2^{p-1}$, then $p^{\frac{n}{p-1}} \leq (2^{p-1})^\frac{n}{p-1} = s^n$ which says that the contribution any prime makes to $n!$ is $< 2^n$.
The limit itself can be used to show there are infinitely many primes(by contradiction), and gives us a rough bound on the number of primes $\pi(n)$, namely $n! < 2^{n \pi(n)}$. If we replace $n!$ with Stirling's approximation, then we get $n\pi(n) > nlg(n/e) + 1/2 lg(2\pi n)$, hence $\pi(n) > lg (n/e)$
Applications
We can extend the gcd algorithm $\text{gcd}(m,n) = b$ to get us coefficients that let us compute $m' m + n' n = b$ for free! This is because the original gcd only uses the remainders, but throws away the quotients. So let's try the same algorithm but keep track of everything.
$
\text{gcd}(240,46) \ \ , 250 - 5 \cdot 46 = 10\\
=\text{gcd}(10,46) \ \ , 46 - 4 \cdot 10 = 6 \\
= \text{gcd}(6,10) \ \, 10 - 1 \cdot 6 = 4 \\
= \text{gcd}(4,6) \ \, 6 - 1 \cdot 4 = 2 \\
= \text{gcd}(2,4) \ \, 4 - 2 \cdot 2 = 0 \\
= \text{gcd}(0,2) \\
$
For the coefficient to 240, we build up the answer our quotient sequence as
$
1 \\
0 \\
1 - 5 \cdot 0 \\
0 - 4 \cdot 1 = -4 \\
1 - 1 \cdot {-4} = 5 \\
{-4} - 2 \cdot 5 = {-9} \\
$
and for 46, similarly
$
0 \\
1 \\
0 - 5 \cdot 1 = {-5} \\
1 - 4 \cdot {-5} = 21 \\
{-5} - 1 \cdot 21 = {-26} \\
{-21} - 2 \cdot {-26} = 47 \\
$
with the result as
${-9} * 240 + 047 * 46 = 2$
$$
x \equiv a_i \bmod m_i \\
m_i \bot m_j, i \neq j \\
m = m_1 \cdot m_2 \dotso m_r
$$
This is sort of similar to solving individual congruences, but we'll show how to do this in a constructive proof.
1) $\frac{m}{m_j}$ must be an integer and $m_j \bot \frac{m}{m_j}$
thus we can say
$\exists \text{integer} b+j | \frac{m}{m_j} b_j \equiv 1 \bmod m_j$
which we know has one solution
2) $\frac{m}{m_j} \cdot b_j \equiv 0 \bmod m_i$
because $m_i \mathop \backslash \frac{m}{m_j},\ \ i \neq j$
Thus we can construct an x by summing
$$x = \sum_{j=1}^r \frac{m}{m_j} b_j a_j$$
which we can then put into our preferred range by adding some multiple of m
This notation, the residue one, gives us a new number system to represent any number in terms of these coprime mods(and a bounds). Think of it as being given an id from the mod-table.
$
\text{gcd}(240,46) \ \ , 250 - 5 \cdot 46 = 10\\
=\text{gcd}(10,46) \ \ , 46 - 4 \cdot 10 = 6 \\
= \text{gcd}(6,10) \ \, 10 - 1 \cdot 6 = 4 \\
= \text{gcd}(4,6) \ \, 6 - 1 \cdot 4 = 2 \\
= \text{gcd}(2,4) \ \, 4 - 2 \cdot 2 = 0 \\
= \text{gcd}(0,2) \\
$
For the coefficient to 240, we build up the answer our quotient sequence as
$
1 \\
0 \\
1 - 5 \cdot 0 \\
0 - 4 \cdot 1 = -4 \\
1 - 1 \cdot {-4} = 5 \\
{-4} - 2 \cdot 5 = {-9} \\
$
and for 46, similarly
$
0 \\
1 \\
0 - 5 \cdot 1 = {-5} \\
1 - 4 \cdot {-5} = 21 \\
{-5} - 1 \cdot 21 = {-26} \\
{-21} - 2 \cdot {-26} = 47 \\
$
with the result as
${-9} * 240 + 047 * 46 = 2$
Chinese Remainder Theorem
This is basically the application of the system of residues. How do we solve a system of $r$ congruences for a number given the following constraints?$$
x \equiv a_i \bmod m_i \\
m_i \bot m_j, i \neq j \\
m = m_1 \cdot m_2 \dotso m_r
$$
This is sort of similar to solving individual congruences, but we'll show how to do this in a constructive proof.
1) $\frac{m}{m_j}$ must be an integer and $m_j \bot \frac{m}{m_j}$
thus we can say
$\exists \text{integer} b+j | \frac{m}{m_j} b_j \equiv 1 \bmod m_j$
which we know has one solution
2) $\frac{m}{m_j} \cdot b_j \equiv 0 \bmod m_i$
because $m_i \mathop \backslash \frac{m}{m_j},\ \ i \neq j$
Thus we can construct an x by summing
$$x = \sum_{j=1}^r \frac{m}{m_j} b_j a_j$$
which we can then put into our preferred range by adding some multiple of m
This notation, the residue one, gives us a new number system to represent any number in terms of these coprime mods(and a bounds). Think of it as being given an id from the mod-table.
 |
| Note, independent residues are the same as CRT, but also give a range to restrict our solution |
In conclusion, number theory is sort of boring(imo) but important for reducing computational work. Just try to learn these basics as a jumping-off point for the algorithms that require these properties.
animations of the concepts found here.
No comments :
Post a Comment