Welcome to my Math Notes.

∴

Here you may find various subject notes, mostly as summaries of YouTube lectures, enjoy!

— erhant

Introduction to Number Theory

These are notes taken from Introduction to Number Theory - Berkeley Math 115 open lectures by fields medalist Prof. Richard Borcherds.

The textbook for the course is "An Introduction to the Theory of Numbers" by Niven, Zuckerman, and Montgomery. (5th edition)

1. Introduction: In the first two lectures, a survey of some of the topics covered later in the course is given, mainly about primes and Diophantine equations. The survey continues with some more problems in number theory, and some discussion is made about congruences, quadratic reciprocity, additive number theory, recreational number theory, and partitions.
   

2. Divisibility: This lecture covers basic properties of divisibility, and Euclid's algorithm for finding greatest common divisors. Then, we discuss how to solve linear equations in integers using Euclid's algorithm. Finally, we discuss some basic properties of primes and prove the fundamental theorem of arithmetic.
   

3. Arithmetical Functions: Arithmetical functions are functions that are defined on positive integers; they are quite interesting. In the lecture, we give some examples of multiplicative functions and show how to calculate them. As an application we discuss even perfect numbers.
   

4. Binomial Coefficients: The number of ways you can choose some elements from a set becomes something really cool real quick. In these two lectures, we review the definitions and basic properties of binomial coefficients. Then, we discuss some applications of binonial coefficients, such as an approximate estimate for the number of primes less than $n$, and the Catalan numbers.
   

• Primes
• Fundamental Theorem of Arithmetic
  • Diophantine Equations
• Congruences
  • Fermat's Little Theorem
  • Quadratic Residue
  • Quadratic Reciprocity
• Additive Number Theory
• Recreational Number Theory
• Algebraic Number Theory
• Combinatorial Number Theory

Primes

Primes are numbers divisible by 1 and itself, such as 2, 3, 5.

How many primes are there? There are infinitely many primes. Proven as follows:

1. Suppose there are finitely many $\{p_1,p_2,...,p_m\}$
2. Find $p_1\times p_2\times ...\times p_m+1$.
3. Let $q$ be a prime factor of this number. It cant divide any prime known so far, because that would mean it should divide 1 too. So, $q$ is a new prime.

How can we find large primes? Mersenne primes are in the form $2^n-1$ for prime $n$. There are also Fermat primes, of the form $2^{2^n}+1$. Gauss discovered that regular polygons with the number of sides equal to a Fermat prime can be constructed using a ruler and compass.

Note that $2^{ab}-1=(2^a-1)(2^{ab-a}+\dots +1)$

If $a$ odd, then $2^a+1$ divides $2^{ab}+1$.

Is there an easy way to generate large primes? In other words, is there a non-constant polynomial $f(n)$ such that the result is a prime? NO! To prove, suppose you have $f(n)=a_k{n}^k+\dots +a_{1}k+a_0$. If $a_0>1$ then $f(a_0)$ is composite. If $a_0\ne 1$, then you can find $f(n+k)$ that has the same argument.

How many primes are there up to a given value? This is famously shown as $\Pi (x)$. Gauss found that $\Pi (x)\cong \frac{x}{\log x}$. Informally, a number $n$ has a chance of being prime with probability $\frac{1}{\log n}$.

Suppose we want to find prime powers too, where $p^n$ is counted as $1/n$. Denote this as ${\Pi }^{\prime }(x)$. Let $\text{Li}(x)={\int }_0^x\frac{1}{\log x}dx$ (limit integral). Riemann amazingly found that:

$${\Pi }^{\prime }(x)=\text{Li}(x)-\sum _{\rho }\text{Li}(x^{\rho })$$

where $\rho$ is the zeros of the Zeta function! By the way, $\log x$ throughout this course always refers to the natural logarithm.

Fundamental Theorem of Arithmetic

Every integer is a product of primes in a unique way (up to order). Euler interpreted this as a factorization of the Zeta function:

$$\zeta (s)=\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\dots =\frac{1}{1-2^{-s}}\times \frac{1}{1-3^{-s}}\times \frac{1}{1-5^{-s}}\times \dots$$

This makes a lot of sense if you think the geometric series of the product terms:

$$\zeta (s)=\left(1+\frac{1}{2^s}+\frac{1}{4^s}+\dots \right)\left(1+\frac{1}{3^s}+\frac{1}{9^s}+\dots \right)\left(1+\frac{1}{5^s}+\frac{1}{25^s}\right)\dots$$

You can choose for example $\frac{1}{2^s}$, $\frac{1}{9^s}$ and 1 everywhere else, to obtain $\frac{1}{18^s}$. This also provides a proof or infinitude of primes: $\zeta (1)$ is a diverging harmonic series. So, the product should also be infinite, which requires infinitely many primes!

Diophantine Equations

These are the equations where we seek integer solutions.

• $x^2+y^2=z^2$ (Pythagoras)
• $2x^2=y^2$ which means find $\frac{y}{x}=\sqrt{2}$. This surprised ancient Greek people who thought all numbers were rational!
• $x^n+y^n=z^n$ for $x,y,z>0$ and $n\ge 3$. (Fermat's Last Theorem)

It turns out that finding solutions to most Diophantine Equations are hard.

Hilbert's 10th problem asks: Is there an algorithm to solve all Diophantine Equations?

The answer turned out to be no! (Robinson, Davies, Putnam, and later Matiyasevich).

Congruences

Question: Is 1234567 a square?

No, because the last digit is not possible to be 7 for square numbers. So we kind of look at the number in modulo 10. Modulo is really useful in these kind of questions. We write them as:

$$a\equiv b(\mathrm{mod}m)$$

This notation is by Gauss, and it means that $a-b$ is divisible by $m$. In other words, $m\mid a-b$.

Question: Can you solve $1000003=x^2+y^2$?

You can realize that $x^2\equiv 0,1\mathrm{mod}4$. Then $x^2+y^2\equiv (0,1)+(0,1)\equiv 0,1,2\mathrm{mod}4$. So, the number can not have 3 as the last digit, thus the equation does not have any integer solutions.

Fermat's Little Theorem

Fermat's little theorem is an awesome little theorem, that states:

$$x^p\equiv x(\mathrm{mod}p)\text{(p prime)}$$

$$x^{p-1}\equiv 1(\mathrm{mod}p)\text{(x not divisible by p)}$$

Euler also found that $x^{\varphi (m)}\equiv 1(\mathrm{mod}m)$ for $x,m$ coprime and $\varphi (m)=$ number of integers less than an coprime to $m$. For example: $\varphi (12)=|\{1,5,7,12\}|=4$

Suppose you want to test if $n$ is prime for very large $n$. We can check if $2^n\equiv 2(\mathrm{mod}n)$ (which can be done efficiently).

• If not, then $n$ is definitely not a prime.
• If yes, then we do not know, but it could be a prime.

For Diophantine equations, if $f(x,y,z)=0$ then $f(x,y,z)\equiv 0(\mathrm{mod}m)$. The reverse is not always true, and Hasse Principle describes that. If the latter turns out to be true for all $m$, then most likely $f(x,y,z)=0$.

Quadratic Residue

Can we solve $x^2\equiv a(\mathrm{mod}p)$ for some prime $p$? Here, we refer to $a$ as the quadratic residue. Legendre symbol is a pretty useful notation about this:

$$\left(\frac{a}{p}\right)=\{\begin{array}{ll}+1& \text{if a squaremodp and a,p coprime}\\ -1& \text{if a is not squaremodp and a,p coprime}\\ 0& \text{if a is divisible by p}\end{array}$$

Quadratic Reciprocity

Euler found a relationship between $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ for $p,q$ odd primes.

• $\left(\frac{p}{q}\right)=1$ if $x^2=p+qy$ has an integer solution.
• $\left(\frac{q}{p}\right)=1$ if $x^2=q+py$ has an integer solution.

What Euler discovered is that:

• $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ if $q$ or $p\equiv 1(\mathrm{mod}4)$.
• $\left(\frac{p}{q}\right)\ne \left(\frac{q}{p}\right)$ if $q$ and $p\equiv 3(\mathrm{mod}4)$ and of course $p\ne q$.

This indicates that there is an amazing hidden structure in this seemingly unrelated equations. Such a feeling happens a lot in Number Theory!

Question: Is 3 quadratic residue of 71?

This is asking if $\left(\frac{3}{71}\right)=1$. We can check instead if $\left(\frac{71}{3}\right)=1$. This is easy to find, as $71\equiv 2(\mathrm{mod}3)$ and 2 is not a square, so $\left(\frac{71}{3}\right)=-1$.

Additive Number Theory

Goldbach Conjecture: Is every even number a sum of 2 primes? Examples are $12=5+7$, $14=7+7$ and so on. The answer: we don't know! Chen managed to show that every even number is a sum of prime and a product of two primes ($p+qr$),

Twin Prime Conjecture: Are there infinitely many primes $p$ such that $p+2$ is also prime? We don't know this too, but Zhang proved that $p$ and $p+k$ for $k$ in the order of millions will always have a prime.

Arithmetic Progressions: Can you find arithmetic progressions of primes, such as $5,11,17,23,29,\dots$? Dirichlet has shown that any arithmetic progression in the form $a+nb$ has infinitely many primes.

Recreational Number Theory

Perfect Numbers: A perfect number is equal to the sum of its proper divisors. Example: $6=1+2+3$.

Amicable Numbers: Two numbers are amicable if the sum of their proper divisors give each other, such as 220 and 284.

Collatz Conjecture: Suppose you map $n\to 3n+1$ for odd $n$ and $n\to n/2$ for even $n$. Doing this repeatedly, do you always reach to 1 in the end for all $n$? We do not know yet!

Sum of Digits: Many examples are there for recreational mathematics concerning digit sums. For example, $370=3^3+7^3+0^3$.

Algebraic Number Theory

As an example of algebraic number, consider $m+ni$ for $i=\sqrt{-1}$. These are called Gaussian Integers and they have a unique factorization. For example, $5=(2+i)(2-i)=2^2+1^2$. Notice that $m^2+n^2=(m+ni)(m-ni)$. Sum of squares turn out to be quite special.

Fermat has shown that a prime $p\equiv 1(\mathrm{mod}4)$ can be written as $p=m^2+n^2$. Quite surprising.

Combinatorial Number Theory

An example would be partitioning. $p(n)$ is the number of partitions that you can write $n$ as a sum of smaller integers. $p(5)=7$ because there are 7 different ways to write $5=4+1=3+2=3+1+1=\dots$

It turns out that $p(5n+4)$ is divisible by 5, for seemingly no reason at all. Looking at the sum of:

$$\sum p(n)q^n=1+q+2q+3q^3+5q^4+7q^5+\dots$$

Euler discovered that this is equal to:

$$\frac{1}{1-q}\times \frac{1}{1-q^2}\times \frac{1}{1-q^3}\times \dots$$

• Divisibility
  • Euclid's Division Algorithm
  • Greatest Common Divisor
  • Fibonacci Sequence
• Euclid's Algorithm to Solve Equations
  • Long Division
• Least Common Multiple
• Primality Tests
• Fundamental Theorem of Arithmetic
• Euclid's Proof of Infinitude of Primes
• Last Digit
• Prime Gaps

Divisibility

If $a$ divides $b$, we show this as $a\mid b$. Note that this does not mean $b/a$ is defined, but rather means that $b=xa$ for some integer $x$. This allows $a$ to be 0 too.

• $a\mid 0$ is always true.
• $0\mid b$ is false, unless $b=0$ too.
• $2\mid b$ is a fancy way of saying $b$ is even.

Question: Show that $6\mid n(n+1)(n+2)$ for any $n$.

We can prove with the argument that one of those terms is even and another is divisible by 3. However, there is a better argument. We can consider the binomial $\left(\genfrac{}{}{0ex}{}{n+2}{3}\right)$, which is the number of ways to choose 3 elements from $n+2$ values. This gives $(n+2)\times (n+1)\times (n)$ to choose 3 elements, and they can be ordered in 6 different ways so we divide by 6. Since we are counting the choices here, the result is definitely an integer. As such, 6 divides $n(n+1)(n+2)$.

Question: Show that $8\mid n^2-1$ if $n$ is odd.

Rewrite $n$ as $2m+1$ as it is odd. Now, $n^2-1=4(m^2+m)$. 4 is there alright, and if we can show that $m^2+m$ is even then the whole thing is divisible by 8. Well, rewrite that as $m(m+1)$ and one of those is definitely even.

Definition: Set of $x$ such that $d\mid x$ is called ideal. For the integers ($\mathbb{Z}$), ideal means "closed under + and -".

Euclid's Division Algorithm

Suppose we have integers $a,b>0$. Then Euclid treats this as $b=qa+r$ and we call $q$ the quotient, and $r$ the remainder. Key point: $0\le r<a$.

$d\mid x$ forms an Ideal (closed under +, -). The converse is also true, suppose that $I$ is ideal. Then, $I$ is the set of multiples of some $d>0$.

Suppose $I$ has some $a>0$ (if not, then $I=\{0\}$). Pick the smallest $a\in I,a>0$. Suppose $b\in I$. Then, $b=qa+r$ and $0\le r<a$. Now, $r=b-qa\in I$ because the Ideal was closed under addition and subtraction.

Since $a$ is the smallest element, this implies $r=0$. So, $b=qa$ and thus $I$ is the multiples of $a$.

So, we applied Euclid's Division Algorithm to show that ideals of integers are exactly the same of multiples of some particular element.

Greatest Common Divisor

For $a,b$, the greatest common divisor is the largest integer $d$ such that $d\mid a$ and $d\mid b$.

• If $a=b=0$ then there is no largest integer that divides both. For conventional reasons, we set $\text{GCD}(0,0)=0$.
• To indicate GCD in elementary number theory, people sometimes use $(a,b)$ as the notation.
• $\text{GCD}(0,a)=a$ even if $a=0$.

Naïve: How do we find the GCD? The naïve method is to check all numbers up to the smallest of the two, and find the first one that divides both. However, this is really slow.

We want a fast algorithm. By fast, we kind of mean that it takes a reasonable amount of time even if the numbers have hundreds of digits (there are more technical definitions).

Better: We can factor $a,b$ into primes. The GCD can be found by looking at the common prime factors (up to order). For example, $24=2^3\times 3$ and $180=2^2\times 3^2\times 5$. Taking the maximum common factors in both, we get $12=2^2\times 3$.

This is cool, but factoring large numbers is hard. So we are still not that efficient.

Cool: Euclid's Algorithm is very efficient. This is probably the oldest mathematical algorithm still in use. We will describe with an example.

We are given 78 and 14. We will do division with remainder, until the remainder is 0:

• $78=14\times 5+8$
• $14=8\times 1+6$
• $8=6\times 1+2$
• $6=2\times 3+0$

The answer is the latest quotient: 2. Note that we know this algorithm will terminate for sure, because the remainder gets smaller on each step. The algorithm kind of looks at the GCD as follows: $(78,14)=(14,8)=(8,6)=(6,2)=(2,0)=2$. This comes from the fact that $(x,y)=(x,xq+r)=(x,r)$.

How fast is this method? Let us consider the worst case. We look at $b=qa+r$, and we want small $r$. The worst case is when $q=1$. For example, $(13,8)$.

• $13=8\times 1+5$
• $8=5\times 1+3$
• $5=3\times 1+2$
• $3=2\times 1+1$
• $2=1\times 2+0$
• aaand we are done!

We notice that we can work our way up backwards, the remainders follow the recursive pattern $r_i=r_{i+1}+r_{i+2}$ for this example. Looks familiar?

Fibonacci Sequence

This sequence 0, 1, 1, 2, 3, 5, $\dots$ is the Fibonacci numbers. $F_n$ is the $n^{th}$ Fibonacci number, and the worst case of Euclid's algorithm is when we are finding $(F_n,F_{n+1})$.

Let us find out how fast does Fibonacci grows.

• _Lower: 0, 1, 1, 2, 2, 4, 4, 8, 8, ...
• Actual: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
• ^Upper: 0, 1, 2, 4, 8, 16, 32, 64, 128, ...

This gives us the growths $2^{n/2}<F_n<2^n$. In particular, we see that $n\approx c\times \log F_n$ for some constant $c$, and $n$ is the number of steps in Euclid's algorithm.

So, the number of steps of Euclid's algorithm $\le c\times \log n$ which is approximately $c\times \text{\# digits}$.

Is there a formula to find $F_n=F_{n-1}+F_{n-2}$ for $F_0=0,F_1=1$? This is an example of "Finite Difference" equation by the way. Note that "General Finite Difference" equations have the form:

$$F_n=a_1{F}_{n-1}+a_2{F}_{n-2}+a_3{F}_{n-3}+\dots$$

for constants $a_1,a_2,a_3,\dots$

The method to solve these equations is to literally guess the answer. That doesn't sound cool, so instead we say you find the ansatz (which means guess).

With ansatz we guess the form of the answer with some unknown coefficients. You could take a guess like $F_n=n^{\lambda }$, or perhaps $F_n={\lambda }^n$ for some constant $\lambda$. The constants $a_1,a_2,\dots$ should also be guessed in those. The latter guess seems to work quite nicely for Finite Difference equations.

Looking at $F_n=F_{n-1}+F_{n-2}$, we have ${\lambda }^n={\lambda }^{n-1}+{\lambda }^{n-2}$. So, ${\lambda }^2=\lambda +1$. The solutions are $\lambda =(1\pm \sqrt{5})/2$. Hmm, that's not cool because those are not integers. But we do not give up. What if the answer is a linear combination of these solutions?

$$a{\left(\frac{1+\sqrt{5}}{2}\right)}^n+b{\left(\frac{1-\sqrt{5}}{2}\right)}^n$$

Now we will try to adjust $a,b$ to get the Fibonacci numbers. Thankfully, we know $F_0$ and $F_1$. This gives us:

• $a+b=0$
• $a\left(\frac{1+\sqrt{5}}{2}\right)+b\left(\frac{1+\sqrt{5}}{2}\right)=1$

We thus find $a=1/\sqrt{5}$ and $b=-1/\sqrt{5}$. So,

$$F_n=\frac{1}{\sqrt{5}}{\left(\left(\frac{1+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)\right)}^n$$

Fibonacci numbers have quite a lot of cool and funny properties (proofs left as exercise):

• $5F_n^2\pm 4$ is always a square.
• $F_n^2=F_{n-1}\times F_{n+1}\pm 1$.

The number $(1+\sqrt{5})/2$ is known as the Golden Ratio (shown as $\varphi$ or $\tau$ sometimes).

Euclid's Algorithm to Solve Equations

Suppose we know $(a,b)=d$ and the problem is to solve $ax+by=d$. We can solve by using the same algorithm described in the previous section. For example, lets find $71x+17y=1$. We first find the GCD:

• $71=4\times 17+3$
• $17=5\times 3+2$
• $3=1\times 2+1$
• $2=2\times 1+0$

The GCD is 1. Now we work our way backwards:

• $1=3-1\times 2$
• $1=3-1\times (17-5\times 3)=6\times 3-1\times 17$
• $1=6\times (71-4\times 17)-1\times 17$
• $1=6\times 71-25\times 17$

Et voila! We found $1=6\times 71-25\times 17$, so $x=6$ and $y=-25$.

Note that $ax+by=c$ is solvable if and only if $(a,b)\mid c$. We can find the solution for $(a,b)$ and the just multiply the findings to reach $c$. Also note that once you find $x,y$, other solutions are possible such as $x+b,y-a$. What about linear equations in 3 variables? Such as:

$$6x+10y+15z=1$$

Well, we can solve two at a time, referring to $6x+10y=2$ (since $(6,10)=2$), giving us $x=2$ and $y=-1$. Then, we find $2w+15z=1$ (since $(2,15)=1$). There we find $w=-7$ and $z=1$.

• $2(-7)+15(1)=1$
• $(6(2)+10(-1))(-7)+15(1)=1$
• $6(-14)+10(7)+15(1)=1$

Done! $x=-14,y=7$ and $z=1$.

Again, we can only solve $ax+by+cz=n$ if and only if $(a,b,c)\mid n$. This actually works for an arbitrary number of variables!

The problem with Euclid's Algorithm is that it is using "long division", which is slow and complicated. For large numbers, computers don't really know how to do it, and you have to program it yourself. Even Intel got it wrong back in the day.

Long Division

We can avoid long division by being a bit more clever, and doing divisions by two only (which is really fast on computers). To solve $ax+by=c$ we do as follows:

1. Take out all factors of 2 from $a$ and $b$. And now assume that $a\ge b$ and both are odd.
2. Change $a$ to $a-b$. Now $a-b$ has to be even.
3. If the result is 0, stop.
4. Otherwise, take out the factors of 2, and go back to step 2.

Least Common Multiple

Given $a$ and $b$, the least common multiple is the smallest number divisible by $a$ and $b$, and is less than or equal to $ab$. For example, $\text{LCM}(12,18)=36$. It turns out that:

$$\text{LCM}(a,b)=\frac{a\times b}{\text{GCD}(a,b)}$$

This is actually a bit obvious when we look at the factors.

• $a=2^{m_2}\times 3^{m_3}\times 5^{m_5}\times \dots$
• $b=2^{n_2}\times 3^{n_3}\times 5^{n_5}\times \dots$
• $ab=2^{m_2+n_2}\times 3^{m_3+n_3}\times 5^{m_5+n_5}\times \dots$
• $\text{GCD}(a,b)=2^{\min (m_2,n_2)}\times 3^{\min (m_3,n_3)}\times 5^{\min (m_5,n_5)}\times \dots$
• $\text{LCM}(a,b)=2^{\max (m_2,n_2)}\times 3^{\max (m_3,n_3)}\times 5^{\max (m_5,n_5)}\times \dots$

Now notice that $n+m=\min (m,n)+\max (m,n)$. Therefore, $ab=\text{GCD}(a,b)\times \text{LCM}(a,b)$.

Primality Tests

A prime $p$ is an integer $>1$ not divisible by anything except $1$ and $p$. 1 is not a prime, because it is defined that way and it is very convenient to define it that way (although not everyone agree with them).

Alternatively, we could allow negative integers too such as $-2,-3,-5,\dots$. In that case: a prime $p$ is an integer $p\ne 0$ such that if $p=ab$ then $a$ or $b$ is a unit. A unit is something that has an inverse, and the only units for integers are $1$ and $-1$.

A naïve method would check if a number $n$ is divisible by anything smaller than itself $<n$. It is very inefficient. We speed up this by:

• Checking only primes in the division
• Checking up to $\le \sqrt{n}$

As such, the number of steps for this method would be $\approx \sqrt{n}$. Even then, this is too slow if $n$ is large (like 100 digits or something).

For very large methods, you could first check if it is divisible for some small primes, and then go on to the more advanced test methods.

Fundamental Theorem of Arithmetic

Any number $n\ge 1$ is a product of primes in a unique way up to order. Note that $1$ is a product of the empty set of primes (this is a nice convention).

Alternatively, allowing negative integers: any number $n\ne 0$ is a product of primes and a unit (1 or -1) in a unique way up to order and then up to units.

Proof: We have two parts: an easy part for existence, and hard part for the uniqueness.

1. Easy part (Existence): Take $n\ge 1$. If $n=1$ or $n$ is prime, then we are done. Otherwise $n=ab$ where $1<a<n,1<b<n$.

   So by induction, $a$ is a product of primes $p_1,p_2,\dots$ and $b$ is a product of primes $q_1,q_2,\dots$ and thus $n$ is a product of primes $p_1,p_2,\dots ,q_1,q_2,\dots$.

2. Hard part (Uniqueness): Suppose $p$ is prime, and $p\mid ab$. Then, $p\mid a$ or $p\mid b$. This is the central key result in order for this proof to work.

   Suppose $p\nmid a$, then $(a,p)=1$ as $p$ is prime. By Euclid, $ax+py=1$ for some integers $x,y$. Now multiply by $b$ to obtain $bax+bpy=b$. Well, $p$ divides $ab$ and $p$ also divides $bp$, therefore $p$ divides $b$ (right-hand side).

   Now lets suppose $n=p_1\times p_2\times \dots =q_1\times q_2\times \dots$. Then $p_1\mid q_1\times q_2\times \dots$. So, $p_i\mid q_i$ for some $i$, but $q_i$ is prime, so $p_i=q_i$. You can repeat this by diving all the newly found $p_i$. So, the factorization is unique up to order.

We can also give a similar result for polynomials over $\mathbb{R}$. Take $f(x)=a_0+a_{1}x+\dots$. Here, the units are non-zero constant polynomials, and every non-zero polynomial can be written as a product of irreducible polynomials and constant polynomials.

Real numbers don't have primes, because any real $x\ge 1$ can be written as $x=\sqrt{x}\times \sqrt{x}$

What about integers in the form $4n+1$, such as $1,5,9,13,17,21,\dots$? Well, you indeed have "primes" where the product is like $(4n+1)(4m+1)=4(mn+m+n)+1$. However, the factorization is not unique, e.g. $9\times 49=21\times 21$.

Both examples (reals and number 1 mod 4) were not closed under addition and subtraction. Maybe that was the cause of non-uniqueness? Well, lets see one example that is closed!

Lets look at functions on reals $\ge 0$. We can multiply, add or subtract them point-wise. Well, turns out we can't write functions as a product of "prime" functions, for example:

• $x=\sqrt{x}\times \sqrt{x}$
• $\sqrt{x}=\sqrt[4]{x}\times \sqrt[4]{x}$
• it goes on like that, and none of them are units.

Another example: take all numbers of the form $m+n\sqrt{-5}$ where $m,n$ are integers. This is an example of algebraic number field. Well, this is not unique too, $6=2+3=(1+\sqrt{5})(1-\sqrt{-5})$.

We will later see that number of the form $m+n\sqrt{-1}$ have unique factorization! These are called Gaussian Integers. Units here are $\pm 1,\pm \sqrt{-1}$

Euclid's Proof of Infinitude of Primes

We have shown this in the first lecture. In three lines:

• $p_1,\dots ,p_m$
• $q\mid p_1\times p_2\times \dots p_m+1$
• $q\ne p_1,p_2,\dots ,p_m$, so $q$ is a new prime.

Note that $p_1\times p_2\times \dots p_m+1$ is not necessarily a prime! Thinking that this is the case is a common mistake.

Here is a cool question: suppose you find the primes following the proof described above (so you take $q$ in every step). You will get $2,3,7,43,13,\dots$ and such. Do all primes appear? We do not know, and it is very hard to check this, but it is almost certainly yes!

Suppose we take some prime, does 101 appear? Well, almost certainly yes! The change that it appears at step $n$ is $\approx 1/101$. This is because we are dividing a number by 101 (so that $q=101$), which is possible every 101 numbers over integers.

So, the chance that it does not appear at step $n$ is $(1-1/101)$. The chance it does not appear at step $\le n$ is $\approx (1-1/101{)}^n$. If you take a very large $n$, this approaches 0. I really liked this proof!

Nevertheless, proving that all primes are given seems to be really hard. We have just no idea how to prove it.

Last Digit

We know that the last digit of primes should be 1, 3, 7 or 9 (other than 2 and 5 for their respective numbers). We may ask, are there infinitely many primes with the last digit 1, i.e. primes of form $10n+1$? Dirichlet proved that yes, indeed there are!

Well, are there infinitely primes in the form $an+b$ where $(a,b)=1$ and $a\ne 0$? Dirichlet's proof on arithmetic progressions actually prove that yes, there are infinitely many primes in all arithmetic progressions.

Let us check some easy cases. Take primes of form $4n+3$. Well, you could do a variation of Euclid's proof. Take number $4\times p_1\times p_2\times \dots \times p_k-1$. This number is indeed of form $4m+3$, and:

• It is not divisible by any of the $p_1,p_2,\dots ,p_k$.
• It must have at least one factor that is not of form $4m+1$. This is because product of primes of that form result in $4m+1$ too, so one prime must be of form $4m+3$ for the result to be of form $4m+3$
• Consequently, there must be a new prime factor of form $4m+3$.

You could do a similar thing for primes of form $3n+2$.

What about $4n+1$? We can't use the previous proof on this one. However, we could notice the fact: if a prime $p$ is one that $p\mid m^2+1$ then $p=2$ or it is of the form $4n+1$ (proof later). Now suppose you have a number:

$$(2\times p_1\times p_2\times \dots \times p_k{)}^2+1$$

We have 2 in there so that the result is odd, and square so that the result is of form $m^2+1$ which a prime can divide. All primes in there were of form $4n+1$ or $2$. The result is obviously not 2, nor any of the existing primes. So, there must be a new prime factor of that number.

Prime Gaps

Looking at $2,3,5,7,11,13,17,19,23,29$ we have varying amount of gaps. Is there a bound to the gaps?

The answer turns out to be no. It is easy to show, as you can take numbers $n!+2,n!+3,\dots ,n!+n$ and there will be $n-1$ numbers that are not prime. Well, $n-1$ is slightly less than $\log (n!)$. Turns out that the average size of prime gap is $\approx \log (n)$. It is very hard to show that gap is sometimes bigger or smaller than this.

Zhang has shown that gap is sometimes less than $70,000,000$ for large $n$, in an amazing breakthrough. It has been reduced to a few hundreds recently.

It is believed that there are infinitely many consecutive primes with gap 2. It is also conjectured that the gap is sometimes $\approx (\log n{)}^2$. This seems to be very hard to prove.

Another crazy result by Rankin (1938) shows that the gap is sometimes bigger than:

$$\frac{1}{3}\frac{\log n\log \log n\log \log \log \log n}{(\log \log \log n{)}^3}$$

Bizarre!

• Strictly Multiplicative Functions
• Multiplicative Functions
  • $d(n)$ number of divisors
  • $\sigma (n)$ sum of divisors
  • Euler's Phi Function $\varphi (n)$
  • Ramanujan Tau Function $\tau (n)$
  • Moebius Function $\mu (n)$
• Perfect Numbers
  • Odd Perfect Numbers
  • Landau's Hard Problems about Primes

An arithmetical function is just a function defined on positive integers. $f:1,2,3,\dots \to \mathbb{R}$ or some other domain.

Strictly Multiplicative Functions

Take $f(n)=n^k$.

• $f(mn)=f(n)f(m)$ means that it is strictly multiplicative.

A simple example is $f(n)=n^k$.

Recall Legendre symbol from before, $f(n)=\left(\frac{n}{p}\right)$ is strictly multiplicative.

Another strictly multiplicative function example is the Liouville function $\lambda (n)=(-1{)}^{\Omega (n)}$ where $\Omega (n)$ is the number of prime factors. For example, $60=2^2\times 3^1\times 5^1$ so $\Omega (60)=2+1+1=4$.

Notice that $\Omega (mn)=\Omega (m)+\Omega (n)$ and therefore $\lambda (mn)=\lambda (m)\lambda (n)$.

Multiplicative Functions

These are functions where $f(mn)=f(m)f(n)$ when $(m,n)=1$ (they are coprime).

$d(n)$ number of divisors

An example: $f(n)=d(n)$ which is just the number of divisors of $n$. In this case, $d(60)$ may be a bit laborious to compute by hand, but we can be more clever. Look at the factors of $60=2^2\times 3^1\times 5^1$. So, its divisors can be of the form $2^a\times 3^b\times 5^c$ where $a\le 2,b\le 1,c\le 1$. This gives us $3\times 2\times 2=12$ possibilities, which is our answer.

In general, given $n=p_1^{n_1}{p}_2^{n_2}\dots$ then $d(n)=(n_1+1)(n_2+1)\dots$. If two numbers $m,n$ are coprime, then $d(mn)=d(m)d(n)$.

$\sigma (n)$ sum of divisors

Another example is $\sigma (n)$ which is the sum of divisors. What is $\sigma (60)$? Again we can look at the factors $60=2^2\times 3^1\times 5^1$ and we take the sum as $(1+2^1+2^2)(1+3^1)(1+5^1)=156$.

In general, given $n=p_1^{n_1}{p}_2^{n_2}\dots$ then $\sigma (n)=(1+p_1+\dots +p_1^{n_1})(1+p_2+\dots +p_2^{n_2})\dots$ and notice that these are geometric series, so $\sigma (n)=(\frac{p_1^{n_1+1}-1}{p_1-1})(\frac{p_2^{n_2+1}-1}{p_2-1})\dots$. If $n=pq$ for two primes $p,q$ then $\sigma (n)=(p+1)(q+1)$.

Euler's Phi Function $\varphi (n)$

Euler's $\varphi$ function is also a well-known multiplicative function. $\varphi (n)$ is the number of numbers $\le n$ and are coprime to $n$. Turns out that $\varphi (mn)=\varphi (m)\varphi (n)$ if $(m,n)=1$.

Ramanujan Tau Function $\tau (n)$

Take $f(q)=q(1-q{)}^{24}(1-q^2{)}^{24}(1-q^3{)}^{24}\dots$. Turns out that this is equal to: $q-24q^2+252q^3+1472q^4+4830q^5-6048q^6+\dots =\sum \tau (n)q^n$.

Ramanujan noticed that $\tau (mn)=\tau (m)\tau (n)$ when $(m,n)=1$.

Moebius Function $\mu (n)$

Let $\mu (n)$ to be:

$$\mu (n)=\{\begin{array}{ll}0& \text{if n divisible by a square >1}\\ (-1{)}^{\omega (n)}& \text{if n divisible by ω(n) primes}\end{array}$$

Turns out $\mu (mn)=\mu (m)\mu (n)$ when $(m,n)=1$. Well that is a pretty funny function right? Check this out: recall the Zeta function

$$\zeta (s)=\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\dots$$

If you look at its inverse:

$$\frac{1}{\zeta (s)}=\frac{1}{1^s}+\frac{\mu (2)}{2^s}+\frac{\mu (3)}{3^s}+\dots$$

Perfect Numbers

A perfect number is one that is equal to the sum of all its proper divisors. So any number where $2n=\sigma (n)$ holds. Euclid gave a way to find perfect numbers in his Elements book. If you take $2^{p-1}(2^p-1)$ where $2^p-1$ is a prime, this number is perfect. (easy to prove)

Euler found that even perfect numbers can only be in this form. Suppose $n=2^a{p}^b{q}^c\dots$ where $p,q,\dots$ are odd primes. It has divisors:

$$\{1,2,4,\dots ,2^n\}\times \{1,p,p^2,\dots ,p^b\}\times \dots$$

Now suppose you take the sum $(1+2+\dots +2^a)(p^b+p^{b-1})q^c\dots$. When you multiply these you have $(2^{a+1}-1)(p+1)p^{b-1}{q}^c\dots$. Well, this is equal to

$$2n\times \left(1-\frac{1}{2^{a-1}}\right)\times \left(1+\frac{1}{p}\right)\times \dots$$

We have only taken a part of the sum of divisors, and we already have $2n$ which was the condition to be a perfect number, so the remaining terms have the inequality:

$$\left(1-\frac{1}{2^{a-1}}\right)\times \left(1+\frac{1}{p}\right)\times \dots \le 1$$

On the other hand, notice that $2^{a+1}-1$ is an odd number within the whole sum, but our number is even ($2n$). So, there must be a smallest prime factor $p$ that divides $2^{a+1}-1$ (so that the result is not odd). This means that $p\le 2^{a+1}-1$. This implies that

$$\left(1-\frac{1}{2^{a-1}}\right)\times \left(1+\frac{1}{p}\right)\times \dots \ge 1$$

We have $\le 1$ and $\ge 1$ at the same time, so that means this is in fact equal to 1.

Therefore, we see that we can't really have any other divisors other than $p$, and $p=2^{a+1}-1$. So, even perfect numbers must be of form: $2^a(2^{a+1}-1)$. This gives us even perfect numbers, but are there infinitely many even perfect numbers? We don't know yet, but probably yes.

Odd Perfect Numbers

Are there any odd perfect numbers? Well, nobody knows. This is quite an old problem, discussed around 2000 years ago! You could put some nice restrictions on it though. Suppose:

$$n=p_1^{n_1}{p}_2^{n_2}\dots$$

and $\sigma (n)=2n$. Looking at $\sigma (n)$:

$$\sigma (n)=2n=(1+p_1+\dots +p_1^{n_1})(1+p_2+\dots +p_2^{n_2})\dots$$

Notice that if $n_1$ is odd, the sum $1+p_1+\dots p_1^{n_1}$ is even. Since the product should be $2n$, only one of these sums may be even, i.e. only one exponent can be odd. So, the other exponents are even numbers. This implies that $n$ is a prime times a square as in:

$$n=p_1\times (p_1^{n_1-1}\times p_2^{n_2/2}\times \dots {)}^2$$

Landau's Hard Problems about Primes

• Are all even numbers sum of two primes, $2n=p+q$? (Goldbach)
• Can we find infinitely many primes $p,q$ such that $p-q=2$? (Twin Primes)
• Can we always find a prime $p$ for any $n$ such that $n^2<p<(n+1{)}^2$?
• Can we find infinitely many primes of the form $p=n^2+1$?

We don't know the answer to these, we don't even have an idea on how to approach them. However, we believe the answer is yes.

• Binomial Coefficients
  • Binomial Polynomials
  • Properties of Binomial Coefficients
• Dividing a Factorial
• How big is a binomial coefficient?
  • Stirling's Formula
• Application to Prime Number Theorem
  • Another application

Binomial Coefficients

We denote Binomial Coefficients as $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ meaning ($n$ choose $k$) and it corresponds to number of $k$ element subsets of an $n$ element subset. For example, $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Binomial (roughly means "two names") corresponds to sum of two things. This is where the coefficients comes from:

$$(x+y{)}^n=(\genfrac{}{}{0ex}{}{n}{0})x^n{y}^0+(\genfrac{}{}{0ex}{}{n}{1})x^{n-1}{y}^1+\dots +(\genfrac{}{}{0ex}{}{n}{n})x^0{y}^n$$

There is an explicit formula for binomial coefficient:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{(n-k)!\times k!}$$

More explicitly:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n(n-1)(n-2)\dots (n-k+1)}{k!}$$

In that case, the numerator is number of ways we can pick $k$ elements, and the denominator is to handle the different ways we could have taken them. Pascal's triangle can also give you these results, but note that Pascal wasn't the first one to find that.

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
// and so on..

Notice that this triangle tells us:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$

Even more, a number in the triangle is equal to the sum of numbers above it in the previous column. In other words:

$$\left(\genfrac{}{}{0ex}{}{0}{k}\right)+\left(\genfrac{}{}{0ex}{}{1}{k}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$$

This is very handy as we will see in a moment.

You could also have trinomials:

$$(x+y+z{)}^n=\sum _{i,j,k}(?)x^i{y}^j{z}^k$$

What should be the $(?)$ there? Well, the things we had for binomials are actually easily generalizable.

$$(?)=\frac{n!}{i!j!k!}$$

You could have a three-dimensional Pascal's triangle (like Pascal's Tetrahedron) and you would find these values. Let us look at the Pascal triangle again:

     1 // only 1s
    1 / 1 // all numbers
   1 / 2 / 1 // Triangular numbers
  1 / 3 / 3 / 1 // Tetrahedral numbers
 1 / 4 / 6 / 4 / 1 // 4-dim Tetrahedral numbers
// and so on..

In general, the $k^{th}$ column gives you the $k-dim$ tetrahedral numbers.

Binomial Polynomials

Let us look at several cases:

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{1}\right)=n$$

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}=\frac{1}{2}{n}^2-\frac{1}{2}n$$

$$\left(\genfrac{}{}{0ex}{}{n}{3}\right)=\frac{n(n-1)(n-2)}{6}=\frac{1}{6}{n}^3-\frac{1}{2}{n}^2+\frac{1}{3}n$$

Now, these polynomials have real coefficients but we are calculating ways to chose elements, so the result is integer. This is a very nice property, namely: if $n$ is an integer, then these polynomials result in an integer.

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}=\frac{1}{2}{n}^2-\frac{1}{2}n$$

What if instead of $n^k$ we used $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$?

The upper triangular part of this table is quite nice, the diagonal is just 1s and the upper part is just 0s. What if we wrote $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ instead of $n^k$ in our polynomials?

$$a_0\left(\genfrac{}{}{0ex}{}{n}{0}\right)+a_1\left(\genfrac{}{}{0ex}{}{n}{1}\right)+a_2\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\dots$$

This polynomial has a really nice property: the result is an integer for all $n$ if and only if $a_i$ are integers. We cant say the same for when we use $n^k$, for example:

$$\frac{n^3}{6}+\frac{5n}{6}$$

is always an integer perhaps? Let us use the binomial polynomial in an example. We remember from high-school:

$$0^2+1^2+2^2+\dots +n^2=\frac{n(n+1)(2n+1)}{6}$$

How would we prove this? Well, notice that

$$n^2=2\frac{n(n-1)}{2}+n=2\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)$$

Then, the sum of squares is:

$$2\left(\left(\genfrac{}{}{0ex}{}{1}{2}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{2}\right))+(\left(\genfrac{}{}{0ex}{}{1}{1}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{1}\right)\right)$$

Using the property we have shown above for the triangle:

$$2\left(\genfrac{}{}{0ex}{}{n+1}{3}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{n(n+1)(2n+1)}{6}$$

Properties of Binomial Coefficients

First, let us rewrite the two properties we have shown before:

• Pascal's Triangle:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$

• Sum of binomials:

$$\left(\genfrac{}{}{0ex}{}{0}{k}\right)+\left(\genfrac{}{}{0ex}{}{1}{k}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$$

• Complementing Coefficient:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$$

• Sum of the rows in Pascal's Triangle:

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)=2^n$$

This can be interpreted (combinatorially) as: sum of number of 0 element subsets, 1 element subsets, $\dots$, $n$ element subsets. This is equal to number of all subsets of a set with $n$ elements, which is $2^n$. You can prove this with generative function $(x+y{)}^n$ with $x=y=1$.

• A Useful Sum:

$$\sum _i\left(\genfrac{}{}{0ex}{}{m}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{k-i}\right)=\left(\genfrac{}{}{0ex}{}{m+n}{k}\right)$$

It is cool to show this combinatorially (just draw two sets and try to pick $k$ elements in total from both).

• Alternating Sums:

     1 = 1
    1 - 1 = 0
   1 - 2 + 1 = 0
  1 - 3 + 3 - 1 = 0
 1 - 4 + 6 - 4 + 1 = 0
// and so on..

You will always get 0. You can prove this both combinatorially, or with generative function $(x+y{)}^n$ by giving $x=1$ and $y=-1$.

Recall lattice paths problem, you can solve it using binomial coefficients. Furthermore, you can divide things up using binomial coefficients. For example, you have 5 pirates and you would like to divide up 100 gold coins. In other words: $a+b+c+d+e=100$ where $a,b,c,d,e$ are integers $\ge 0$. Well, you could think of:

o o | o o o o | o ... o | o | o o

where o is a coin and | is a separator, so the coins between separator (and ends) denote the number of golds for a pirate. Well, this can be interpreted as: how many ways could we place these separators? There are 104 positions, and we have 4 separators, so the result is:

$$\left(\genfrac{}{}{0ex}{}{104}{4}\right)$$

Let us look at binomial coefficients in modulo 2.

        1 // row 0
       1 1 // row 1
      1 0 1 // row 2
     1 1 1 1
    1 0 0 0 1 // row 4
   1 1 0 0 1 1
  1 0 1 0 1 0 1
 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1 // row 8

This is just like Sierpinsky Triangle! Notice that when the row is a power of two, we get almost all zeros:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0\text{ if }n=2^{\ast }\text{ and }0<k<n$$

What if we do this with other primes? Let us look at modulo 3:

   1
  1 1
 1 2 1
1 0 0 1 // row 3

Indeed we get the same pattern at a power of that prime. This is a general property. For prime $p$, $\left(\genfrac{}{}{0ex}{}{p}{k}\right)=0$ and $0<k<p$; and furthermore $\left(\genfrac{}{}{0ex}{}{p}{0}\right)=\left(\genfrac{}{}{0ex}{}{p}{p}\right)=1$. You can prove this by looking at the expression:

$$\frac{p!}{k!\times (p-k)!}$$

The numerator is obviously divisible by $p$ (which would give 0 in modulo $p$), and the denominator is only divisible by $p$ if $k=p$ or $k=0$, which are the edge cases. This has a funny application. Take $(x+y{)}^p$, you would get:

$$(x+y{)}^p=x^p+y^p+p(\dots )$$

In modulo $p$, you would only get $x^p+y^p$. This is true for prime powers too.

$$(x+y{)}^{p^2}=(x^p+y^p+p(\dots ){)}^p=x^{p^2}+y^{p^2}+p(\dots )$$

So the property we have shown above is actually general to prime powers:

$$\left(\genfrac{}{}{0ex}{}{p^n}{k}\right)\text{ is divisible by }p\text{ if }0<k<p^n$$

Dividing a Factorial

We would like to find how many times a prime $p$ divides $n!$. We can find this as:

$$\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\dots$$

where $[a]$ takes the integer part of $a$. This is a finite sum, as when $p^{\ast }$ gets large enough the term would be $0$. This formula just comes from looking at the number in $n!$ as:

$$n!=1\times 2\times \dots \times p\times \dots \times 2p\times \dots \times n$$

A rough estimate of this sum is just the series:

$$\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+\dots =\frac{n}{p-1}$$

Q: How many zeros are there in the decimal representation of $1000!$? A: We can find this by checking how many times $2$ and $5$ divide this together (i.e., how many times $10$ divides this number). It is calculated from the above formula.

$\left[\frac{1000}{5}\right]=200$, $\left[\frac{200}{5}\right]=40$, $\left[\frac{40}{5}\right]=8$, $\left[\frac{8}{5}\right]=1$ and $\left[\frac{1}{5}\right]=0$; in total 249. We can do the same for $2$, but the result will be larger than 249 surely, so we can say 10 divides this number 249 times in total and therefore there are 249 zeros in the end.

A similar method can be used to find how many times $p$ divides $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. For that, you find how many times $p$ divides $n!$, and then subtract how many times $p$ divides $k!$ and $(n-k)!$.

How big is a binomial coefficient?

We sometimes want to know roughly how big a binomial coefficient is. A crude estimate is that we can have the upper bound:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^n$$

since the sum of the $n^{th}$ row is $2^n$.

We can also look at the middle coefficient (the largest coefficient) of a row:

$$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\ge \frac{2^{2n}}{2n+1}$$

which is because the sum of that row is $2^{2n}$ and the largest one should be larger than the average of all them. Since there are $2n+1$ values in $2n^{th}$ row, we divide by $2n+1$.

Stirling's Formula

Stirling gave a brilliant formula to find $n!$.

$$n!\approx n^{n+\frac{1}{2}}\times e^{-n}\times \sqrt{2\pi }$$

If you put these into the factorials of binomial coefficient, you will also get a nice approximation.

Application to Prime Number Theorem

Recall that we want to know how many primes are there up to some number $n$, which we show as $\Pi (n)$. It was found that

$$\Pi (n)\approx \frac{n}{\log n}$$

We will show a weak form of this theorem, by showing:

$$\frac{1}{2}\frac{n}{\log n}\le \Pi (n)\le 2\frac{n}{\log n}$$

so we can show this up to a factor of two. The key idea of the proof is to look at $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ and look at primes dividing it. First we will find the upper-bound.

Suppose $n<p<2n$. Then $p$ divides $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ exactly once. This is because the expression is:

$$\frac{2n!}{n!n!}$$

and $p$ appears only once in the numerator. Now lets look at the product of primes between $n$ and $2n$:

$$\prod _{n<p<2n}p\le \left(\genfrac{}{}{0ex}{}{2n}{n}\right)\le 2^{2n}$$

How could we say that this is less than $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$? Well because any prime in between could only divide that binomial coefficient once, and since all those primes are in the numerator then the product itself can divide that by once. As such, the coefficient must be at least larger than the product of primes itself. We also know that the coefficient there is less than $2^{2n}$ from a similar result.

Now lets take the logarithm of that inequality:

$$\sum _{n<p<2n}\log p\le \log 2^{2n}=2n\log 2$$

Also notice that

$$\sum _{n<p<2n}\log p\ge \log n\times \text{\# primes in [n,2n]}$$

because the actual sum has # primes in $[n,2n]$ terms in it but $\log p$ for any prime there is larger than $\log n$. Then,

$$\text{\# primes in [n,2n]}\le 2\log 2\frac{n}{n}\approx \log 2\frac{2n}{\log 2n}$$

Using this estimate, you can find $[0,n]$ by repeatedly finding $[n/2,n]$, and then $[n/4,n/2]$ and then $[n/8.n/4]$ and so on... We skip that technical detail. The result of this is going to be that # primes $\le n$ is bounded by about $2n/\log n$. You can make that 2 factor a bit smaller if you work really hard.

Now we will find the lower-bound. First we notice:

$$\prod _{p^k\le 2n}p\ge \left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

To show this, we must count # times $p$ divides $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ and we know how to do this:

$$\left[\frac{2n}{p}\right]-\left[\frac{n}{p}\right]-\left[\frac{n}{p}\right]$$

$$\left[\frac{2n}{p^2}\right]-\left[\frac{n}{p^2}\right]-\left[\frac{n}{p^2}\right]$$