Number Theory

Exercise 1.1   (Erdos)
If $A\subset\{1,\ldots,2n\}$ with $\vert A\vert=n+1$, show two elements of $A$ are relatively prime.

Exercise 1.2   (Erdos)
In the above situation; show some element of $A$ divides another. Hint. Pigeon hole principle.

Theorem 1.3   (Dirichlet's theorem on simultaneous Diophantine approximation)
For all $(\alpha_1,\ldots,\alpha_n)\in\mathbb{R}^n$ and $\epsilon>0$ there exist $p_1,\ldots,p_n,q\in\mathbb{Z}$ such that

$$1\leq q\leq\left(\frac{1}{\epsilon}\right)^n$$ and $$\left\vert\alpha_i-\frac{p_i}{q} \right\vert<\frac{\epsilon}{q}$$ for all $$i.$$

The proof is a striking application of the Pigeon Hole Principle.

Exercise 1.4   (Erdos)
Consider a collection of arithmetic progressions $A_1,\ldots,A_k$ for $k\geq2$, with $\mathbb{N}=A_1\cup\ldots\cup A_k$ and $A_i\cap A_j=\emptyset$. Show it is not possible for all the increments to be distinct. (In fact the largest increment must occur at least twice).