Prelim Workbook 2023 Number Theory PDF

PAMANTASAN NG CABUYAO |NUMBER THEORY 1 Course Material No. 1 NUMBER THEORY EMERSON B. ROBLES Course Instructor PAMANTASAN NG CABUYAO |NUMBER THEORY 2 THE INTEGERS...

PAMANTASAN NG CABUYAO |NUMBER THEORY 1 Course Material No. 1 NUMBER THEORY EMERSON B. ROBLES Course Instructor PAMANTASAN NG CABUYAO |NUMBER THEORY 2 THE INTEGERS 1 LEARNING OUTCOMES Here’s what I will teach you in this course material: Explain the definitions and properties of basic concepts related to numbers and sequences by producing examples and non-examples; Use the Well-Ordering Property in proving propositions about the integers; Prove the properties on sums and products and other related propositions; Apply appropriate properties in solving problems involving sums and products; Prove the first and second principles of Mathematical Induction (PMI); apply the principles of mathematical induction in proving formulae and other claims related to the integers; produce counterexamples to show falsity of statements; prove claims on the Fibonacci sequence and other similar recursive functions prove the properties of binomial coefficients; apply the Binomial Theorem in writing the expansions of binomial powers; use definitions and theorems in proving propositions on divisibility; recognize and describe number patterns on the Pascal Triangle. PAMANTASAN NG CABUYAO |NUMBER THEORY 3 RESOURCES NEEDED For this lesson, you would need the following resources: Power Point Presentation: a. Number Concepts b. Sequences c. Well-Ordering Properties d. Sum and Product e. Fibonacci Sequence f. Mathematical Induction g. Binomial Coefficient h. Divisibility Video Link a. Number Theory - Numbers and Sequences, Rational and Irrational Numbers, part 1 https://www.youtube.com/watch?v=2X86zLDxBGM b. Number Theory - Numbers and Sequences, Rational and Irrational Numbers, part 2 https://www.youtube.com/watch?v=CVI8I09VrHg c. Number Theory - Sums and Products, part 1 https://www.youtube.com/watch?v=3w-Vwbo8JHQ d. Number Theory - Sums and Products, part 2 https://www.youtube.com/watch?v=zJ1d91DFH00 e. Number Theory - Mathematical Induction, part 3 https://www.youtube.com/watch?v=p9JRLW0x-UM f. Number Theory - The Fibonacci Numbers https://www.youtube.com/watch?v=xIXuzP-Se8g g. Number Theory - Divisibility https://www.youtube.com/watch?v=XHSC-Y3fnMQ h. Number Theory - Mathematical Induction, part 2 https://www.youtube.com/watch?v=KvfU3dw263U Reference materials, tools, and equipment PAMANTASAN NG CABUYAO |NUMBER THEORY 4 MODULE CONTENTS Direction: Give at least 5 numbers written in the form of sequence on each type of numbers. 4 Pretest 1. Natural Numbers _________________________________________ 5 Unjumbled It! 2. Whole Numbers ________________________________________ 6 Number and Sequence 3. Even Numbers ________________________________________ 4. Odd numbers 9 Sum and Product Mathematical ________________________________________ 5. Prime Numbers 13 Induction ________________________________________ 6. Composite Numbers 15 Binomial Coefficient ________________________________________ 7. Square Numbers 16 Divisibility ________________________________________ Let’s Go Activities 8. Cube Numbers 17 ________________________________________ 9. Fibonacci Numbers 19 Summary ________________________________________ 10. Triangular Pattern Symbols Key Terms ________________________________________ 19 Post-test 20 References 21 PAMANTASAN NG CABUYAO |NUMBER THEORY 5 Unjumble It! Rearrange the jumbled letter to form a word that describe on each statement. 1. M U R N E B S - _________________________________ An arithmetic value used for representing the quantity and used in making calculations. 2. L A R U T A N - _________________________________ Numbers that start from 1 and end at infinity. 3. L E W O H - _________________________________ Numbers that start from 0 and end at infinity. 4. B U R N E M R H E T O Y - _________________________________ The branch of mathematics that deals with the properties and relationships of numbers, especially the positive integers. 5. C S E U N Q E E - _________________________________ A set of numbers with corresponding patterns. 6. V E E N - _________________________________ Numbers that are divisible by 2. 7. D O D - _________________________________ Numbers that are not divisible by 2. 8. R I M P E - _________________________________ Numbers whose factors are one and itself that is not 1. 9. P O C O M T I S E - _________________________________ Numbers with more than two factors. 10. I D I V I S I V I L Y T - _________________________________ Property of an integer number to be divided by another, resulting an integer number. PAMANTASAN NG CABUYAO |NUMBER THEORY 6 NUMBERS AND SEQUENCES Number theory is a branch of mathematics concerned with the properties and relationships of whole numbers and integers. It investigates into the fundamental principles and structures of numbers, revealing patterns, features and relationships that support the complex world of mathematics. In this module, you will study the fundamental properties and relationships of numbers. Number Concepts 1. Natural Numbers: Definition: Natural numbers, denoted by N, are the set of positive whole numbers starting from 1 and continuing infinitely. They do not include zero or any negative numbers. Examples: 1, 2, 3, 4, 5... Non-examples: 0, -1, -2, fractions or decimals 2. Whole Numbers: Definition: Whole numbers, denoted by W, are the set of non-negative integers, including zero. They do not include fractions or decimals. Examples: 0, 1, 2, 3, 4... Non-examples: -1, -2, 1.5, 3/4 3. Integers: Definition: Integers, denoted by Z, are the set of positive and negative whole numbers, including zero. Examples: -3, -2, -1, 0, 1, 2, 3... Non-examples: 1.5, 3/4, √2, fractions 4. Rational Numbers: Definition: Rational numbers, denoted by Q, are numbers that can be expressed as a fraction, where the numerator and denominator are integers (non-zero). Examples: 1/2, -3/4, 2, 0, 7/1... Non-examples: √2, π, e, non-terminating or non-repeating decimals PAMANTASAN NG CABUYAO |NUMBER THEORY 7 5. Irrational Numbers: Definition: Irrational numbers are numbers that cannot be expressed as a fraction. They are non-terminating and non-repeating decimals. Examples: √2, π, e... Non-examples: 2, 3/4, 0, 5, integers, rational numbers 6. Real Numbers: Definition: Real numbers, denoted by R, include all rational and irrational numbers. They encompass the entire number line. Examples: 1, √2, π, -5, 3/4, 0, 7... Non-examples: Complex numbers, fractions, integers only 6. Arithmetic Sequence: Definition: An arithmetic sequence is a sequence of numbers in which the difference between any two consecutive terms is constant. Example: 2, 5, 8, 11, 14... (common difference = 3) Non-example: 1, 3, 7, 12, 18... (not a constant difference) 7. Geometric Sequence: Definition: A geometric sequence is a sequence of numbers in which each term is obtained by multiplying the previous term by a constant ratio. Example: 3, 6, 12, 24, 48... (common ratio = 2) Non-example: 1, 4, 8, 12, 16... (not a constant ratio) 8. Fibonacci Sequence: Definition: The Fibonacci sequence is a sequence of numbers in which each term is the sum of the two preceding terms, starting with 0 and 1. Example: 0, 1, 1, 2, 3, 5, 8, 13... Non-example: 1, 2, 4, 7, 11, 16, 22... (not following the Fibonacci rule) PAMANTASAN NG CABUYAO |NUMBER THEORY 8 Types of Numbers The following types of numbers that help in analyzing the properties and relationships and providing insights into the fascinating world of mathematics. 1. Even Numbers: Even numbers are integers that are divisible by 2 without leaving a remainder. They can be represented as 2n, where n is an integer. Examples include 2, 4, 6, 8, 10, and so on. 2. Odd Numbers: Odd numbers are integers that are not divisible by 2 without leaving a remainder. They can be represented as 2n + 1 or 2n - 1, where n is an integer. Examples include 1, 3, 5, 7, 9, and so on. 3. Prime Numbers: Prime numbers are positive integers greater than 1 that have no divisors other than 1 and themselves. In other words, they cannot be divided evenly by any other number. Examples of prime numbers include 2, 3, 5, 7, 11, 13, 17, and so on. 4. Composite Numbers: Composite numbers are positive integers greater than 1 that are not prime, meaning they have divisors other than 1 and themselves. They can be divided evenly by multiple factors. Examples of composite numbers include 4, 6, 8, 9, 10, 12, 14, and so on. 5. Perfect Numbers: Perfect numbers are positive integers that are equal to the sum of their proper divisors. Proper divisors are all the divisors of a number except the number itself. The first four perfect numbers are 6, 28, 496, and 8128. 6. Triangular Numbers: Triangular numbers are a sequence of numbers that can form an equilateral triangle when arranged in dots or objects. The nth triangular number is equal to the sum of the first n positive integers. The sequence begins as 1, 3, 6, 10, 15, and so on. Some Typical Number Theoretic Questions The primary objective of number theory is to identify intriguing and surprising connections between various types of numbers and to demonstrate that these connections exist and are real. The few common number theory issues are listed below. 1. Sums of Squares I. Can two squares added together form a square? a. Yes, these numbers are called Pythagorean Triple. For example, i. 32 + 42 = 52 52 + 122 = 132 b. Can you think of another example? PAMANTASAN NG CABUYAO |NUMBER THEORY 9 2. Sum of Higher Power. Can two cubes added together form a cube? Can two fourth powers added together make a fourth power? Can the sum of two nth powers in general be an nth power? a. No. 3. Infinitude of Primes. Are there infinitely many prime numbers? a. Since prime numbers are numbers whose only factor is 1 and itself, therefore, there are infinite many prime numbers such as 2, 3, 5, 7, … 4. Sums of Squares II. Is there a prime number that is a sum of two squares? a. Yes. Number such as 5, 13, 17, 29, 37,... i. 5 = 12 + 22 13 = 22 + 32 17 = 12 + 42 b. What are the two squares whose sum is 29 and 37? Can you think of another example? 5. Number Shapes. Is there are any triangular numbers that are also square numbers (other than 1). a. Yes. The smallest triangular number (except 1) that is also a square number is 36. b. square: 1, 4, 9, 16, 25, 36,... c. triangular: 1, 3, 6, 10, 15, 21, 36... 6. Twin Primes or Consecutive Prime Numbers. Is there an infinite number of twin primes? a. There are twin primes, but no one knows whether there are infinitely many twin primes. i. 3, 5 5, 7 11, 13 17, 19 b. Can you think of another example of twin prime? THE WELL-ORDERING PRINCIPLE A Well-Ordering Principle states that every nonempty set of nonnegative integers has a least element. Example of Well-Ordered Set A ={n ∈ N ∣ n is a multiple of 4}, B = {n ∈ N ∣ n = −15 + 6m for some m ∈ Z}, Since they only include positive integers, it is simple to verify that each of the three sets is nonempty. Additionally, the well-ordering principle ensures that each set has a minimum element. PAMANTASAN NG CABUYAO |NUMBER THEORY 10 It is obvious that the smallest element in A is 4. To find the smallest element in B, you need −15 + 6m > 0, which means m > 15/6 = 2.5 = 3. Therefore, the smallest element in B is −15 + 6 ⋅ 3 = 3. Example of NOT Well-Ordered Set Z (the open interval (0, 5) is a non-empty subset of R but it has no smallest element) Z (the set of negative integers is a non-empty subset of Z but with no smallest element) The interval [0, 2] (because (0, 2) is a non-empty subset of [0, 2] without smallest element) SUM AND PRODUCT In number theory, the concepts of the sum and product play significant roles in understanding the properties and relationships of numbers. The sum refers to the result of adding two or more numbers together, while the product refers to the result of multiplying two or more numbers. A. Sum of Numbers The sum of numbers can be used to determine the total or combined value of quantities. It allows us to find the result of adding individual values together, such as the sum of two or more integers, fractions, decimals, or even algebraic expressions. The sigma notation denotes the sum of two or more numbers. Sigma (Summation) Notation 𝑛 ∑ 𝑎𝑘 = 𝑎𝑖 + 𝑎𝑖+1 + 𝑎𝑖+2 + ⋯ + 𝑎𝑛 𝑘=𝑖 Examples 1 7 𝑎. ∑ 𝑎𝑘 = 𝑎2 + 𝑎3 + 𝑎4 + 𝑎5 + 𝑎6 + 𝑎7 𝑘=2 5 𝑏. ∑ 6 = 6 + 6 + 6 + 6 + 6 = 30 𝑘=1 4 𝑐. ∑(𝑘 + 1) = 2 + 3 + 4 + 5 = 14 𝑘=1 PAMANTASAN NG CABUYAO |NUMBER THEORY 11 Example 2 2 3 4 5 Write 3 + 4 + 5 + 6 using notation form. Solution: 4 5 3 2 3 4 5 𝑘+1 𝑘 𝑘+2 + + + =∑ =∑ =∑ 3 4 5 6 𝑘+2 𝑘+1 𝑘+3 𝑘=1 𝑘=2 𝑘=0 Example 3 Write 22 + 32 + 42 + 52 + 62 using notation form. Solution: 5 6 4 2 + 3 + 4 + 5 + 6 = ∑(𝑘 + 1) = ∑ 𝑘 = ∑(𝑘 + 2)2 2 2 2 2 2 2 2 𝑘=1 𝑘=2 𝑘=0 B. Product of Numbers The product of numbers represents the result of multiplying values together. It is commonly used to determine the total value obtained from repeated addition or multiplication, and it is especially useful in calculating the area, volume, or the total outcome of a set of quantities. The pi notation denotes the sum of two or more numbers. Pi (Product) Notation 𝑛 ∏ 𝑎𝑘 = 𝑎𝑖 𝑎𝑖+1 ∙ 𝑎𝑖+1 𝑎𝑖+2 ∙ … 𝑎𝑗 𝑘=𝑖 Example 4 𝑎. ∏ 3 = 3 ∙ 3 ∙ 3 ∙ 3 = 34 = 81 𝑘=1 5 𝑏. ∏ 3 = 3 ∙ 3 ∙ 3 ∙ 3 = 34 = 81 𝑘=2 6 𝑐. ∏ 𝑘 = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 6! = 720 𝑘=1 PAMANTASAN NG CABUYAO |NUMBER THEORY 12 Properties of Sums and Products 1. Distributive Property: The distributive property allows you to expand expressions involving sums and products. It states that for any numbers a, b, and c, (a + b) * c = a * c + b * c. This property can be useful in simplifying expressions and performing calculations. For example: Simplify the expression 3 * (4 + 2): 3 * (4 + 2) = 3 * 4 + 3 * 2 = 12 + 6 = 18 2. Commutative Property: The commutative property applies to addition and multiplication and states that the order of the numbers does not affect the result. For example: Calculate the sum of 7 + 3 + 5 + 2: By applying the commutative property, we can rearrange the numbers: 7 + 3 + 5 + 2 = 2 + 3 + 5 + 7 = 17 3. Associative Property: The associative property applies to addition and multiplication and states that the grouping of numbers does not affect the result. For example: Calculate the sum of (4 + 7) + 2 + 5: By applying the associative property, we can regroup the numbers: (4 + 7) + 2 + 5 = 4 + (7 + 2) + 5 = 4 + 9 + 5 = 18 4. Identity Property: The identity property of addition and multiplication states that there exist unique elements (0 for addition and 1 for multiplication) that, when added or multiplied to any number, do not change the result. For example: Calculate the sum of 6 + 0: The identity property of addition tells us that the sum is simply the number itself: 6+0=6 5. Zero Property: The zero property of multiplication states that any number multiplied by zero results in zero. For example: Calculate the product of 9 * 0: Applying the zero property of multiplication, we know that the product is zero: 9*0=0 PAMANTASAN NG CABUYAO |NUMBER THEORY 13 MATHEMATICAL INDUCTION For each and every natural number n, a statement, theorem, or formula can be proved using the mathematical induction technique. By generalizing this into the "Principle of Mathematical Induction," which we would utilize to demonstrate any mathematical statement. It has only 3 steps: Step 1. Show it is true for first case, usually n = 1 Step 2. Show that n = k is true. Step 3. Show that n = k + 1 is also true. Example 1: Prove that 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 𝑓𝑜𝑟 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 𝑛 ≥ 1. Proof: STEP 1: For n = 1, 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 is true since 1 = (1)2. STEP 2: Supposed 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 is true for some integer 𝑛 = 𝑘 ≥ 1. That is 1 + 3 + 5 + ⋯ + (2𝑘 − 1) = 𝑘 2 STEP 3: Prove that 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛2 is true for n = k + 1. That is 1 + 3 + 5 + ⋯ + (2𝑘 − 1) + (2(𝑘 + 1) − 1) = (𝑘 + 1)2 1 + 3 + 5 + ⋯ + (2𝑘 − 1) + (2𝑘 + 1) = (𝑘 + 1)2 𝑘 2 + (2𝑘 + 1) = (𝑘 + 1)2 𝑘 2 + 2𝑘 + 1 = (𝑘 + 1)2 ∎ Example 2: Prove 𝑛(𝑛 + 1) 1+2+3+⋯+𝑛 = ,𝑛 ≥ 1 2 Proof: STEP 1: For n = 1, 𝑛(𝑛+1) 1(1+1) 1 + 2 + 3 + ⋯ + 𝑛 = 2 is true since 1 = 2. 𝑛(𝑛+1) STEP 2: Supposed 1 + 2 + 3 + ⋯ + 𝑛 = is rue for some integer 𝑛 = 𝑘 ≥ 1. That is 2 𝑘(𝑘+1) 1+2+3+⋯+𝑘 =. 2 𝑛(𝑛+1) STEP 3: Prove that 1 + 2 + 3 + ⋯ + 𝑛 = is true for n = k + 1. That is 2 (𝑘 + 1)((𝑘 + 1) + 1) 1 + 2 + 3 + ⋯ + 𝑘 + (𝑘 + 1) = 2 PAMANTASAN NG CABUYAO |NUMBER THEORY 14 𝑘 (𝑘 + 1) (𝑘 + 1)(𝑘 + 2) + (𝑘 + 1) = 2 2 𝑘 (𝑘 + 1) + 2(𝑘 + 1) = (𝑘 + 1)(𝑘 + 2) (𝑘 + 1)(𝑘 + 2) = (𝑘 + 1)(𝑘 + 2)∎ Example 3: Prove 3𝑛 ≥ 2𝑛 + 1, 𝑛 ≥ 0 𝑎𝑛𝑑 𝑛 ∈ ℤ Proof: STEP 1: For n = 0, 3𝑛 ≥ 2𝑛 + 1, is true since 30 ≥ 2(0) + 1. STEP 2: Supposed 3𝑛 ≥ 2𝑛 + 1, is true for some integer 𝑛 = 𝑘 ≥ 0. That is 3𝑘 ≥ 2𝑘 + 1, STEP 3: Prove that 3𝑛 ≥ 2𝑛 + 1, is true for n = k + 1. That is 3𝑘+1 ≥ 2(𝑘 + 1) + 1 31 ∙ 3𝑘 ≥ 2(𝑘 + 1) + 1 3(2𝑘 + 1) ≥ 2𝑘 + 2 + 1 6𝑘 + 3 ≥ 2𝑘 + 3 4𝑘 ≥ 0∎ Mathematical induction is a powerful proof technique used to establish the truth of statements about integers. However, it is not infallible, and there can be cases where it fails to prove a statement. Here are a couple of counterexamples that demonstrate the falsity of statements using mathematical induction: Counterexample 1: Statement - "All positive integers are equal." Let's consider the base case where n = 1. The statement claims that 1 is equal to all positive integers, which is false. Now, assuming the statement is true for some positive integer k, let's consider the next positive integer k + 1. According to the statement, k + 1 should also be equal to all positive integers, but that is clearly not the case. Therefore, the statement fails for the base case and is false for all positive integers. Counterexample 2: Statement - "Every positive integer is a multiple of 5." Let's consider the base case where n = 1. The statement claims that 1 is a multiple of 5, which is false. Now, assuming the statement is true for some positive integer k, let's consider the next positive integer k+1. According to the statement, k+1 should also be a multiple of 5, but that is not true for all positive integers. For example, if k = 4, which is not a multiple of 5, then k+1 = 5, which is a multiple of 5. However, if k = 5, then k+1 = 6, which is not a multiple of 5. Therefore, the statement fails for the base case and is false for all positive integers. PAMANTASAN NG CABUYAO |NUMBER THEORY 15 FIBONACCI SEQUENCE The Fibonacci sequence is a famous sequence of numbers that has fascinated mathematicians for centuries. It is named after the Italian mathematician Leonardo of Pisa, also known as Fibonacci, who introduced the sequence to Western mathematics in the 13th century. The Fibonacci sequence starts with two initial terms, usually 0 and 1. Each subsequent term in the sequence is found by summing the two preceding terms. In other words, the sequence follows a recursive rule: F(1) = 0 F(2) = 1 F(n) = F(n-1) + F(n-2) for n > 2 The Fibonacci sequence begins as: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... Proofs for Some Claims about the Fibonacci Sequence Claim 1: The Fibonacci sequence is strictly increasing. Proof: Base Case: For the Fibonacci sequence, the first two terms are 0 and 1. Therefore, F(1) = 0 and F(2) = 1. Since 0 is less than 1, the base case holds. Inductive Step: Assume that for some positive integer k, F(k) < F(k + 1). We need to prove that F(k + 1) < F(k+2). Using the recursive definition of the Fibonacci sequence, we have: F(k + 2) = F(k + 1) + F(k) By the assumption, F(k) < F(k+1), and since the Fibonacci sequence only consists of non- negative integers, we have F(k + 1) ≥ 0 and F(k) ≥ 0. Therefore, F(k + 2) = F(k+1) + F(k) > F(k + 1) + 0 = F(k + 1), which implies F(k + 1) < F(k + 2). By mathematical induction, we have proved that the Fibonacci sequence is strictly increasing. Claim 2: The sum of the first n terms in the Fibonacci sequence is equal to F(n + 2) - 1. Proof: Base Case: For n = 1, the sum of the first term in the Fibonacci sequence is F(1) = 0. The formula F(1 + 2) - 1 = F(3) - 1 = 1 - 1 = 0 also gives the same result. Therefore, the base case holds. PAMANTASAN NG CABUYAO |NUMBER THEORY 16 Inductive Step: Assume that the claim is true for some positive integer k, i.e., the sum of the first k terms is equal to F(k + 2) – 1. We need to prove that the claim holds for k + 1, i.e., the sum of the first k + 1 terms is equal to F(k + 3) – 1. The sum of the first k+1 terms can be written as: F(1) + F(2) +... + F(k) + F(k + 1) Using the recursive definition of the Fibonacci sequence, we know that F(k + 1) = F(k) + F(k – 1). Therefore, we can rewrite the sum as: (F(1) + F(2) +... + F(k – 1)) + (F(k) + F(k + 1)) By the assumption, the first term in the parentheses is equal to F(k + 1) – 1, and the second term is F(k + 2) – 1. So the sum becomes: (F(k + 1) – 1) + (F(k + 2) – 1) Simplifying, we get: F(k + 1) + F(k + 2) – 2. Using the recursive definition of the Fibonacci sequence again, we know that F(k + 3) = F(k + 2) + F(k + 1). Substituting this into the sum, we have: F(k + 3) – 1. Therefore, by mathematical induction, we have proved that the sum of the first n terms in the Fibonacci sequence is equal to F(n +2 ) – 1. BINOMIAL COEFFICIENT Definition : Binomial coefficient is the number of possible combinations of r items from a set of n items. Additionally, it represent for a point on Pascal's triangle. Properties of Binomial Coefficients 1. Symmetry Property: The binomial coefficient, denoted as "n choose k" or C(n, k), satisfies the symmetry property: C(n, k) = C(n, n – k) Proof: By definition, the binomial coefficient is given by: C(n, k) = n! / (k!(n-k)!) C(n, k) = n! / (k!(n-k)!) = n! / ((n-k)!k!) C(n, k) = n! / ((n-k)!k!) = n! / (k!(n-k)!) = C(n, n-k) Thus, we have proved the symmetry property of binomial coefficients. 2. Pascal's Identity: Pascal's Identity states that the sum of two adjacent binomial coefficients is equal to the binomial coefficient of the next row. Mathematically, it can be expressed as: C(n, k) + C(n, k+1) = C(n+1, k+1) PAMANTASAN NG CABUYAO |NUMBER THEORY 17 Proof: Using the definition of binomial coefficients, we have: C(n, k) = n! / (k!(n-k)!) C(n, k+1) = n! / ((k+1)!(n-k-1)!) C(n, k) + C(n, k+1) = n! / (k!(n-k)!) + n! / ((k+1)!(n-k-1)!) C(n, k) + C(n, k+1) = [(n!(k+1))/(k!(n-k)!(k+1))] + [(n!(n-k))/(k!(n-k)!(n-k))] C(n, k) + C(n, k+1) = [(n!(k+1)+n!(n-k))/(k!(n-k)!(k+1))] C(n, k) + C(n, k+1) = [n!(k+1+n-k)] / (k!(n-k)!(k+1)) C(n, k) + C(n, k+1) = [n!(n+1)] / (k!(n-k)!(k+1)) C(n, k) + C(n, k+1) = C(n+1, k+1) Thus, we have proved Pascal's Identity. The Binomial Theorem For each positive integer n, 𝑛 𝑛 𝑛 𝑛 (𝑥 + 𝑦)𝑛 = 𝑥 𝑛 + ( ) 𝑥 𝑛−1 𝑦 + ( ) 𝑥 𝑛−2 𝑦 2 + ⋯ + ( ) 𝑥 𝑛 𝑦 𝑟 + ⋯ + ( ) 𝑥𝑦 𝑛−1 + 𝑦 𝑛 1 2 𝑟 𝑛−1 Example: Expand (2x +3)4. Solution: 4 4 4 (2𝑥 + 3)4 = (2𝑥)4 + ( ) (2𝑥)3 (3) + ( ) (2𝑥)2 (3)2 + ( ) (2𝑥)(3)3 + (3)4 1 2 3 = 16𝑥 4 + 4(8𝑥)3 (3) + 6(4𝑥 2 )(9) + 4(2𝑥 )(27) + 81 = 16𝑥 4 + 96𝑥 3 + 216𝑥 2 + 216𝑥 + 81 The General Term of Binomial Expansion 𝑛 𝑛 (𝑎 + 𝑏) = ∑ ( ) 𝑎𝑛−𝑘 𝑏𝑘 𝑛 𝑘 𝑘=0 Wherein k = n – r + 2 Example: Find the 7th term in the expansion of (x + 2)10. Solution: 10 10 10 (𝑥 + 2)10 = ∑ ( ) 𝑥 4 (2)10−4 = ( ) (64)𝑥 4 = 13440𝑥 4 10 − 7 + 1 4 𝑘=0 PAMANTASAN NG CABUYAO |NUMBER THEORY 18 DIVISIBILITY Divisibility Rule Divisibility by 1: Every integer is divisible by 1. In other words, for any integer n, n divided by 1 leaves no remainder. Divisibility by itself: Every integer is divisible by itself. For any integer n, n divided by n leaves no remainder. Divisibility by 0: Division by zero is undefined in mathematics. Therefore, we cannot talk about divisibility by zero. Divisibility by 2 (even numbers): An integer is divisible by 2 if its last digit is even. In other words, if the ones digit is 0, 2, 4, 6, or 8, then the number is divisible by 2. Divisibility by 3: An integer is divisible by 3 if the sum of its digits is divisible by 3. For example, the number 123 is divisible by 3 since 1 + 2 + 3 = 6, which is divisible by 3. Divisibility by 4: An integer is divisible by 4 if the number formed by its last two digits is divisible by 4. For example, the number 568 is divisible by 4 since 68 is divisible by 4. Divisibility by 5: An integer is divisible by 5 if its last digit is 0 or 5. In other words, if the ones digit is 0 or 5, then the number is divisible by 5. Divisibility by 6: An integer is divisible by 6 if it is divisible by both 2 and 3. This means that the number must have an even last digit and the sum of its digits must be divisible by 3. Divisibility by 9: An integer is divisible by 9 if the sum of its digits is divisible by 9. For example, the number 315 is divisible by 9 since 3 + 1 + 5 = 9, which is divisible by 9. Divisibility by 10: An integer is divisible by 10 if its last digit is 0. In other words, if the ones digit is 0, then the number is divisible by 10. Divisibility on Number Theory Definition: Let a and b be two integers such that a ≠ 0. We say that a divides b if there is an integer q such that aq = b. If a divides b, then a is a divisor or factor of b. This denoted as a | b which read as a divides b. Example: 4 | 16, since 16 = 4 · 4 3 | 12, since 12 = 3 · 4 PAMANTASAN NG CABUYAO |NUMBER THEORY 19 Properties of Divisibility 1. If a | b, then a | bc for all c. Proof: a. If a | b then b = am for 𝑚 ∈ ℤ. Since we want to show a | bc, then there should be exist some integer n where bc = an. Since bc = (am)c = a(mc), then n = mc so a| bc. 2. If a | b and b | c, then a | c. Proof: a. Since a | b, there exists an integer m1 such that am1 = b. Since b | c , there b. exists an integer m2 such that bm2 = c. Substituting am1 for b in the second equation gives am1m2 = c, which implies that a | c. 3. For all c ≠ 0, a | b if and only if ca | cb. Proof: First, suppose a | b. This means am = b for some m. Multiplying both sides by c gives cam = cb for some m. This implies ca | cb. Now, suppose ca | cb. Then cam = cb for some m. We can divide both sides by c since c is nonzero, so am = b for some k. This means a | b. PAMANTASAN NG CABUYAO |NUMBER THEORY 20 Activity 1: Think Deeply 1. What square numbers less than 500 that is also a cube numbers? 2. How many prime numbers between 100 and 150? 3. What prime number/s that can be represented as sums and differences between two primes? 4. What are the common factors of 48, 54 and 72? 5. How many triplets’ prime numbers less than 300? Activity 2: Sum and Product A. Use sigma notation to express each series. 1. 1 + 3 + 5 + 7 + 9 + … + 99 2. 2 + 4 + 6 + 8 + 10 + … + 100 3. 1 + 4 + 9 + 16 + … + 400 2 3 9 27 81 4. − 1+ − + − 3 2 4 8 16 2 4 8 16 32 64 5. + + + + − 3 7 11 15 19 23 B. Write out the terms of the following sums or product; then compute the sum or product. 6 5 7 𝑖 2 3𝑖 + 1 1. ∑ 3𝑖 2. ∑ 2 ∙ 𝑖 3. ∑ 𝑖+1 𝑖=0 𝑖=1 𝑖=2 PAMANTASAN NG CABUYAO |NUMBER THEORY 21 5 6 3 4. ∏(𝑖 − 1) 5. ∏ 2𝑖! 𝑖=1 𝑖=0 Activity 3: Prove to be True Direction: Use mathematical induction to prove that each statement is true for all positive integers. Use extra sheet of paper for your answer. 1. 𝑃𝑛 : 11 + 19 + 27 + ⋯ + (8𝑛 + 3) = 𝑛(4𝑛 + 7) 𝑛2 (𝑛+1)2 2. 𝑃𝑛 : 13 + 23 + ⋯ + 𝑛3 = 4 3. 𝑃𝑛 : 2𝑛 ≥ 1 + 𝑛, 𝑓𝑜𝑟 𝑛 ≥ 1 Activity 4: Expand Me A. Using the Binomial Theorem, expand the following binomial. 1. (2x – y)5 2. (x + 3y)4 3. (2a – 3b)5 4. (s + 2)6 5. (x – 2)6 B. Find the coefficient of the specific term in each of the following binomial. 6. (x +3)8 ; 7th term 7. (2x – 1)7 ; 5th term 8. (1 – y)10 ; 3rd term 9. (2y + 5)6 ; 4th term 10. (x + 6)5 ; 2nd term PAMANTASAN NG CABUYAO |NUMBER THEORY 22 SUMMARY 1. Number theory is the study of integers, particularly of those positive whole numbers 1, 2, 3, 4, 5, 6, 7,..., which are often called the set of natural or counting numbers. There are different types of natural numbers such as even, odd, prime, composite, triangular, Fibonacci, square, cube perfect, etc 2. Sequence is an ordered list of numbers. These numbers n exhibit a pattern where you’ll get the next number in the series by adding or multiplying a constant c to the last number. 3. A Well-Ordering Principle states that every nonempty set of nonnegative integers has a least element. 4. Sum : ∑𝑛𝑘=𝑖 𝑎𝑘 = 𝑎𝑖 + 𝑎𝑖+1 + 𝑎𝑖+1 + ⋯ + 𝑎𝑗 5. Product: ∏𝑛𝑘=𝑖 𝑎𝑘 = 𝑎𝑖 𝑎𝑖+1 ∙ 𝑎𝑖+1 𝑎𝑖+2 ∙ … 𝑎𝑗 6. For each and every natural number n, a statement, theorem, or formula can be proved using the mathematical induction technique. By generalizing this into the "Principle of Mathematical Induction," which we would utilize to demonstrate any mathematical statement. It has only 3 steps: Step 1. Show it is true for first case, usually n = 1 Step 2. Show that n = k is true. Step 3. Show that n = k + 1 is also true. 7. Binomial coefficient is the number of possible combinations of r items from a set of n items. Additionally, it represent for a point on Pascal's triangle. 𝑛 𝑛 (𝑎 + 𝑏) = ∑ ( ) 𝑎𝑛−𝑘 𝑏𝑘 𝑛 𝑘 𝑘=0 8. Divisibility. Let a and b be two integers such that a ≠ 0. We say that a divides b if there is an integer q such that aq = b. If a divides b, then a is a divisor or factor of b. This denoted as a | b which read as a divides b. which are often called the set of natural or counting KEY TERMS numbers. Number Theory Square and Cube Number Binomial Theorem Prime and Composite Number Sequence Binomial Coefficient Even and Odd Number Well-Ordering Principal Divisibility Triangular Number Mathematical Induction Notation PAMANTASAN NG CABUYAO |NUMBER THEORY 23 POSTTEST Directions: Fill in the blank with the letter corresponding to your answer. _______ 1. Which of the following is NOT a perfect number? a. 6 c. 120 b. 28 d. 496 _______ 2. The difference of an even number and an odd number is ____. a. an odd number c. a prime number b. an even number d. an even composite number _______ 3. Which of the following statements is true? a. All even numbers are prime numbers b. All composite numbers are even numbers c. All odd numbers are composite numbers d. 2 is an even prime numbers _______ 4. What is the general form of an even number? a. 2k c. k + 2 b. 2k + 1 d. none of these _______ 5. Two consecutive terms of a Fibonacci sequence are ______. a. Coprime c. Prime b. Even d. Composite _______ 6. If n, k ∈ ℤ such that n is the square of an odd integer, then perfect square must be of the form ______. a. 8k + 1 c. 6k + 1 b. 7k + 1 d. 9k + 1 _______ 7. If K is divisible by 3, 4 and 5, which of the following will also divide K? I. 3, 4, and 15 II. 12, 15, and 18 III. 5, 20, and 30 a. I only c. I and III b. III only d. I, II, III _______ 8. If a is divisible by b, which of the following are true? a. b divides into a evenly b. when we divide a by b, the remainder is 0. c. a = bq, for some integer q. d. All of the above. _______ 9. Which of the following is NOT a well-ordering set? a. N ∪ {0} c. {n ∈ N : n > 5} b. N ∪ {−1, 0} d. an open interval (0, 2) PAMANTASAN NG CABUYAO |NUMBER THEORY 24 _______ 10. Evaluate: ∑10 2 𝑘=1 2𝑘 + 4𝑘 − 5 a. 235 c. 940 b. 555 d. 1865 _______ 11. Express this series using sigma notation: 3 + 5 + 9 + 17 + 33. a. ∑∞ 𝑘 𝑘=1 2 + 1 c. ∑5𝑘=1 3 + 2𝑛 b. ∑𝑘=1 3 + 2𝑛 ∞ d. ∑5𝑘=1 2𝑘 + 1 _______ 12. By induction hypothesis, the series 12 + 22 + 32 + … + n2 can be proved equivalent to ____________ 𝑛2 +2 𝑛(𝑛+1) a. c. 7 4 𝑛(𝑛+1)(2𝑛+1) 𝑛2 +𝑛 b. d. 6 2 _______ 13. Which of the following is the base case for 4 n + 1 > (n+1)2 where n = 2? a. 17 > 9 c. 27 > 91 b. 16 > 2 d. 54 > 8 _______ 14. Find the coefficient of the x3 in (2x+1)12 a. 440 c. 1760 b. 440x3 d. 1760x3 _______ 15. Use the binomial theorem to expand (x + 2y)5. a. x5 + 2x4y + 8x3y2 + 16x2y3 + 16xy4 + 32y5 b. x5 + 10x4y + 40x3y2 + 80x2y3 + 80xy4 + 32y5 c. x5 + 2x4y + 4x3y2 + 8x2y3 + 8xy4 + 16y5 d. x5 + x4y + x3y2 + x2y3 + xy4 + y5 REFERENCES Burton, David M. (2011) Elementary Number Theory (7th edition). New York, USA: The McGraw-Hill Companies, Inc Hill, Richard Michael (2018) Introduction to Number Theory ( Essential Textbooks in Mathematics). London, Europe: World Scientific Publishing Europe Ltd. Jones, Gareth Michael (1998) Elementary Number Theory. Southampton, UK: Springer-Verlag London. Rosen, K.H. (2011). Elementary number theory and its applications (6th Edition). Boston, USA: Pearson. Tattersal, J.J. (1999). Elementary number theory in nine chapters. New York, USA: Cambridge University Press. PAMANTASAN NG CABUYAO |NUMBER THEORY 25 ANSWERS TO EXERCISES Page 4 Pre-Test answers vary Page 5 Pre-Activity 1. NUMBER 6. EVEN 2. NATURAL 7. ODD 3. WHOLE 8. PRIME 4. NUMBER THEORY 9. COMPOSITE 5. SEQUENCE 10. DIVISIBILITY Page 17 Activity 1 1.64 2. 10 3. 5 4. 6 5. 17 Page 17 Activity 2.A 1.∑100 𝑛=1 2𝑛 + 1 2. ∑100 𝑛=1 2𝑛 3. ∑20 1 𝑛 2 3 4. ∑6𝑛=1(− )𝑛 2 2𝑛 5. ∑6𝑛=1 4𝑛−1 2.B 1.63 2. 1146 3. 2179/140 4. 0 5. 3185049600 Page 18 Activity 3 Answer vary Page 18 Activity 4.A 1. 32x^5-80x^4y+80x^3y^2-40x^2y^3+10xy^4-y^5 2. x^4+12x^3y+54x^2y^2+108xy^3+81y^4 3. 32a^5-240a^4b+720a^3b^2-1080a^2b^3+810ab^4-243b^5 4. s^6+12s^5+60s^4+160s^3+240s^2+192s+64 5. x^6-12x^5+60x^4-160x^3+240x^2-192x+64 4.B 1.20412 2. 280 3. 45 4. 20000 5. 30 Page 19 Post-Test 1. C 6. A 11. d 2. a 7. B 12. b 3. d 8. D 13. a 4. a 9. D 14. c 5. a 10. C 15. b PAMANTASAN NG CABUYAO |NUMBER THEORY 26 Course Material No. 2 NUMBER THEORY EMERSON B. ROBLES Course Instructor PAMANTASAN NG CABUYAO |NUMBER THEORY 27 Primes and Greatest Common Divisors 2 LEARNING OUTCOMES Here’s what I will teach you in this course material: express relatively large positive integers in canonical or prime- factored form. use different methods in finding the greatest common divisor and least common multiple of given integers; prove theorems concerning the prime numbers, greatest common divisor and least common multiple of integers; RESOURCES NEEDED For this lesson, you would need the following resources: Power Point Presentation: a. Prime Numbers b. Greatest Common Divisor c. The Euclidean Algorithm d. Extended Euclidean Algorithm e. The Fundamental Theorem of Arithmetic Video Link a. The Prime Number Theorem, An Introduction https://www.youtube.com/watch?v=EKfdRks8oMI&pp=ygUecHJpbWUgbnVtY mVycyBpbiBudW1iZXIgdGhlb3J5 PAMANTASAN NG CABUYAO |NUMBER THEORY 28 b. Number Theory – The Greatest Common Divisor https://www.youtube.com/watch?v=1- kX4Zkw2Sc&pp=ygUoZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3IgaW4gbnVtY mVyIHRoZW9yeQ%3D%3D c. Euclidean Algorithm – An Example https://www.youtube.com/watch?v=fwuj4yzoX1o&pp=ygUkZXVjbGlkZWFuIGFsZ29ya XRobSBpbiBudW1iZXIgdGhlb3J5 d. Fundamental Theorem of Arithmetic https://www.youtube.com/watch?v=kFc8vDSF22M&pp=ygU3VGhlIGZ1bmRhbWVudGF sIHRoZW9yZW0gb2YgYXJpdGhtZXRpYyAgaW4gbnVtYmVyIHRoZW9yeQ%3D%3D PAMANTASAN NG CABUYAO |NUMBER THEORY 29 MODULE CONTENTS Direction: Choose the letter of your best answer. 29 Pretest 1. What is the only even prime number? a) 2 b) 4 c) 6 d) 8 30 Euclidean Riddle 2. Which of the following numbers is NOT a prime number? a) 3 b) 9 c) 17 d) 19 3. What is the prime factorization of 36? 31 Prime Numbers a) 22 x 33 b) 22 x 32 c) 23 x 33 d) 23 x 32 4. What is the largest prime number less than 100? 31 Greatest Common Divisor a) 93 b) 95 c) 97 d) 99 Euclidean Algorithm 5. What is the sum of the first three prime numbers? a) 4 b) 6 c) 8 d) 10 32 6. What is the GCD of 75 and 125 using the Euclidean algorithm? 33 The Fundamental Theorem of a) 5 b) 15 c) 25 d) 75 Arithmetic 7. What is the GCD of 36 and 48 using the Euclidean algorithm? 34 Euclidean Puzzle a) 3 b) 6 c) 9 d) 12 8. What is the GCD of 90 and 144 using the Euclidean algorithm? 35 Summary a) 6 b) 9 c) 18 d) 36 9. What is the GCD of 105 and 140 using the Euclidean 35 Key Terms algorithm? a) 5 b) 7 c) 15 d) 35 Post Test 10. What is the GCD of 60 and 75 using the Euclidean 35 algorithm? a) 5 b) 10 c) 15 d) 20 References 36 PAMANTASAN NG CABUYAO |NUMBER THEORY 30 Euclidean Riddle Solve the following math riddles. 1. Riddle: "I am thinking of two numbers. Their greatest common divisor is 9, and their product is 360. What are the two numbers?" 2. Riddle: "I have two different prime numbers. When their GCD is subtracted from their sum, the result is 9. What are the two prime numbers?" 3. Riddle: "I am thinking of a number. When I divide it by 15, the remainder is 8. However, when I divide it by 21, the remainder is 12. What is the number?" 4. Riddle: "I have a collection of 40 identical toys. I want to divide them equally among my children. However, I also want to keep the largest number of toys for myself. What is the largest number of toys I can keep?" PAMANTASAN NG CABUYAO |NUMBER THEORY 31 PRIME NUMBERS Prime numbers play a fundamental role in number theory, which is the branch of mathematics that deals with the properties and relationships of integers. Prime numbers are natural numbers greater than 1 that are divisible only by 1 and themselves, with no other factors. Definition: If the only positive factors of p are 1 and p, then the integer p is called prime. A composite integer is one that is greater than one but not prime. Note: An integer is a composite if and only if there exists an integer 𝑎 such that 𝑎|𝑛 and 1 < 𝑎 < 𝑛. There are infinitely many prime numbers, a fact famously proved by the ancient Greek mathematician Euclid. Some prime numbers are 2, 3, 5, 7, 9, 11, … Note that 1 is neither prime nor composite. Can you give a list of prime numbers less than 100? Some Theorems on Prime Numbers 1. An integer p ≥ 2 is composite if and only if it has factors a and b such that 1 < a < p and 1 < b < p. 2. If n > 1 then there is a prime p such that p | n. 3. There are infinitely many primes. 4. If n > 1 is composite then n has a prime divisor p ≤ √n. GREATEST COMMON DIVISOR The greatest common divisor (GCD), also known as the highest common factor, is a fundamental concept in number theory that represents the largest positive integer that divides two or more numbers without leaving a remainder. The GCD of two numbers is commonly denoted as GCD(a, b), where 'a' and 'b' are the given integers. The GCD can be found using different methods, with the most well-known being the Euclidean algorithm. This algorithm repeatedly divides the larger number by the smaller number and takes the remainder as the new divisor until the remainder becomes zero. The last non-zero remainder obtained in the process is the GCD of the original two numbers. The GCD has several key properties: 1. Divisibility: The GCD of two numbers divides both numbers evenly. In other words, if GCD(a, b) = d, then d divides both 'a' and 'b' without leaving a remainder. PAMANTASAN NG CABUYAO |NUMBER THEORY 32 2. Common Divisors: The GCD represents the largest common divisor of two or more numbers. It is the greatest number that divides all given numbers without remainder. Note: Two numbers are relatively prime if they have a greatest common divisor of 1. 3. Prime Factorization: The GCD of two numbers can be determined by identifying their common prime factors. The GCD is the product of the prime factors shared by both numbers, raised to the lowest exponent. 4. GCD and LCM Relationship: The GCD and the least common multiple (LCM) are related. The product of two numbers is equal to the product of their GCD and LCM: a * b = GCD(a, b) * LCM(a, b). This relationship can be extended to multiple numbers as well. Example: The set of common divisors of 18 and 30 is gcd(18, 30) = {−1, 1, −2, 2, −3, 3, −6, 6}. So, gcd(18, 30) = 6. EUCLIDEAN ALGORITHM The Euclidean algorithm is an ancient and efficient algorithm for finding the greatest common divisor (GCD) of two integers. It is named after the ancient Greek mathematician Euclid, who described the algorithm in his book "Elements" around 300 BCE. The algorithm works by repeatedly dividing the larger number by the smaller number and replacing the larger number with the remainder obtained. This process is repeated until the remainder becomes zero. The last non-zero remainder obtained is the GCD of the original two numbers. The steps of the Euclidean algorithm can be summarized as follows: 1. Take two integers, 'a' and 'b', where 'a' is greater than or equal to 'b'. 2. Divide 'a' by 'b' and obtain the remainder, 'r'. 3. If 'r' is equal to zero, then 'b' is the GCD of 'a' and 'b'. Terminate the algorithm. 4. If 'r' is not zero, replace 'a' with 'b' and 'b' with 'r'. 5. Repeat steps 2-4 until the remainder 'r' becomes zero. Example 1. Compute gcd(803, 154). Solution: gcd(803, 154) = gcd(154, 33) since 803 = 154 · 5 + 33 gcd(154, 33) = gcd(33, 22) since 154 = 33 · 4 + 22 gcd(33, 22) = gcd(22, 11) since 33 = 22 · 1 + 11 gcd(22, 11) = gcd(11, 0) since 22 = 11 · 1 + 0 gcd(11, 0) = 11 Hence gcd(803, 154) = 11. PAMANTASAN NG CABUYAO |NUMBER THEORY 33 Example 2 Express gcd(803, 154) as a linear combination of 803 and 154. Solution: 11 = 33 + 22 · (−1) = 33 + (154 − 33 · 4) · (−1) = 154 · (−1) + 33 · 5 = 154 · (−1) + (803 − 154 · 5) · 5 = 803 · 5 + 154 · (−26) THE FUNDAMENTAL THEOREM OF ARITHMETIC The Fundamental Theorem of Arithmetic Theorem: Every positive integer greater than 1 can be represented as a product of primes: N = p₁k₁ * p₂k₂ * p₃k₃ *... * pₙkₙ where p₁, p₂, p₃,..., pₙ are prime numbers, and k₁, k₂, k₃,..., kₙ are positive integers representing the exponents. The prime factorization of a number provides a unique representation of that number as a product of primes. For example: 24 = 23 * 3 56 = 23 * 7 105 = 3 * 5 * 7 This theorem is fundamental in number theory and has several important consequences. Some of these consequences include: 1. Unique Factorization: The Fundamental Theorem of Arithmetic guarantees that the prime factorization of a number is unique. This property is useful in various mathematical applications, such as finding common factors, simplifying fractions, and solving equations. 2. GCD and LCM: The prime factorization of two numbers allows us to find their greatest common divisor (GCD) and least common multiple (LCM). By identifying the common prime factors and the highest powers of those primes, we can determine the GCD and LCM of two numbers. 3. Divisibility Tests: The prime factorization of a number can be used to determine if it is divisible by another number. If the prime factors of the divisor are present in the prime factorization PAMANTASAN NG CABUYAO |NUMBER THEORY 34 Puzzle on Euclidean 1. Puzzle: "Arrange the numbers 18, 24, 36, and 48 in a sequence using the Euclidean algorithm. Start with any two numbers and apply the algorithm until you find the GCD. Repeat this process until all four numbers are used. What is the final sequence?" 2. Puzzle: Alice and Bob are playing a game. Alice picks two positive integers, 'a' and 'b', and tells Bob their GCD. Bob's task is to determine the original numbers 'a' and 'b' using the Euclidean algorithm. Can you help Bob solve the puzzle? PAMANTASAN NG CABUYAO |NUMBER THEORY 35 SUMMARY Prime numbers are integers with no divisors other than 1 and themselves, while the GCD represents the largest common divisor of two or more numbers. The Euclidean algorithm is used to efficiently find the GCD, and the Fundamental Theorem of Arithmetic states that every positive integer has a unique prime factorization. These concepts are fundamental in number theory and have various applications in mathematics and other fields. which are often called the set of natural or counting KEY TERMS numbers. Prime Numbers Greatest Common Divisor Euclidean Algorithm Composite Number Prime Factorization POSTTEST Directions: Fill in the blank with the letter corresponding to your answer. 1. A prime number is a number that: a) Is divisible by 1 b) Has exactly two divisors c) Is divisible by 2 d) Is a perfect square 2. Which of the following is a prime number? a) 12 b) 17 c) 20 d) 25 3. The GCD of two prime numbers is always: a) 1 b) Their sum c) Their product d) The larger number 4. What is the GCD of 24 and 36? a) 12 b) 6 c) 24 d) 36 5. The Euclidean algorithm is used to find the: a) Least Common Multiple b) Prime factorization c) Greatest Common Divisor d) Prime number sequence 6. Which step is repeated in the Euclidean algorithm? a) Addition b) Subtraction c) Multiplication d) Division PAMANTASAN NG CABUYAO |NUMBER THEORY 36 7. The Euclidean algorithm terminates when: a) The remainder becomes zero b) The quotient becomes zero c) The remainder is equal to the divisor d) The quotient is equal to the dividend 8. The Fundamental Theorem of Arithmetic states that: a) Every number is divisible by 1 b) Every number is divisible by 2 c) Every number can be expressed as a product of primes d) Every number is a prime number 9. The prime factorization of 48 is: a) 24 * 32 b) 2 * 3 * 5 c) 23 * 3 d) 22 * 32 10. Which number has a prime factorization of 2 3 * 5 * 7? a) 70 b) 112 c) 140 d) 168 11. The GCD of two co-prime numbers is always: a) 1 b) 2 c) Their sum d) Their product 12. The prime factorization of 64 is: a) 23 * 4 b) 26 c) 24 * 4 d) 25 * 3 13. The GCD of two numbers is always: a) Their product b) The larger number c) The smaller number d) A common divisor 14. The LCM of two prime numbers is always: a) 1 b) A prime number c) Their sum d) Their product 15. The GCD of two numbers can be found using: a) The Prime Factorization method b) The Euclidean Algorithm c) The Multiplication method d) The Division method REFERENCES Burton, David M. (2011) Elementary Number Theory (7th edition). New York, USA: The McGraw-Hill Companies, Inc Hill, Richard Michael (2018) Introduction to Number Theory ( Essential Textbooks in Mathematics). London, Europe: World Scientific Publishing Europe Ltd. Jim Hefferon and Edwin Clark. (2003). Elementary number theory - saint michael’s college. Elementary Number Theory. https://joshua.smcvt.edu/numbertheory/book.pdf PAMANTASAN NG CABUYAO |NUMBER THEORY 37 Jones, Gareth Michael (1998) Elementary Number Theory. Southampton, UK: Springer-Verlag London. Rosen, K.H. (2011). Elementary number theory and its applications (6th Edition). Boston, USA: Pearson. Tattersal, J.J. (1999). Elementary number theory in nine chapters. New York, USA: Cambridge University Press. ANSWERS TO EXERCISES Page 29 Pretest 1. a 6. c 2. b 7. d 3. b 8. c 4. c 9. d 5. d 10. c Page 30 Pre-Activity 1. 40 & 81 3. 39 2. none 4. 32 Page 34 Activity 1 1. 18, 24, 36, 48 2. Yes. a' = 6 and b' = 6 Page 35 Post-Test 1. a 6. d 11. a 2. b 7. a 12. b 3. a 8. c 13. d 4. a 9. c 14. b 5. c 10. c 15. b PAMANTASAN NG CABUYAO |NUMBER THEORY 38