Fiche de révision : Number Theory Fundamentals

📋 Course Outline

1. Division Algorithm
2. Divisibility and Linear Combinations
3. Quotients and Remainders
4. Modular Arithmetic
5. Prime Factorization
6. Prime Numbers and Theorems
7. Greatest Common Divisor
8. Euclid's Algorithm
9. Extended Euclidean Algorithm
10. Multiplicative Inverse

📖 1. Division Algorithm

🔑 Key Concepts & Definitions

• Division Algorithm:
  The theorem stating that for any integer $a$ and positive integer $d$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:
  $a = dq + r \quad \text{with} \quad 0 \leq r < d$
  This guarantees the existence and uniqueness of the quotient and remainder when dividing integers.

• Quotients and Remainders:
  The results of division, where the quotient $q$ is the integer part of the division, and the remainder $r$ is what is left over, satisfying $0 \leq r < d$.

• Integer Division Definitions:
  In the context of the Division Algorithm, the quotient $q$ and remainder $r$ are defined such that:
  $a = dq + r$ with the specified bounds on $r$. The quotient and remainder are uniquely determined by this relation.

• Procedural Version of the Division Algorithm:
  A step-by-step method to compute $q$ and $r$ for given integers $a$ and positive integer $d$. It involves iterative subtraction or division steps to find the unique $q$ and $r$ satisfying the relation, ensuring $0 \leq r < d$.

📝 Essential Points

• The Division Algorithm applies to all integers $a$ and positive integers $d$, ensuring the existence of a unique pair $(q, r)$.
• The quotient $q$ and the remainder $r$ satisfy the key relation $a = dq + r$.
• The remainder $r$ always lies within the range $0 \leq r < d$.
• The procedural version involves repeatedly subtracting or dividing to find the quotient and remainder, with specific steps depending on whether $a$ is positive or negative.
• The theorem guarantees the existence of such $q$ and $r$, with uniqueness proven separately.

💡 Key Takeaway

The Division Algorithm ensures that every integer division produces a unique quotient and remainder, with the remainder always falling within a specific range, providing a fundamental foundation for understanding division in integers.

📖 2. Divisibility and Linear Combinations

🔑 Key Concepts & Definitions

Divides (denoted as " | "):
Let and be two integers. Then, divides (denoted as ) if and only if there exists an integer such that . If does not divide , it is denoted as .

Multiple:
If an integer divides another, then the latter is called a multiple of the former.

Factor or Divisor:
If a number divides another, the first number is called a factor or divisor of the second.

Linear combination:
A sum of multiples of integers, expressed as , where and are integers. For example, and are linear combinations of and.

Divisibility and linear combinations (Theorem 9.1.1):
If and , then for any integers and , and any linear combination of and is divisible by . Conversely, if a number divides both and , then it divides any linear combination of these numbers.

📝 Essential Points

• An integer divides another if there exists an integer multiple, establishing a divisibility relation.
• The concept of linear combinations involves sums of multiples of integers, with the coefficients being integers.
• Theorem 9.1.1 states that if divides both and , then it divides any linear combination of and . Conversely, if a number divides both and , it divides their linear combinations.
• The division process involves finding quotients and remainders, which are unique as per the Division Algorithm.
• The division operation's interpretation depends on the properties of integers, with the quotient and remainder satisfying specific bounds.
• The concept of divisibility extends to properties of linear combinations, which are fundamental in number theory.

💡 Key Takeaway

Divisibility relates to the existence of integer multiples, and linear combinations serve as a tool to express and analyze divisibility properties, with theorems linking the divisibility of individual numbers to that of their linear combinations.

📖 3. Quotients and Remainders

🔑 Key Concepts & Definitions

Quotients and Remainders: The unique pair of integers resulting from division, where the quotient is the integer part of the division, and the remainder is the leftover part that is less than the divisor.

Division Algorithm: The theorem that guarantees, for any integer $a$ and positive integer $b$, the existence and uniqueness of integers $q$ and $r$ such that $a = bq + r$, with $0 \leq r < b$. This theorem states that the quotient $q$ and the remainder $r$ are uniquely determined by the division.

📝 Essential Points

• When dividing an integer $a$ by a positive integer $b$, the division results in a quotient $q$ and a remainder $r$.
• The quotient $q$ and the remainder $r$ satisfy the relation $a = bq + r$.
• The remainder $r$ always lies within the range $0 \leq r < b$.
• The Division Algorithm asserts that for each division, the pair $(q, r)$ is unique.
• The division process is fundamental in number theory and is used to justify and prove properties related to divisibility and linear combinations.

💡 Key Takeaway

The division of integers produces a unique quotient and remainder, with the division theorem ensuring their existence and uniqueness, forming a foundational concept in understanding divisibility and number properties.

📖 4. Modular Arithmetic

🔑 Key Concepts & Definitions

Modular Arithmetic: Arithmetic performed with respect to a modulus, involving congruence relations. It considers numbers within a set where operations are defined modulo a fixed integer, ensuring results stay within a specific range.

Congruence: An equivalence relation between two integers indicating they have the same remainder when divided by a given modulus. It is denoted as $a \equiv b \ (\text{mod} \ m)$.

Properties of modular arithmetic: Rules and properties used to simplify calculations in modular systems, including the fact that addition, subtraction, and multiplication are well-defined and preserve congruence relations within the modulus.

📝 Essential Points

• Congruence relation $a \equiv b \ (\text{mod} \ m)$ holds if and only if $m$ divides $a - b$.
• Two integers are congruent modulo $m$ if they leave the same remainder when divided by $m$.
• The equivalence classes of integers under congruence modulo $m$ are represented by their remainders, ranging from 0 to $m-1$.
• Arithmetic operations (addition, subtraction, multiplication) are compatible with congruence: if $a \equiv b \ (\text{mod} \ m)$ and $c \equiv d \ (\text{mod} \ m)$, then:
  • $a + c \equiv b + d \ (\text{mod} \ m)$
  • $a - c \equiv b - d \ (\text{mod} \ m)$
  • $a \times c \equiv b \times d \ (\text{mod} \ m)$
• These properties allow for the simplification of calculations involving large numbers by reducing intermediate results modulo $m$.

💡 Key Takeaway

Modular arithmetic uses congruence relations to perform and simplify calculations within a fixed range, making it fundamental for applications like cryptography and computer science.

📖 5. Prime Factorization

🔑 Key Concepts & Definitions

Prime Number: An integer greater than 1 whose only factors are 1 and itself.

Composite Number: A positive integer greater than 1 that has factors other than 1 and itself.

Prime Factorization: The expression of a positive integer as a product of prime numbers, written in nondecreasing order, with primes raised to their multiplicities (exponential notation).
Theorem 9.3.1 (Fundamental Theorem of Arithmetic): Every positive integer greater than 1 can be expressed uniquely as a product of primes, up to ordering.

Prime Factors: The prime numbers in the prime factorization of a number.

Multiplicity: The number of times a particular prime appears in the prime factorization of a number.

📝 Essential Points

• Every integer greater than 1 is either prime or composite.
• The prime factorization of a number is unique when written with primes in nondecreasing order.
• Prime factorization can be expressed using exponential notation, where each prime factor is raised to its multiplicity.
• Prime factors are the building blocks of all integers, central to number theory.
• Prime factorization is used to find the greatest common divisor (GCD) and least common multiple (LCM) of two integers.
• To find GCD and LCM from prime factorizations, compare exponents of common primes:
  • GCD uses the smaller exponents.
  • LCM uses the larger exponents.

💡 Key Takeaway

Prime factorization provides a unique and fundamental way to express integers as products of primes, enabling the calculation of divisibility properties, GCD, and LCM, which are essential in number theory and applications like cryptography.

📖 6. Prime Numbers and Theorems

🔑 Key Concepts & Definitions

Prime Numbers:
Numbers greater than 1 that have no divisors other than 1 and themselves. They are the fundamental building blocks of integers, as every integer greater than 1 can be expressed as a product of primes.

Theorem (Euclid's Theorem):
While not explicitly stated in the source, the importance of prime numbers and their distribution is highlighted through the study of prime numbers and related theorems, such as Euclid's theorem, which concerns the properties and distribution of primes.

Prime Factorization:
Expressing a number as a product of prime numbers, uniquely up to the order of factors, as established by the Fundamental Theorem of Arithmetic.

Fundamental Theorem of Arithmetic:
States that every positive integer greater than 1 can be expressed uniquely as a product of prime numbers, with the primes listed in nondecreasing order.

📝 Essential Points

• Prime numbers are greater than 1 and only divisible by 1 and themselves.
• Every integer greater than 1 has a unique prime factorization, which is central to number theory.
• Prime factorization can be written using exponential notation, where each prime factor is raised to its multiplicity.
• The prime factorization of a number is used to determine the greatest common divisor (GCD) and least common multiple (LCM) of two integers.
• The GCD of two numbers is the largest positive integer dividing both, found by taking the minimum exponents of common primes in their factorizations.
• The LCM of two numbers is the smallest positive integer divisible by both, found by taking the maximum exponents of primes in their factorizations.

💡 Key Takeaway

Prime numbers are the fundamental building blocks of integers, and their properties underpin key theorems like the Fundamental Theorem of Arithmetic, which guarantees the unique prime factorization of every integer greater than 1.

📖 7. Greatest Common Divisor

🔑 Key Concepts & Definitions

Greatest Common Divisor (GCD): The largest positive integer dividing two or more integers without remainder. It is the greatest number that is a factor of each of the given integers.

Euclid's Algorithm: An efficient method to compute the GCD of two integers using division. Although the detailed process is not explicitly defined in the source, it is referenced as an effective approach for finding the GCD.

📝 Essential Points

• The GCD of two integers is the largest positive integer that divides both without leaving a remainder.
• The GCD can be determined through prime factorizations by identifying the common prime factors with the smallest exponents.
• The prime factorization approach involves expressing each number as a product of primes and then taking the product of the common primes raised to the minimum exponents.
• The GCD is used to simplify fractions, find common divisors, and solve divisibility problems.
• The source emphasizes that the GCD is a fundamental concept in number theory and is related to the divisibility of integers.

💡 Key Takeaway

The greatest common divisor is the largest shared factor of two or more integers, and it can be efficiently computed using methods like Euclid's Algorithm or prime factorization techniques.

📖 8. Euclid's Algorithm

🔑 Key Concepts & Definitions

Euclid's Algorithm: An iterative process to find the greatest common divisor (GCD) of two integers based on division. It repeatedly applies the division process to reduce the problem until the GCD is identified.

Extended Euclidean Algorithm: An extension of Euclid's algorithm that finds integers x and y such that ax + by = gcd(a, b). It not only computes the GCD but also expresses it as a linear combination of the two integers.

📝 Essential Points

• Euclid's algorithm uses division to compute the GCD by repeatedly replacing the larger number with the remainder of division until the remainder is zero.
• The last non-zero remainder in the process is the GCD of the original two numbers.
• The extended version allows for the calculation of coefficients x and y, which satisfy the linear combination ax + by = gcd(a, b).
• Both algorithms are fundamental in number theory and have applications in areas like cryptography and solving linear Diophantine equations.

💡 Key Takeaway

Euclid's algorithm provides an efficient method to compute the GCD of two integers through division, while its extension, the Extended Euclidean Algorithm, additionally finds the linear combination of those integers that equals the GCD.

📖 9. Extended Euclidean Algorithm

🔑 Key Concepts & Definitions

Extended Euclidean Algorithm: An algorithm to find the coefficients of Bézout's identity, expressing the GCD as a linear combination. It extends Euclid's Algorithm by not only computing the greatest common divisor (GCD) of two integers but also providing integers $x$ and $y$ such that $ax + by = \gcd(a, b)$.

Multiplicative Inverse: An integer $x$ such that $ax \equiv 1 \pmod{m}$. It exists if and only if $a$ and $m$ are coprime, meaning their GCD is 1.

📝 Essential Points

• The Extended Euclidean Algorithm is used to find integers $x$ and $y$ satisfying $ax + by = \gcd(a, b)$, known as Bézout's identity.
• It builds upon Euclid's Algorithm, which computes the GCD of two integers through successive division.
• The coefficients $x$ and $y$ obtained can be used to express the GCD as a linear combination of $a$ and $b$.
• The algorithm is fundamental in computing the multiplicative inverse of an integer modulo $m$, which exists if $a$ and $m$ are coprime.
• The existence of the multiplicative inverse is conditional: it exists if and only if $a$ and $m$ are coprime.

💡 Key Takeaway

The Extended Euclidean Algorithm not only finds the GCD of two integers but also provides the specific coefficients that express this GCD as a linear combination, which is essential for computing modular inverses when the integers are coprime.

📖 10. Multiplicative Inverse

🔑 Key Concepts & Definitions

• Congruence (see section 9.2): An equivalence relation where two integers are congruent modulo n if they have the same remainder when divided by n, denoted as $a \equiv b \pmod{n}$.

• Multiplicative Inverse: An integer $x$ such that $a \times x \equiv 1 \pmod{n}$, where $a$ and $n$ are integers, and $a$ is coprime to $n$. The inverse exists if and only if $a$ and $n$ are coprime.

📝 Essential Points

• The multiplicative inverse of $a$ modulo $n$ is an integer $x$ satisfying $a \times x \equiv 1 \pmod{n}$.

• The inverse exists only when $a$ and $n$ are coprime, i.e., their greatest common divisor $\gcd(a, n) = 1$.

• The concept of the multiplicative inverse is fundamental in modular arithmetic, especially in solving linear congruences and in cryptography.

• The inverse, if it exists, is unique modulo $n$.

💡 Key Takeaway

A multiplicative inverse of an integer modulo $n$ is an integer that, when multiplied by the original, yields 1 in modular terms; it exists only when the original and $n$ are coprime, and it is unique modulo $n$.

📊 Synthesis Tables

⚠️ Common Pitfalls & Confusions

1. Confusing quotient $q$ and remainder $r$ in division; forgetting $0 \leq r < d$.
2. Assuming divisibility implies the divisor divides the dividend evenly without remainder.
3. Misapplying the properties of modular arithmetic; forgetting that congruence is an equivalence relation.
4. Overlooking the uniqueness of prime factorization; assuming multiple factorizations.
5. Confusing linear combinations with simple sums; coefficients must be integers.
6. Forgetting that the division algorithm applies to all integers, including negatives, with specific procedures.
7. Misinterpreting the relation between divisibility and linear combinations; divisibility of individual numbers does not automatically imply divisibility of their sum unless conditions are met.
8. Assuming prime numbers are only positive; note that primes are greater than 1.

✅ Exam Checklist

• Know the statement and proof of the Division Algorithm, including the existence and uniqueness of $q, r$.
• Understand the definitions of divisibility, multiple, factor, and their relation to linear combinations.
• Be able to compute quotients and remainders for given integers and understand their properties.
• Master the concept of congruence modulo $m$, including properties of addition, subtraction, and multiplication within modular arithmetic.
• Recall the Fundamental Theorem of Arithmetic and the uniqueness of prime factorization.
• Know the definitions and properties of prime and composite numbers.
• Apply Euclid's Algorithm to find the Greatest Common Divisor (GCD) of two integers.
• Understand the Extended Euclidean Algorithm and how it computes the GCD along with coefficients for linear combinations.
• Be able to find the multiplicative inverse of an integer modulo $m$, especially using the Extended Euclidean Algorithm.
• Recognize the importance of the GCD in divisibility and linear combinations.
• Know SMITH's definition of the invisible hand (if relevant to the course content).
• Be familiar with the procedural steps for division, modular arithmetic, and prime factorization.
• Understand how to use prime factorization to compute GCD and least common multiple (if covered).