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.