Number Theory Notes PDF

Preview

Summary

7.0 introduction number theory notes...

Description

Number Theory Section 2.1: Prime Factorizations A Natural Number is a counting number: 0,1,2,3,… An integer number is a counting number or its corresponding negatives: …, -3, -2, -1, 0, 1, 2, 3, … Decimals or fractions are not integers. Definition: a is a multiple of b if there is an integer c such that a=b*c (that means, a is the result of multiplying b by an integer) Examples: 12 is a multiple of 4 because 12=4*3 (in this case, a=12, b=4, c=3). 22 is a multiple of 11 because 22=11*2 13 is not a multiple of 3 because there is no integer that multiplied by 3 gives 13 as a result. When 3 is multiplied by 4, the result is 12 and when 3 is multiplied by 5, the result is 15. Definition: We say that b divides a (notation: b|a) if a is multiple of b. Examples: 4 divides 12 (4|12) because 12 is a multiple of 4. 11 divides 22 (11|22) because 22 is a multiple of 11. 3 does not divide 13 because 13 is not a multiple of 3.

Note: “Divides” only means that a number is a multiple of another one, and it is not asking for a result. It is a true/false statement. Definition: A prime number is a positive integer that can be divided evenly only by two positive integers: 1 and itself. Some prime numbers: 2,3,5,7,11,13,17,19,23,… Definition: A composite number is a positive integer that can be divided by three or more positive integers (or the number has three or more divisors). Examples: 4 is composite since it can be divided by 1, 2, and 4. 12 is composite because its divisors are 1, 2, 3, 4, 6, and 12. Note: 1 is not a prime number, nor a composite number. The Fundamental Theorem of Arithmetic: Any positive integer greater than 1 can be expressed as a multiplication of only prime numbers. The process to find this multiplication of prime numbers is called prime factorization or prime decomposition. Example: 12 can be expressed as the multiplication 2*2*3. 2 and 3 are prime numbers. 2*6 is not a prime decomposition of 12 because 6 is not a prime number, and it can be decomposed further. 3*4 is not a prime decomposition of 12 since 4 is not a prime number.

Note: If a number is repeated in the multiplication, it can be expressed with exponents. For example, since 2 appears twice in the prime decomposition of 12, we can write it as 12 = 22*3. How to find the prime decomposition of large numbers: Divide the number by the smallest possible prime number. Then divide the result of the division by the smallest possible prime number. Repeat the process until the result is 1. Collect the prime numbers found in the process. Example: Find the prime decomposition of 60. Number Prime Result 60 2 30 60 can be divided by 2, which is the smallest prime number 30 2 15 60 divided by 2 is 30. Divide 30 by the smallest prime number 15 3 5 3 is the smallest prime number that divides 15 5 5 1 Since 5 is prime, it can only be divided by 5. Since the result is 1, the process is completed. Prime decomposition of 60: 60=22*3*5 Greatest Common Divisor (GCD): The largest integer that divides the given numbers. Example: 12 can be divided by 1,2,3,4,6, and 12. 18 can be divided by 1,2,3,6,9,18. The largest positive integer that divides both 12 and 18 is 6. That means, GCD(12,18)=6.

How to find the GCD of large numbers: Use prime decomposition, and determine the prime numbers that are common. Divide only by integers that are divisors of the given numbers at the same time. Example: Find GCD(60, 90) Number 1 60 30 10 2

Number 2 90 45 15 3

Prime 2 Both numbers are divisible by 2 3 Both numbers are divisible by 3 5 Both numbers are divisible by 5 2 and 3 do not have common divisors. Stop here.

Therefore: GCD(60,90) = 2*3*5 = 30 If the prime decomposition is given, select the common prime numbers with the lowest exponent. Example: Find the GCD of the following numbers: 68,343,750 = 2*37*56 1,350,000 = 24*33*55 2, 3, and 5 are common prime numbers, so they appear in the GCD. Find the smallest exponent for each prime number: 21 is the smallest exponent for 2, 33 is the smallest exponent for 3, and 55 is the smallest exponent for 5. Therefore, the GCD is: 2*33*55 (there is no need to multiply the numbers sometimes) Definition: Two numbers are relatively prime (or coprime) if they do not have common divisors, besides 1. Note: It does not mean the numbers are prime. It only means that the divisors of the numbers are different.

Example: 21 and 25 are relatively prime because the divisors of 21 are 1, 3, 7, and 21, and the divisors of 25 are 1, 5, and 25, and no divisors are common, besides 1. 21 is not a prime number and 25 is not a prime number. Example: 60 and 90 are not relatively prime because they both can be divided by 30. Least Common Multiple (LCM): The smallest integer that is a multiple of the given numbers. Example: Multiples of 12 are 12, 24, 36, 48, 60, 72, … Multiples of 18 are 18, 36, 54, 72, 90, … 36 and 72 are multiples of both 12 and 18. The smallest multiple is 36, so LCM(12,18) = 36. How to find the LCM of large numbers: Use prime decomposition, and divide by any prime number that divides either of the numbers. If a number is not divisible, do not change it. Stop when all numbers have been reduced to 1. Example: Find LCM(60,90) Number 1 60 30 15 5 5 1

Number 2 90 45 45 15 5 1

Prime 2 2 3 3 5

Both numbers are even 30 is even. Keep 45. Both numbers are divisible by 3 15 is divisible by 3. Keep the 5. Both numbers are divisible by 5

LCM(60,90) = 22*32*5 = 4*9*5 = 180 If the prime decomposition of the numbers is given, use every prime divisor with the greatest exponent. Example: Find LCM(3*57*76, 24*32*5*79) 2 is a divisor of the second number, so it needs to be included, with its exponent of 4. 3 is a common divisor. The largest exponent is 2, so 32 is part of the LCM. 5 is common and 7 is its largest exponent: 57. 7 is a common divisor and its largest exponent is 9: 79 LCM(3*57*76, 24*32*5*79) = 24*32*57*79

The Division Algorithm Integer Division: In a division 𝑎 ÷ 𝑏, a is the dividend and b is the divisor. The number of times b is in a is the quotient (usually represented with the letter q). If b*q is not equal to a, we need to add a number in order to get to a. This number is called the remainder, and it is usually represented with letter r. The remainder is always a number greater or equal to 0 and less than the divisor (0 ≤ r < b). This means the remainder is never a negative number. Example: In 23 ÷ 4, 23 is the dividend and 4 is the divisor. 4 is 5 times into 23, so 5 is the quotient. Since 4*5=20, we need to add 3 to get 23, so 3 is the remainder of the division. Notes: The quotient and the remainder in integer division are always integer numbers. This means decimals are not used in this process. If a division is performed in a calculator, the decimal found in a division is NOT the remainder. The Division Algorithm: represent the dividend as the multiplication of the divisor and the quotient, and add the remainder. Example: In 23 ÷ 4, 23 is the dividend. Represent 23 as 4*5+3, where 4 is the divisor, 5 is the quotient, and 3 is the remainder (23 = 4*5+3) Integer Division Operators: Div: Find the quotient of a division Example: 23 div 4 = 5 since the quotient of dividing 23 by 4 is 5. Mod: Find the remainder of the division:

Example: 23 mod 4 = 3 since the remainder of 23 divided by 4 is 3. Calculate: 16 div 5 = 93 div 9 = -112 div 9 = 17 mod 5 = 118 mod 9 = -105 mod 8 =

Modular Arithmetic Modular arithmetic means to perform common arithmetic operations (addition, subtraction, multiplication) using only remainders. More specifically, find the remainder of the result of the operation after dividing by m, when the result is greater than the divisor (the divisor appears after the word mod) Example: (10 mod 11) + (9 mod 11) = 19 mod 11 = 8 mod 11 Here, 19 is greater than 11, so divide 19 by 11. The quotient is 1 and the remainder of that division is 8. (the quotient is not used as part of the answer) Example: (10 mod 11)*(9 mod 11) = 90 mod 11 = 2 mod 11 Here, 90 is greater than 11, and when 90 is divided by 11, the quotient is 8 and the remainder is 2. 𝒁𝒏 represents the set of all the possible remainders when any number is divided by n. For example, in 𝑍*, the possible remainders are 0,1,2,3,4,5,6. Recall that a remainder is never equal or greater than the divisor. More specifically, 𝑍+ means “mod n”. Example: What is 5 times 7 in Z9? Multiply 5 times 7: 5*7 = 35. Then divide 35 by 9 and get the remainder: 9 is 3 times into 35; 9 times 3 is 27, so 8 needs to be added to get 35. The remainder is 8. Therefore, 5 times 7 in Z9 is 8. Example: What is 6+8 in Z4?

6+8 mod 4 = 14 mod 4 = 2 (The remainder after dividing 14 by 4 is 2) Example: Compute [56*25*38] mod 9 Divide each number by 9 and find the remainders: 56 mod 9 = 2 (6*9=54+2 = 56) 25 mod 9 = 7 (2*9=18+7 = 25) 38 mod 9 = 2 (4*9=36+2 = 38) Then, perform the operations to the results: [56*25*38] mod 9 = [2*7*2] mod 9 = 28 mod 9 Finally, simplify (find the remainder) mod 9: 28 mod 9 = 1 mod 9 (3*9 = 27+1 = 28) Note: When an expression contains an exponent, simplify the base of the exponent using mod, and afterwards apply the exponent to the result. For example, if you need to find 25176 mod 4, simplify 25 mod 4, which is 1. Now, the expression gets simplified as 1176 mod 4. 1 raised to any power is 1, so: 25176 mod 4 = 1176 mod 4 = 1 mod 4 = 1 Definition: Two numbers are congruent mod m if they have the same remainder after dividing by m. Example: 23 mod 4 = 3 and 47 mod 4 = 3. Therefore, 23 and 47 are congruent mod 4. Alternative definition: Two numbers are congruent mod m if the subtraction of the numbers is a multiple of m.

Example: 47-23 = 24. 24 is a multiple of 4. Therefore, 47 and 23 are congruent mod 4.

Number Representation The usual number system is the decimal system, which is also called base 10, since there are ten distinct digits: 0,1,2,3,4,5,6,7,8,9. Any number can be represented using a combination of those digits, no matter how long the number may be. For this section, numbers in decimal form are represented with a small 10 on the right side of the number. For example, (321)10 means that the number 321 is in decimal notation (or it is a decimal number) Computers use binary system (or base 2): Only two digits are used to represent any number, 1 and 0. Any number can be represented using only the digits 1 and 0, no matter how long the number is. Numbers in binary are represented with a small 2 on the right side of the number. For example, (11010101)2 means “the number 11010101 is a binary number”. Each digit in a number represents a power (exponent) of the base used. The exponents go in order, from right to left, starting at exponent 0. Multiply each position by the corresponding power, add the results, and you find the decimal representation of a number in any base. How to change from binary (base 2) to decimal: Write the binary number. Multiply each digit by a power 2, starting with 20 on the right side and moving to the left. Add the results. Example: Change (11010)2 to decimal Binary number 1 1 0 1 0 24 23 22 21 20 Powers of 2 Powers of 2 (after multiplying) 16 8 4 2 1

Multiply each digit by its corresponding power of 2, and add the results: 1*16 + 1*8 + 0*4 + 1*2 + 0*1 = 16+8+0+2+0 = 26. Therefore, (11010)2 = (26)10 It is possible to have any base for number representation. The main point is to use the base accordingly. For example, it is possible to represent numbers in base 3, 5, 8, or any other base. Example: Change (10021)3 to decimal Since the number is in base 3, each digit has to be multiplied by a power of 3: Base 3 number 1 0 0 2 1 34 33 32 31 30 Powers of 3 Powers of 3 (expanded) 81 27 9 3 1 Multiply each digit by its corresponding power of three and add the results: 1*81 + 0*27 + 0*9 + 2*3 + 1*1 = 81+0+0+6+1 = 88. Therefore, (10021)3 = (88)10 A decimal number can be changed to a number in any base. To do so, divide the number by the base, collect the remainder, and divide the quotient by the base. Repeat the process until the quotient is 1. Then, collect all the remainders and the last quotient, and write the numbers from the last one to the first digit found.

Example: Change 91 in decimal to binary Divide 91 by 2, get the quotient and remainder. Then divide the quotient by 2 and get the new quotient and remainder. Keep going until the quotient is 1. Number 91 45 22 11 5 2

Base 2 2 2 2 2 2

Quotient 45 22 11 5 2 1

Remainder 1 1 0 1 1 0

The first digit of the binary number is the last quotient (it is always a 1). Then, include all the other remainders, going from the bottom to the top. Therefore, 91 in decimal is 101 1011 in binary. Always try to represent a binary number in blocks of four digits, starting from the right side, to the left side. The reason for this is to find easily hexadecimal numbers. A number in any base can be changed to decimal by using the same method, but dividing by the corresponding base. Example: Change 1687 in decimal to base 7 Divide the number and the quotients by 7, and collect the remainders. Stop the process when the quotient is less than 7.

Number 1687 241 34

Base 7 7 7

Quotient 241 34 4

Remainder 0 3 6

Again, the first digit is the last quotient, which is less that the base (4 is less than 7), and then collect the remainders from the bottom to the top. We can say that (1687)10 = (4630)7. A hexadecimal number is a number base 16. Base 16 means that there are 16 digits to represent any number. Since we only have ten digits (0,1,2,3,4,5,6,7,8,9), we need to include new digits to complete the base. Those digits added are A, B, C, D, E, F. That means that base 16 uses the digits 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Since 16 = 24, we can see hexadecimal representation as a simplification of binary representation, where a set of four digits in binary can be represented as a single digit in hexadecimal. The following is a table of corresponding binary and hexadecimal values. Binary 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Hexadecimal 0 1 2 3 4 5 6 7 8 9

Decimal 0 1 2 3 4 5 6 7 8 9

1010 1011 1100 1101 1110 1111

A B C D E F

10 11 12 13 14 15

To change from binary to hexadecimal, divide the binary number in blocks of four digits from right to left, and then use the table to perform the change. If the block on left has less than four digits, complete with zeros on its left side. Example: Change 1011011001 in binary to hexadecimal First, divide the binary number into blocks of four digits, from right to left: 10 1101 1001. The block on left side contains only two digits, so include two zeros on the left to make the block four-digit long: 0010 1101 1001. Now, use the table to translate each block into hexadecimal: 0010 is 2 in hex, 1101 is D, 1001 is 9. Therefore, (0010 1101 1001)2 = (2D9)16 To change from hexadecimal to binary, use the table to translate each digit to its corresponding binary expression. Leave spaces between the blocks to read the number in an easier way.

Example: Change 8A5E from hexadecimal to binary: 8 is 1000 in binary A is 1010 5 is 0101 E is 1110 Therefore, (8A5E)16 = (1000 1010 0101 1110)2...