# Problem Sets ## Problem Set 1. Foundations 1. Prove that the sum of two even integers is even. 2. Prove that the product of two odd integers is odd. 3. Prove that if $n^2$ is even, then $n$ is even. 4. Prove by induction that $$ 1+2+\cdots+n=\frac{n(n+1)}{2}. $$ 5. Prove by induction that $$ 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. $$ 6. Prove that every integer $n\ge2$ has a prime divisor. 7. Prove that there are infinitely many primes. 8. Show that if $a\mid b$ and $b\mid c$, then $a\mid c$. 9. Show that if $a\mid b$ and $a\mid c$, then $$ a\mid bx+cy $$ for all integers $x,y$. 10. Prove that $\gcd(a,b)=\gcd(b,a-b)$. ## Problem Set 2. Divisibility and Euclidean Algorithm 1. Use the Euclidean algorithm to compute $$ \gcd(252,198). $$ 2. Find integers $x,y$ such that $$ 252x+198y=\gcd(252,198). $$ 3. Prove Bézout’s identity using the Euclidean algorithm. 4. Prove Euclid’s lemma: if $p$ is prime and $p\mid ab$, then $p\mid a$ or $p\mid b$. 5. Prove the uniqueness part of the fundamental theorem of arithmetic. 6. Find the prime factorization of $$ 5040. $$ 7. Compute $$ \gcd(840,1008) $$ from prime factorizations. 8. Compute $$ \operatorname{lcm}(840,1008). $$ 9. Prove that $$ \gcd(a,b)\operatorname{lcm}(a,b)=|ab|. $$ 10. Show that if $\gcd(a,b)=1$ and $a\mid bc$, then $a\mid c$. ## Problem Set 3. Congruences 1. Prove that congruence modulo $n$ is an equivalence relation. 2. Solve $$ 3x\equiv 7\pmod{11}. $$ 3. Solve $$ 12x\equiv 8\pmod{20}. $$ 4. Find the inverse of $17$ modulo $43$. 5. Prove that $a$ has an inverse modulo $n$ if and only if $$ \gcd(a,n)=1. $$ 6. Solve the system $$ x\equiv 2\pmod 3, $$ $$ x\equiv 3\pmod 5, $$ $$ x\equiv 2\pmod 7. $$ 7. Prove the Chinese remainder theorem for two coprime moduli. 8. Compute $$ 2^{100}\pmod{13}. $$ 9. Prove Fermat’s little theorem. 10. Use Euler’s theorem to compute $$ 7^{222}\pmod{40}. $$ ## Problem Set 4. Arithmetic Functions 1. Compute $\varphi(n)$ for $$ n=12,18,36,100. $$ 2. Prove that if $p$ is prime, then $$ \varphi(p^k)=p^k-p^{k-1}. $$ 3. Prove that $\varphi$ is multiplicative. 4. Compute $\mu(n)$ for $1\le n\le 20$. 5. Prove that $$ \sum_{d\mid n}\mu(d)= \begin{cases} 1 & n=1,\\ 0 & n>1. \end{cases} $$ 6. Prove the Möbius inversion formula. 7. Compute $$ \sum_{d\mid 60}\varphi(d). $$ 8. Prove that $$ \sum_{d\mid n}\varphi(d)=n. $$ 9. Show that the divisor-counting function $\tau(n)$ is multiplicative. 10. Find a formula for $\tau(n)$ from the prime factorization of $n$. ## Problem Set 5. Diophantine Equations 1. Determine whether $$ 35x+21y=14 $$ has integer solutions. If so, find all of them. 2. Solve $$ 15x+28y=1. $$ 3. Classify all primitive Pythagorean triples. 4. Find all primitive Pythagorean triples with hypotenuse less than $50$. 5. Solve $$ x^2-2y^2=1 $$ for the first five positive solutions. 6. Prove that no integer solution exists for $$ x^2\equiv 3\pmod 4. $$ 7. Prove that if $p\equiv 3\pmod 4$, then $p$ cannot divide a sum of two squares unless it divides both terms. 8. Find all integer solutions to $$ x^2-y^2=45. $$ 9. Prove that there are no positive integers $x,y$ such that $$ x^2=2y^2. $$ 10. Find all rational points on $$ x^2+y^2=1. $$ ## Problem Set 6. Quadratic Residues 1. List all quadratic residues modulo $11$. 2. Compute $$ \left(\frac{2}{7}\right),\quad \left(\frac{3}{11}\right),\quad \left(\frac{5}{13}\right). $$ 3. Prove Euler’s criterion. 4. Use quadratic reciprocity to compute $$ \left(\frac{37}{101}\right). $$ 5. Determine whether $$ x^2\equiv 10\pmod{13} $$ has a solution. 6. Prove the first supplementary law: $$ \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}. $$ 7. Prove the second supplementary law for $\left(\frac{2}{p}\right)$. 8. Show that the Jacobi symbol being $1$ does not imply solvability. 9. Compute $$ \left(\frac{1001}{9907}\right). $$ 10. Find all solutions of $$ x^2\equiv 1\pmod{35}. $$ ## Problem Set 7. Analytic Number Theory 1. Prove that the harmonic series diverges. 2. Prove that $$ \sum_p \frac1p $$ diverges. 3. Show that the Euler product for $\zeta(s)$ converges absolutely when $\operatorname{Re}(s)>1$. 4. Derive the Euler product formula $$ \zeta(s)=\prod_p(1-p^{-s})^{-1}. $$ 5. Prove Abel summation. 6. Estimate $$ \sum_{n\le x}\log n. $$ 7. Show that $$ \vartheta(x)\le \psi(x). $$ 8. State the prime number theorem in terms of $\pi(x)$, $\vartheta(x)$, and $\psi(x)$. 9. Prove the orthogonality relations for Dirichlet characters modulo $q$. 10. Explain why nonvanishing of $L(1,\chi)$ is central to Dirichlet’s theorem. ## Problem Set 8. Algebraic Number Theory 1. Prove that $\sqrt{2}$ is an algebraic integer. 2. Show that $$ \frac12 $$ is not an algebraic integer. 3. Find the minimal polynomial of $$ \sqrt{2}+\sqrt{3}. $$ 4. Compute the norm and trace of $$ a+b\sqrt{d} $$ over $\mathbb{Q}$. 5. Determine the units in $\mathbb{Z}[i]$. 6. Factor $$ 5 $$ in $\mathbb{Z}[i]$. 7. Show that $\mathbb{Z}[\sqrt{-5}]$ does not have unique factorization. 8. Define a Dedekind domain and give an example. 9. Prove that every nonzero ideal in $\mathbb{Z}$ is principal. 10. Explain how ideals restore unique factorization in rings of integers. ## Problem Set 9. Elliptic Curves and Modular Forms 1. Check whether $$ y^2=x^3-4x $$ is nonsingular. 2. Find the rational points with small integer coordinates on $$ y^2=x^3+x+1. $$ 3. Derive the chord-and-tangent group law geometrically. 4. Compute $P+Q$ for two given points on a Weierstrass curve. 5. Count points on $$ y^2=x^3+x+1 $$ over $\mathbb{F}_5$. 6. State Hasse’s bound. 7. Define a modular form of weight $k$. 8. Explain the difference between modular forms and cusp forms. 9. Define a Hecke operator. 10. State the modularity theorem for elliptic curves over $\mathbb{Q}$. ## Problem Set 10. Computational and Cryptographic Number Theory 1. Implement the Euclidean algorithm. 2. Implement the extended Euclidean algorithm. 3. Implement fast modular exponentiation. 4. Use Miller-Rabin to test whether a given large integer is probably prime. 5. Factor a small composite using Pollard rho. 6. Generate two RSA primes and compute public and private exponents. 7. Prove correctness of RSA encryption and decryption. 8. Implement arithmetic in $\mathbb{F}_p$. 9. Implement point addition on an elliptic curve over $\mathbb{F}_p$. 10. Explain why integer factorization and discrete logarithms are central to public-key cryptography.