•  Number Theory and Cryptography – Math UN3020, for undergraduate students at Columbia University.
• mcgil MATH 346 Number Theory
• ucalgary MATH 641.01 – Algebraic Number Theory
• UCB Math613-Winter2023

The key result is the existence of primitive roots modulo a prime. This theorem was used by mathematicians before Gauss but he was the first to give a proof.The existence of primitive roots is equivalent to the fact that $U(\mathbb{Z} / p \mathbb{Z})$ is a cyclic group when $p$ is a prime. Using this fact we shall find an explicit description of the group $U(\mathbb{Z} / n \mathbb{Z})$ for arbitrary $n$.

The polynomial method is a relatively new algebraic tool (and philosophy) that has over the past ten years enabled researchers to settle several long-standing open problems arising from diverse areas such as Combinatorial and Finite Geometry, Additive Combinatorics, Number theory, and so on. I shall in this note, provide an introduction to what this method is all about, and as an attempt to expound on this new technique, go over four problems in which substantial progress happened from a prior state of virtual hopelessness. In particular, we shall consider the following:

1. Dvir’s solution of the Finite Kakeya Conjecture,
2. Guth-Katz’ solution of the Joints’ Problem,
3. The Cap-set problem and the work of Ellenberg-Gisjwijt, and
4. A function field analogue of Sárközy’s theorem, due to Green.

## 下面是一些经典的The Structure of $U(\mathbb{Z} / n \mathbb{Z})$题目

Problem 1. Show that the sum of all the primitive roots modulo $p$ is congruent to $\mu(p-1)$ modulo $p$.

Key techniques or knowledge

understanding of Möbius function.

Problem 2. Prove that $1^k+2^k+\cdots+(p-1)^k \equiv 0(p)$ if $p-1 \nmid k$ and $-1(p)$ if $p-1 \mid k$.

Key techniques or knowledge

Guass’s lemma, Fermat’s little theorem.

Problem 3. Use the existence of a primitive root to give another proof of Wilson’s theorem $(p-1) ! \equiv-1(p)$.

Key techniques or knowledge

Wilson’s theorem. This involves Euler’s theorem

Problem 4. Let $G$ be a finite cyclic group and $g \in G$ a generator. Show that all the other generators are of the form $g^k$, where $(k, n)=1, n$ being the order of $G$.

Key techniques or knowledge

applying Euclid’s algorithm

Problem 5. Let $A$ be a finite abelian group and $a, b \in A$ elements of order $m$ and $n$, respectively. If $(m, n)=1$, prove that $a b$ has order $m n$.

Key techniques or knowledge

the property of order of an element

Problem 6. Let $K$ be a field and $G \subseteq K^*$ a finite subgroup of the multiplicative group of $K$. Extend the arguments used in the proof of Theorem 1 to show that $G$ is cyclic.

Key techniques or knowledge

the structure theorem for finitely generated abelian groups.

Problem 7. Calculate the solutions to $x^3 \equiv 1$ (19) and $x^4 \equiv 1$ (17).
Problem 8. Use the fact that 2 is a primitive root modulo 29 to find the seven solutions to $x^7 \equiv 1(29)$.
Problem 9. Solve the congruence $1+x+x^2+\cdots+x^6 \equiv 0$ (29).

Key techniques or knowledge

the Chinese remainder theorem.

BS equation代写