Elementary Number Theory

数論初級

Elementary (Undergraduate 1st–2nd year)

日本語版

About This Chapter

This chapter focuses on congruences (modular arithmetic). We cover Fermat's little theorem, Euler's theorem, the Chinese Remainder Theorem, and other classical, fundamental theorems of number theory. These form the mathematical foundation of modern cryptography (e.g., RSA).

Prerequisites

  • Introductory-level content (divisors, multiples, primes, the Euclidean algorithm)
  • Basic proof reading and writing

Table of Contents

1. Basics of Congruences

Definition and fundamental properties of congruence.

  • Definition: $a \equiv b \pmod{n}$
  • Basic properties of congruence
  • Residue classes and $\mathbb{Z}/n\mathbb{Z}$

2. Arithmetic of Congruences

The four operations and inverses in modular arithmetic.

  • Addition, subtraction, multiplication
  • Existence of multiplicative inverses
  • Solving linear congruences

3. Fermat's Little Theorem

A fundamental theorem for congruences modulo a prime.

  • Statement and proof
  • Application to computing inverses
  • The Fermat primality test

4. Euler's Theorem

A generalization of Fermat's little theorem.

  • Euler's $\varphi$ function
  • Euler's theorem
  • Computing $\varphi(n)$

5. Chinese Remainder Theorem

Solving systems of simultaneous congruences.

  • Statement of the theorem
  • Constructive proof
  • Computational algorithm

6. Primitive Roots

Generators of $(\mathbb{Z}/n\mathbb{Z})^*$.

  • Definition of order
  • Existence conditions for primitive roots
  • Number of primitive roots

7. Applications to Cryptography

The mathematical foundations of RSA.

  • The concept of public-key cryptography
  • How RSA works
  • Basis of security

Appendix: Diophantine Equations

A systematic treatment of Diophantine equations.

  • Linear Diophantine equations via congruences
  • Complete classification of Pythagorean triples
  • Sums of two squares, Pell's equation

Appendix: Hamming Numbers

A systematic account of Hamming numbers (5-smooth numbers).

  • Definition and basic properties
  • Dijkstra's 3-way merge algorithm
  • Applications to FFT and music theory

Appendix: Taxicab Numbers

The number 1729, made famous by Ramanujan.

  • Definition and known values of Ta(n)
  • Connection to Carmichael numbers
  • Waring's problem

Appendix: Sieve of Eratosthenes

An algorithm for efficiently listing all primes up to N.

  • Algorithm and the $p^2$ optimization
  • Complexity $O(N \log \log N)$
  • Segmented sieve and linear sieve

Appendix: Collatz Conjecture

The 3n+1 problem — an unsolved problem in mathematics.

  • The Collatz map and orbits
  • Stopping time and the Collatz tree
  • Terence Tao's partial results

Appendix: Infinitude of Primes (Analytic Proof)

An analytic proof via prime factorization and logarithms.

  • Deriving a lower bound for $\pi(x)$
  • Proof that $\pi(x) \to \infty$
  • Connections to the PNT and the Riemann Hypothesis

Appendix: Rule of 72

A handy approximation for compound interest.

  • Mathematical derivation and error analysis
  • Comparison of 69.3 / 70 / 72
  • Applications to finance and population growth

8. Exercises

Practice problems to deepen understanding.

  • Congruence calculations
  • Applications of theorems
  • Proof problems

Key Theorems

Fermat's Little Theorem

Let $p$ be a prime and $a$ an integer coprime to $p$. Then

$$a^{p-1} \equiv 1 \pmod{p}$$

Euler's Theorem

Let $n$ be a positive integer and $a$ an integer coprime to $n$. Then

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

where $\varphi(n)$ is the number of integers from $1$ to $n$ that are coprime to $n$.

Chinese Remainder Theorem

If $m_1, m_2, \ldots, m_k$ are pairwise coprime, then the system of congruences

$$x \equiv a_i \pmod{m_i} \quad (i = 1, 2, \ldots, k)$$

has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

Applications Accessible at This Level

RSA Cryptography

The backbone of modern Internet security. Two large primes $p, q$ are chosen; their product $n = pq$ is made public while $\varphi(n) = (p-1)(q-1)$ is kept secret. By Euler's theorem, integers $e, d$ satisfying $m^{ed} \equiv m \pmod{n}$ are used for encryption and decryption. The security relies on the difficulty of factoring large integers.

Pseudo-Random Number Generation

The linear congruential method $x_{n+1} = ax_n + c \pmod{m}$ is the most basic pseudo-random number generator. Number-theoretic conditions on the parameters ($a, c, m$) are required, and the concept of primitive roots also plays a role.

Hash Functions

In hash tables, a common approach is to use the remainder of a key divided by a prime $p$ as the index. Using a prime reduces collisions (different keys landing in the same slot), thanks to the "hard-to-divide" nature of primes.

Primality Testing

The Fermat test, based on Fermat's little theorem: if $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ is composite. However, Carmichael numbers are exceptions, making the test incomplete. The Miller–Rabin test is a refinement.

Study Tips

  • Get comfortable with congruences: understand how they differ from ordinary equations (especially regarding division)
  • Euler's $\varphi$ function: grasp its connection to prime factorization
  • Connection to group theory: be aware that $(\mathbb{Z}/n\mathbb{Z})^*$ forms a multiplicative group
  • Keep applications in mind: experience the practical power of the theory through RSA cryptography