Erdos' proof

Erdos proved that there are infinitely many primes by counting numbers of the form $rs^2$, $r$ squarefree. Every number can be put in this form - suppose there were $k$ primes, there is fewer than $2^k \sqrt{N}$ numbers of this form below $N$. If you make $N$ big enough this is a contradiction, so there has to be infinitely many primes!

Straight from the book imo.


I made a mistake in an earlier blog post. I said that a polynomial $p(x)$ of degree $d$ has at most $d$ roots. This is not wrong but it isn't really true either. It holds in an integral domain (i.e. a ring with no zero divisors). If you do have zero divisors then a polynomial can have 'more' roots than it should.

I wrote a pari/gp script to search for some interesting polynomials which have moreroots mod something than their degree:

testpolymod(p,x,m) = {if(lift(Mod(subst(p,variable(p),x),m))==0,1,0)}
countrootsmod(p,m) = sum(x=0, m-1, testpolymod(p,x,m))
randompoly() = random(10)*x^4 + random(10)*x^3 + random(10)*x^2 + random(10)*x + random(10)
randomirrpoly() = {my(p);until(polisirreducible(p),p=randompoly());p}

? p(x) = (x-2)*(x-3)*(x-5)
? countrootsmod(p,6)
%39 = 4

? countrootsmod(p,2*3*5)
%41 = 12

? countrootsmod(4*x^3 + 7*x^2 + 5, 8)
%50 = 4
? countrootsmod(6*x^3 + 3*x + 6, 15)
%79 = 6
? countrootsmod(9*x^3 + x^2 + 2*x + 6, 6)
%84 = 4

? countrootsmod(7*x^4 + x^3 + 8*x^2 + 4*x + 8, 8)
%110 = 5
? countrootsmod(7*x^4 + x^3 + 8*x^2 + 4*x + 8, 14)
%111 = 6

? countrootsmod(4*x^4 + 4*x^3 + 8*x^2 + 8*x + 4, 28)
%171 = 8

Wikipedia math

I saw an interesting result that sounded strong to me on wikipedia <>. Every ideal is generated by 2 or fewer elements.

They point to some deep theorems so I thought that result was out of my range. Turns out it's a simple consequence of chinese remainder theorem!

There is a proof in Frolich & Taylor page 45. It makes use of the valuation on ideals.


If $\mathfrak p$ is a prime ideal then there is a valuation/place $v_{\mathfrak p}$ defined on ideals. To define it we can use the theorem about unique factorization of ideals. Factor the ideal $I$ and define $v_{\mathfrak p}(I)$ as a function of the index $\mathfrak p$ occurs in.

This will also be useful and important for producing the local rings which I think are an important tool in alg. number theory. I'm having some trouble getting there though.


I read a nice interview of Ben Green about his mathematics <>. It was also very interesting to read about polymath on <>.

Integral basis

I think Dirichlet first showed this. The existence of an integral basis for the ring of integers of a number field. It's a very fundamental fact about these things, but tricky to prove. The idea is to show that the integers are contained inside a f.g. $\mathbb Z$-module. To do that we use the "dual basis" we get from a nondegenerate bilinear form.

Let a number field $K$ have basis $\bar e$ so that $K = \mathbb Q(\bar e)$. By clearing denominators we can assume the basis consists of algebraic integers: each $e_i \in \mathcal O_K$.

The trace form is non-degenerate so produce a dual basis $\bar e^*$ with the property $\text{tr}(e_i e_j^*) = \delta_{i,j}$. The dual basis elements may not be algebraic integers! Think of them as algebraic rationals.

Take some algebraic integer $\beta \in \mathcal O_K$ and express it in terms of the bases $\beta = \sum b_i e_i^*$. The trace of two algebraic integers is a rational integer, so $\text{tr}(\beta e_i) = b_i$ is an integer. This shows every algebraic integer can be expressed as a $\mathbb Z$ combination of the basis $\bar e^*$.

Now given that $R$ is a PID: whenever an $R$-module $A$ is contained inside a f.g. $R$-module $B$ it must also be f.g. To prove this just take generators for the ideals $A \cap R(e_i)$.