Introduction to Number Theory Exhaustive Study Notes

Number Classification and Arithmetic Fundamentals

• Integers and Number Theory: Number theory is the study of integers. The set contains positive integers, negative integers, and zero: $\dots, -3, -2, -1, 0, 1, 2, 3, \dots$. Integers are essentially used for counting whole, indivisible objects.
• Subsets of Integers:
  • Natural Numbers (Counting Numbers): $1, 2, 3, 4, 5, \dots$.
  • Whole Numbers: $0, 1, 2, 3, 4, \dots$.
• Identifying Non-Integers: Any number with a non-zero digit after its decimal point is not an integer. This is because integers must be reachable from zero moving 1 unit at a time. Examples of non-integers include $2.5$, $-82.21$, and $\pi$ ($\approx 3.14159$).
• Arithmetic as Fast Counting:
  • Addition and Subtraction: These operations represent moving forward or backward on the number line. Subtracting an object is conceptually identical to adding its negative counterpart.
  • Multiplication: Defined as repeated addition. For example, $2 \times 4$ is shifting 4 units to the right twice.
  • Exponentiation: Defined as repeated multiplication for whole number exponents. $2^3$ is $2 \cdot 2 \cdot 2 = 8$. Note that $x^0 = 1$ for any non-zero integer.
• Power Integers:
  • Perfect Square: An integer equal to an integer to the second power (e.g., $0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100$).
  • Perfect Cube: An integer equal to an integer to the third power (e.g., $0, 1, 8, 27, 64, 125, 216, 343, 512$).
  • Perfect Power: An integer equal to an integer to a power of at least 2. Examples: $2^5 = 32$, $3^4 = 81$, $6^4 = 1296$, $5^6 = 15625$.

Multiples and Divisibility

• Multiple: The product of a specific integer with any other integer. For any integers $m$ and $n$, their product $mn$ is a multiple of both.
• Divisibility Rule: An integer $m$ is divisible by $n$ if the quotient $\frac{m}{n}$ is an integer. When $n \ne 0$, "m is divisible by n" is logically equivalent to "m is a multiple of n."
• Zero Property: The number $0$ is a multiple of every integer because $0 \cdot n = 0$. Conversely, no integer is divisible by $0$ as the operation is undefined.
• Divisors (Factors): If $n$ is divisible by $d$, $d$ is called a divisor of $n$.
• Transitive Property of Divisibility: If $a$ is a divisor of $b$ and $b$ is a divisor of $c$, then $a$ must be a divisor of $c$. This also implies that if $c$ is a multiple of $b$ and $b$ is a multiple of $a$, then $c$ is a multiple of $a$.
• Transitive Lemma: $\frac{b}{a} \cdot \frac{c}{b} = \frac{c}{a}$. Since $\frac{b}{a}$ and $\frac{c}{b}$ are integers, $\frac{c}{a}$ must be an integer.
• Proper Divisor: A positive divisor of $n$ other than $n$ itself.
• Divisor Search Space: Multiples of a positive integer $n$ only exist at $0$ or values $\ge n$. Therefore, when searching for proper divisors of $m$, only integers between $0$ and $m$ need to be tested.
• Symbolic Notation: $a | b$ denotes "a divides b." $a \nmid b$ denotes "a does not divide b."

Primes, Composites, and GCD/LCM

• Prime Number: A natural number $p > 1$ whose only positive divisors are $1$ and itself. The primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$.
• Composite Number: A natural number $c > 1$ with a positive divisor other than $1$ and $c$. Composites can be written as $c = ab$ where $a, b$ are integers such that $1 < a, b < c$.
• Non-Classification of 1: The number $1$ is neither prime nor composite.
• Sieve of Eratosthenes: A method for identifying primes in a range by circling the smallest unmarked number and crossing out all its subsequent multiples.
• Primality Test: A natural number $n > 1$ is prime if it has no prime divisors less than or equal to $\sqrt{n}$.
• Common Divisors and Multiples:
  • Common Divisor: A divisor shared by all integers in a group.
  • Greatest Common Divisor (GCD/GCF): The largest of the common divisors. Notation: $gcd(a, b)$.
  • Relatively Prime (Coprime): Two integers whose only common positive divisor is $1$ ($gcd(a, b) = 1$).
  • Common Multiple: A multiple shared by all integers in a group.
  • Least Common Multiple (LCM): The smallest positive common multiple. Notation: $lcm[a, b]$.
• Euclidean Algorithm: Based on the fact that for natural numbers $m > n$, $gcd(m, n) = gcd(m - n, n)$.
• Extended Euclidean Algorithm: Uses remainders to find the GCD more efficiently: $gcd(m, n) = gcd(r, n)$, where $r$ is the remainder of $m \div n$.

Prime Factorization Principles

• Fundamental Theorem of Arithmetic: Every positive integer has exactly one unique prime factorization.
• Factor Trees: Visual tools to break a composite number down into a product of primes until only primes remain.
• Constructing GCD and LCM:
  • For LCM: Identify all primes present in any of the factorizations and take the maximum exponent for each.
  • For GCD: Identify primes present in all factorizations and take the minimum exponent for each.
  • Let $a = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$ and $b = p_1^{f_1} p_2^{f_2} \dots p_n^{f_n}$:
  • $gcd(a, b) = p_1^{min(e_1, f_1)} \dots p_n^{min(e_n, f_n)}$.
  • $lcm[a, b] = p_1^{max(e_1, f_1)} \dots p_n^{max(e_n, f_n)}$.
• LCM-GCD Identity: For two natural numbers $m$ and $n$, $mn = gcd(m, n) \cdot lcm[m, n]$. This identity does not extend to groups of three or more integers.
• Scaling Properties:
  • $gcd(ac, bc) = c \cdot gcd(a, b)$.
  • $lcm[ac, bc] = c \cdot lcm[a, b]$.
• Power Exponents: In the prime factorization of a perfect square, every exponent must be even. In a perfect cube, every exponent is a multiple of 3.

Divisor Properties and Formulas

• Counting Divisors: For an integer $n$ with prime factorization $p_1^{e_1} \cdot p_2^{e_2} \dots p_m^{e_m}$, the number of positive divisors $t(n)$ is calculated as:
  • $t(n) = (e_1 + 1)(e_2 + 1) \dots (e_m + 1)$.
• Divisor Count Theorems:
  • A positive integer is a perfect square if and only if its number of divisors $t(n)$ is odd.
  • If $gcd(m, n) = 1$, then $t(mn) = t(m) \cdot t(n)$.
• Product of Divisors: The product of all positive divisors $P_n$ of a natural number $n$ is given by:
  • $P_n = n^{t(n) / 2}$.
• Complementary Counting: To count things matching a condition, it is often simpler to subtract the count of those not matching the condition from the total. (e.g., Total divisors - odd divisors = even divisors).

Specialized Number Classes

• Factorials: The factorial $n!$ is the product of all positive integers $\le n$.
  • Important relation: $(n + 1)! = (n + 1) \cdot n!$.
  • Finding prime exponents in $n!$: To find the highest power of $p$ dividing $n!$, sum the quotients (ignoring remainders) of $\frac{n}{p}$, \frac{n}{p^2}, \frac{n}{p^3}, \dots`.\n- **Perfect, Abundant, and Deficient Numbers**: Let `s(n)$` be the sum of proper divisors of `$n`:\n - **Perfect**: `s(n) = n$` (e.g., `$6, 28, 496`).\n - **Abundant**: `s(n) > n$` (e.g., `$12, 24`).\n - **Deficient**: `s(n) < n$` (e.g., `$8, 44`).\n- **Special Primes**:\n - **Mersenne Primes**: Primes in the form `2^p - 1$`, where `$p` is prime.\n - **Fermat Primes**: Primes in the form `2^{2^n} + 1$`. Examples include `$3, 5, 17, 257, 65537`.\n - **Twin Primes**: Pairs of primes differing by 2 (e.g., `3, 5$`; `$101, 103`).\n- **Palindromes**: Integers that remain the same when digits are reversed (e.g., `121, 3443`).\n\n# Base Number Systems\n\n- **Bundling Principle**: A numeral system groups values into bundles of powers of a base `b`.\n- **Decimal (Base 10)**: Uses digits `0$` to `$9$` and digit bundles based on `$10^k`.\n- **Base b Numerals**: Uses digits `0$` to `$b - 1$`. Bases larger than 10 use letters (e.g., Duodecimal/Base 12 uses `$A=10, B=11$`; Hexadecimal/Base 16 uses `$A \dots F`).\n- **Conversion to Decimal**: Sum the decimal values of the digit bundles: `d_k b^k + \dots + d_1 b^1 + d_0 b^0`.\n- **Conversion from Decimal**: Use repeated division by the base `b$`. The remainders in reverse order (bottom to top) form the base `$b` digits.\n- **Radix Point**: Separates the integer and fractional parts in non-decimal bases. `0.d_1 d_2 d_3_b = d_1 b^{-1} + d_2 b^{-2} + d_3 b^{-3}`.\n- **Multiplication by Base**: Multiplying a base `b$` integer by `$b$` (written as `$10_b`) is equivalent to shifting all digits left and appending a trailing zero.\n\n# Modular Arithmetic and Congruences\n\n- **Modular Definitions**:\n - **Modulus**: A system counting with integers `0, 1, \dots, m - 1`.\n - **Congruence**: `a \equiv b \pmod{m}$` if `$m | (a - b)`.\n - **Residue**: The integer `r$` such that `$n \equiv r \pmod{m}$` where `$0 \le r < m`.\n- **Arithmetic Rules**: If `a_1 \equiv a_2 \pmod{m}$` and `$b_1 \equiv b_2 \pmod{m}`:\n - `a_1 + b_1 \equiv a_2 + b_2 \pmod{m}`.\n - `a_1 \cdot b_1 \equiv a_2 \cdot b_2 \pmod{m}`.\n - `a^n \equiv a_2^n \pmod{m}$` for natural numbers `$n`.\n- **Modular Inverse**: An integer `b^{-1}$` such that `$b \cdot b^{-1} \equiv 1 \pmod{m}$`. It exists if and only if `$gcd(b, m) = 1`. \n- **Linear Congruence**: An equation `ax \equiv b \pmod{m}`.\n - A solution exists if and only if `gcd(a, m) | b`.\n - Simplification: If `ac \equiv bc \pmod{mc}$`, then `$a \equiv b \pmod{m}`.\n - Division rule: `ac \equiv bc \pmod{m} \iff a \equiv b \pmod{\frac{m}{gcd(m, c)}}`.\n- **Systems of Congruences**: Solved by converting modular congruences to parametric equations (e.g., `n \equiv r \pmod{m} \rightarrow n = mk + r`) and substituting into the other congruences.\n\n# Rational Numbers and Divisibility Rules\n\n- **Terms and Conversions**:\n - **Terminating Decimal**: A fraction `\frac{a}{b}$` in lowest terms terminates if `$b$`'s prime factors are only 2 or 5. The number of digits past the decimal is `$max(\text{power of 2, power of 5})`.\n - **Repeating Decimal**: A rational number is a repeating decimal if the denominator has prime factors other than 2 or 5.\n- **Standard Divisibility Rules**:\n - **2, 5, 10**: Depends on the units digit.\n - **4, 25, 100**: Depends on the last two digits.\n - **`2^m, 5^m, 10^m$`**: Depends on the last `$m` digits.\n - **3, 9**: Sum of digits must be divisible by 3 or 9.\n - **11**: Alternating sum of digits must be divisible by 11.\n- **Units Digit Property**: The units digit of a sum, difference, or product is determined solely by the units digits of the operands.\n\n# Advanced Algebraic Tactics\n\n- **Factorization Identities**:\n - `x^2 - y^2 = (x + y)(x - y)` (Difference of Squares).\n - `x^3 - y^3 = (x - y)(x^2 + xy + y^2)` (Difference of Cubes).\n - `x^3 + y^3 = (x + y)(x^2 - xy + y^2)` (Sum of Cubes).\n- **Simon's Favorite Factoring Trick**: Used for equations like `xy + Ax + By = K$`. Adding `$AB$` to both sides enables the factorization `$(x + B)(y + A) = K + AB`.\n- **Place Value Expansion**: A decimal number `ABC$` is expanded as `$100A + 10B + C$$ to allow algebraic manipulation of its digits.
• Parity: The classification of an integer as even or odd (Arithmetic Modulo 2).