Number Theory

Number theory is a branch of pure mathematics that studies the properties and relationships of integers. It is one of the oldest and most abstract areas of mathematics (so no need to be panic when there's something incomprehensible), yet it has significant applications in modern fields like cryptography, computer science, and coding theory.

Part 1: Divisibility and GCD

Definition: the ability of being completely divided without any reminder. (整除)

Explain: there are $a$ apples, which need to be given to $b$ people. As result, everyone has the same number of apples and no apple left.

Examples: 4 % 2 = 0

• There is no remainder on division
• Notation $b | a$
• $b$ is $a$ divisor/factor of $a$
• $a$ is divisible by $b$

Division Algorithm

In mathematics, when division is "not exact" or "doesn't divide evenly," it means that in integer division, the division operation does not result in a whole number; instead, there is a non-zero remainder. Well, if the integer cannot be completely divided, and the result seems like this:

Or in another way:

Where:

• $d_0$ is the dividend, the number that is being divided.
• $d$ is the divisor, the number by which the dividend is divided.
• $q$ is the quotient, which is an integer;
• $r$ is the remainder, and it satisfies $0 \leq r < b$;

If the purpose is to calculate the reminder of $a$ being divided by $b$, then:

Greatest Common Divisor

Greatest Common Divisor (GCD): The greatest common divisor of $a$ and $b$, i.e., $gcd(a, b)$, is the largest integer that divides both $a$ and $b$.

Euclidean Algorithm

The Euclidean algorithm works by repeatedly applying the relation:

The process continues until the remainder becomes 0, at which point the GCD is the last non-zero remainder.

In detail:

Until meet the 0:

Part 2: Modular Arithmetic

The modulus

Definition: If $a$ is an integer and $b$ is a positive integer, we define $a \mod b$ to be the remainder when $a$ is divided by $b$; the integer $b$ is called the modulus.

Thus, for any integer a:

Congruent modulo

Definition: Two integers $a$ and $b$ are said to be congruent modulo $n$ if $(a \mod n) = (b \mod n)$, which can be written as:

• $≡$: This symbol represents congruence. It indicates that the two values are equivalent in terms of their remainders when divided by $n$.
• $(\mod n)$: This notation means "modulo $n$." It specifies the modulus, which is the divisor $n$.

Note 1: if $a ≡ 0 (\mod n)$, then $n ｜ a$.

Note 2: if $gcd(a, n) = 1$, $a \cdot x ≡ a \cdot y (\mod n)$, then $x ≡ y (\mod n)$

Modular Inverse

In modular arithmetic, instead of working with division (which can be problematic in modular systems), we use multiplication to "undo" the effect of a number. The modular inverse of $a$ modulo $n$ is a number $x$ such that:

There exists $a$ modular inverse for $a$ mod $b$ if $a$ is relatively prime to $b$

Arithmetic Modulo 8

Ever unit in this table represents $(x + y) \mod 8$, such as in $(1,1)$, $(1+1) \mod 8 = 2$.

Multiplication Modulo 8

Ever unit in this table represents $(x \cdot y) \mod 8$, such as in $(1,1)$, $(1 \cdot 1) \mod 8 = 1$.

Additive and Multiplicative Inverse Modulo 8

Column $w$: These are the elements (integers) from 0 to 7, which are taken modulo 8.

Column $-w$ : These represent the additive inverses modulo 8. For each number $w$, its additive inverse is the number that, when added to $w$, results in 0 modulo 8. For example: $1 + 7 = 8 ≡ 0 \mod 8$, so the additive inverse of 1 is 7.

Column $w^{-1}$ : These represent the multiplicative inverses modulo 8. The multiplicative inverse of a number $w$ is the number $x$ such that $w \cdot x ≡ 1 \mod 8$. For example: The multiplicative inverse of 1 is 1, as $1 \cdot 1 = 1 \mod 8.$

Bezout's Identity

For any two integers $a$ and $b$, there exist integers $x$ and $y$ such that:

Part 3: Prime Number, Fermat’s Theorem and Euler’s Theorem

Prime Number

Prime numbers only have divisors of 1 and itself.

Composite number has at least one divisor other than 1 and itself

The fundamental theorem of arithmetic: Any integer $a , a > 1$ can be factored in a unique way as: $a = p_1^{a_1} \cdot p_2^{a_2} \cdot \text{...} \cdot p_t^{a_t}$ where $p_1 < p_2 < \text{...} < p_t$ are prime numbers and where each $a_i$ is a positive integer. For example: $24 = 2 \cdot 2 \cdot 2 \cdot 3 = 2^{3} \cdot 3^{1}$

Fermat's Theorem

If $p$ is prime and $a$ is a positive integer not divisible by $p$ then:

Euler’s Totient Function

For a positive integer $n$, Euler's Totient Function $\phi(n)$ is defined as the number of integers from 1 to $n$ that are coprime to $n$. Two integers are coprime if their greatest common divisor (gcd) is 1.

Basic Property:

For a Prime Number$p$: If $p$ is a prime number, then every number from 1 to $p - 1$ is coprime with $p$. Therefore:

It is used in Euler's Theorem, which generalizes Fermat's Little Theorem. For any integer $a$ and $n$ where $a$ is coprime to $n$:

General Formula:

The general formula for Euler's Totient Function $\phi(n)$, where $n$ is expressed as a product of distinct prime factors, is given by:

where $n$ can be expressed as:

and $p_1, p_2, \ldots, p_m$ are distinct prime numbers.

If $n = p^{k}$ ($p$ is prime), then $\phi(n) = p^{k} - p^{k-1}$

Part 4: Efficient Modulo Operation for Large Numbers

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that provides a method for solving systems of simultaneous congruences with pairwise coprime moduli. It ensures that there is a unique solution to such systems, and this solution is congruent modulo the product of the moduli.

Theorem

Let $n_1, n_2, \ldots, n_k$ be pairwise coprime positive integers, and let $a_1, a_2, \ldots, a_k$ be integers. Then there exists a unique integer $x$ modulo $N = n_1 \cdot n_2 \cdots n_k$ such that: