Summary of "สรุป "ทฤษฎีจำนวน" (ตอนที่ 2) | เตรียมความพร้อมสู่การสอบ สอวน. คอมพิวเตอร์ ค่าย 1"
Main Ideas, Concepts, and Lessons Conveyed
1. Introduction to Number Theory and Its Importance
- Number Theory is frequently tested in math competitions and exams like สอวน. (Thailand's Olympiad in Informatics).
- Although some topics are not in the standard curriculum, they appear often in competitions.
- The tutor encourages students to practice and understand division, remainders, prime numbers, and related concepts.
2. Division Algorithm and Remainders
- Fundamental division formula: Dividend = Divisor × Quotient + Remainder
- Problems involving prime divisors where two numbers give the same remainder upon division.
- Using variables for quotient and remainder to form equations.
- Subtracting equations to find relationships and divisibility (e.g., divisor divides the difference of dividends).
3. Prime Numbers and Divisibility
- Identification of prime divisors based on the problem conditions.
- Checking divisibility by prime factors of the difference between two numbers.
- Using prime factorization to find possible divisors.
- Confirming which prime divisor yields the same remainder for both numbers.
4. Properties of Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
- Definitions and properties of GCD and LCM.
- GCD divides both numbers evenly.
- LCM is related to GCD by the formula: LCM(a, b) × GCD(a, b) = a × b
- Euclidean Algorithm for finding GCD:
- Repeated division with remainder.
- Last non-zero remainder is the GCD.
- Linear combinations: expressing GCD as a linear combination of two numbers (ax + by = GCD).
- Applications in solving Diophantine Equations.
5. Euclidean Algorithm Step-by-Step
- Example calculations with numbers (e.g., 1331 and 891).
- Process of dividing, taking remainders, and swapping dividend/divisor.
- Finding GCD efficiently without prime factorization.
- Using Euclidean Algorithm to find unknown coefficients in linear combinations.
6. Application of GCD and LCM in Polynomial Remainder Problems
- Use of the Remainder Theorem: The remainder when a polynomial f(x) is divided by (x - a) is f(a).
- Substituting values into polynomials to find remainders.
- Examples with cubic polynomials and given coefficients.
7. Relative Prime Numbers (Coprime)
- Two numbers are relatively prime if their GCD is 1.
- Properties of relative primes:
- Multiplying relative primes keeps the GCD as 1.
- Powers of relative primes remain relative prime.
- Problems involving counting numbers relatively prime to a given number within a range.
- Use of inclusion-exclusion principle to count multiples and non-multiples.
8. Modular Arithmetic (Congruences)
- Definition of congruence: a ≡ b (mod m) means a and b leave the same remainder when divided by m.
- Properties of Modular Arithmetic:
- Addition and multiplication of congruences.
- Powers under modulo.
- Using Modular Arithmetic to solve problems such as finding units digits and remainders of large exponents.
- Examples:
- Units digit of 8^50.
- Remainder of 3^2556 when divided by 10.
- Application of Modular Arithmetic in simplifying large exponent calculations.
9. Practice Problems and Exam Tips
- Step-by-step solving of past exam problems from various years (2013, 2014, 2016, 2017, 2020, etc.).
- Emphasis on understanding the properties and applying the Euclidean Algorithm.
- Encouragement to practice linear combinations and Modular Arithmetic.
- Advice on recognizing patterns and using theorems to simplify calculations.
- Importance of accurately finding remainders and divisors in problems.
10. Additional Notes and Resources
- Announcement of future tutoring sessions (both online and onsite).
- Mention of supplementary videos for deeper understanding, especially on Modular Arithmetic.
- Encouragement to visit a specific website (SJC Computer) for more practice and video tutorials.
- Teacher Job’s teaching style includes humor, interaction, and encouragement.
Methodologies and Step-by-Step Instructions Highlighted
- Using the Division Algorithm:
- Express dividend as divisor × quotient + remainder.
- Set variables for unknown quotients and remainders.
- Subtract equations to find divisibility conditions.
- Finding GCD via Euclidean Algorithm:
- Divide larger number by smaller number.
- Replace larger number with smaller number and smaller number with remainder.
- Repeat until remainder is zero; last non-zero remainder is the GCD.
Category
Educational
