Elementary Number Theory

 Class Topics 1 Euclidean Algorithm 2 Prime Factorization 3 Change of base 4 Binary Numbers 5 Exponent and factorial 6 Permutation

Elementary Number Theory Package

Euclidean Algorithm

The goal is to find the greatest common divisor of two numbers x and y. This can be written as

GCD(x, y).

Cases:

1)      If x = y, then GCD(x, y) = x.

2)      If x = 0 and y != 0, then GCD(x, y) = y

3)      If x > y and y evenly divides x, then GCD(x, y) = y

4)      If x > y and y doesn’t evenly divide x, follow the below steps. Each step will be written out as an equation.

1. a)       x = y*p1 + r1
2. b)      y = r1*p2  + r2
3. c)       r1 = r2*p3 + r3

Once you reach the line where there is a remainder of 0, you are done. The GCD(x, y) will be the remainder from the previous line. Here is an example:

GCD(55, 15)

55 = 15*3 + 10

15 = 10*1 + 5

10 = 5*2

Videos:

Problems:

1)      Use the Euclidean Algorithm to find the following:

1.       GCD(237, 279)
2.       GCD(89, 225)
3.       GCD(507, 182)

Prime Factorization

The goal is to be able to represent a number as the product of prime numbers, with each number raised to a power. To teach this concept, I suggest using smaller numbers (<=10000). It might also be a good idea to review prime numbers and give a few examples. To find the prime factorization of a number x > 1, you can do the following:

1)      Start with 2. If 2 divides x, divide by 2. Whatever the result is, attempt to divide this by 2. Divide by 2 as many times as you can, which is as long as it evenly divides the result. If n is the number of times that 2 divides x, write down 2^n. If 2 doesn’t divide x evenly at all, don’t write down anything.

2)      Move onto 3. Use whatever result is left after dividing by 2, which can be x itself if x isn’t divided evenly by 2, and divide this result by 3. Continue to divide by 3 until you cannot divide by 3. If n is the number of times that the result from the first step can be divided by 3, write down 3^n.

3)      Move onto 5….

Once the result found from one of the steps is 1 or you are attempting to divide by a number greater than the square root of the result of one of the steps and the number doesn’t divide the result, you are finished. Write down whatever result is left if it is not 1. Every prime and the power that it is raised to will be part of one product. Below are some examples:

Find the prime factorization of 8:

1)      Divide 8 by 2. The result is 4

2)      Divide 4 by 2. The result is 2.

3)      Divide 2 by 2. The result is 1.

8 is therefore 2^3.

Find the prime factorization of 49:

1)      Divide 49 by 2. Since 2 doesn’t divide 49 evenly, pass on 49.

2)      Divide 49 by 3. Since 3 doesn’t divide 49 evenly, pass on 49.

3)      Divide 49 by 5. Since 5 doesn’t divide 49 evenly, pass on 49.

4)      Divide 49 by 7. The result is 7.

5)      Divide 7 by 7. The result is 1.

49 is therefore 7^2.

Find the prime factorization of 56:

1)      Divide by 2. The result is 28.

2)      Divide by 2. The result is 14.

3)      Divide by 2. The result is 7.

4)      Divide by 2. Since 2 doesn’t divide 7 evenly, pass on 7.

5)      Divide by 3. Since 3 doesn’t divide 7 evenly and 3 is greater than the square root of 7, you are done.

56 is therefore (2^3)*7.

Videos:

Alternative way of learning to find the prime factorization of a number:

Prime number use:

Problems:

1)      Find the prime factorization of 925

2)      Find the prime factorization of 2999

3)      Suppose you are given two numbers x and y. How can you use the result of the Euclidean Algorithm as a means to find the prime factorization of each?

Change of Base

Using the same general rule from the last section on binary numbers, we can convert to base-10 from another base and from base-10 to another base. Note that for some numbers – base-16, for instance – you need more symbols than the traditional 10 digits. Below are the digits for base-16:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Notice that there are 16 digits. Each of the letters represents the following:

A = 10

B = 11

C = 12

D = 13

E = 14

F = 15

For any number in a specific base, the number can be written as the sum of multiples of the base’s powers to get to base-10.

Here is an example from base-10:

95893 = 9*(10^4) + 5*(10^3) + 8*(10^2) + 9*(10^1) + 3*(10^0)

Suppose that you are given 6270 and told that the number is in base-7. How can you write it as a sum that is in base-10?

6*(7^3) + 2*(7^2) + 7*(7^1) + 0*(7^0)  = 2205

Now suppose that you are given 1205 in base-10 and you want to convert the number into base-8. How do you convert the number?

Start by finding the highest power of 8 that goes into 1205. It’s 512, which is 8^3. Based on the exponent, the number will have 4 spaces:

_ _ _ _

How many times does 512 go into 1205? 2 times. So the leftmost space will have 2 in it:

2 _ _ _

Now subtract: 1205 – 1024 = 181

Does 8^2 go into 181? 64 goes into it 2 times, so we put another 2 down:

2 2 _ _

Again, subtract: 181 – 128 = 53

Does 8 ^ 1 go into 53? 8 goes into it 6 times, so we put a 6 down:

2 2 6 _

Subtract again to get 5. This is what you will put in the last space:

2 2 6 5

Now we check our work:

2*(8^3) + 2*(8^2) + 6*(8^1) + 5*(8^0) = 1024 + 128 + 48 + 5 = 1205

Finally, let’s try one from base-16 to base-10 and one from base-10 to base-16. By the way, we also use the word “hexadecimal” to refer to numbers in base-16.

Suppose you are given FA92 and are told that it’s in base-16. How do you convert it into base-10?

We know that the number has 4 digits, so the highest exponent will be 3.

So we write it as

15*(16^3) + 10*(16^2) + 9*(16^1) + 2 = 61440 + 2560 + 144 + 2 = 64146

Now suppose that we want to convert 956 in base-10 into base-16. How do you do it?

Start by finding the highest power of 16 that goes into 956. It’s 256, which is 16^2. Since the highest exponent is 2, the number will have 3 digits.

_ _ _

256 will go into 956 3 times, so we write a 3 in the leftmost space:

3 _ _

Subtract: 956 – 768 = 188

Does 16^1 go into 188? Yes, 11 times. So we put a B in the next spot:

3 B _

Subtract: 188 – 176 = 12

We put a C in the last spot:

3 B C

Now we check our work:

3*(16^2) + 11*(16) + 12 = 768 + 176 + 12 = 956

Videos:

Binary Numbers

The goal is to teach ways of translating from base-10 numbers to another base or from another base to base-10. But this section will be for binary numbers.

Start by showing how any base-10 number can be written as the sum of powers of ten, with each power of ten multiplied by a number. Below are some examples:

525 = 5*(10^2) + 2*(10^1) + 5*(10^0)

1039 = 1*(10^3) + 0*(10^2) + 3*(10^1) + 9*(10^0)

Now start with binary numbers. Suppose you are given the following binary number:

10110

The digits represent the following, starting from the right:

0 -> (2^0) * 0 = 0

1 -> (2^1) * 1 = 2

1 -> (2^2) * 1 = 4

0 -> (2^3) * 0 = 0

1 -> (2^4)*1 = 16

Summing all of the results, we get 22. So 10110 is the binary representation for the base-10 number 22.

Now move onto translating a base-10 number to a binary number. Suppose the number is 75.

First, find the largest exponent n for 2 such that 2^n <= 75. In this case it’s 6. The binary number will therefore have 7 digits. Below are blanks we will fill in for the number:

_ _ _ _ _ _ _

We know that the first number will be a 1, so after finding the highest exponent for 2 and getting the number of spaces, we fill in the leftmost digit:

1 _ _ _ _ _

1 * (2 ^ 6) = 64, so subtract 64 from 75 to get 11.

The next space available is for 2^5. Since 32 > 11, we put a 0 there.

1 0 _ _ _ _ _

The next space available is for 2^4. Again, 16 > 11, so we fill in the blank with a 0.

1 0 0 _ _ _ _

2^3 < 11, so we put a 1 in the next space and subtract 8 from 11.

1 0 0 1 _ _ _

2^2 > 3, so we put a 0 in the next space.

1 0 0 1 0 _ _

2^1 < 3, so we put a 1 in the next space and subtract 2 from 1

1 0 0 1 0 1 _.

Finally, 2^0 = 1 = 1, so we put a 1 in the last space.

1 0 0 1 0 1 1.

Therefore, 1 0 0 1 0 1 1 is the binary representation of 75.

The general rule is the following:

Find the largest exponent n for 2 such that 2^n is less than or equal to the base-10 number x you are converting from. Whatever this exponent is, add 1 to this exponent, and this will be the number of spaces needed for the binary number. If there are n spaces, the leftmost space will be for 2^(n-1). The next space to the right will be for 2^(n -2), and so on. The rightmost space will be for 2^0. Start with the leftmost space, which is for the highest power of 2 less than or equal to x. Subtract 2^(n-1) from x. The difference is y. Is 2^(n-2) <= y? If so, put a 1 in this space, and subtract 2^(n-2) from y. If not, put a 0 in this space and move on. Continue in this way, checking if the power of 2 is less than or equal to whatever is left of the original number, and putting a 1 in the space if it is and subtracting or putting a 0 in the space.

Videos:

Problems:

1)      Convert the following binary number into its base-10 representation: 10110110

2)      Convert the following base-10 number into its binary representation: 1056

3)      Can you figure out a way to add two binary numbers without converting them into base-10?

Exponents and Factorials

Rules for exponents:

1)      (x^i) * (x^j) = (x^(i + j))

Examples:

(3^4) * (3^5) = 3^9

(2^5) * (2^6) * (2^7) = 2^18

2)      (x^i)^j = (x^(i*j))

Examples:

(2^2)^3 = 2^6

((3^3)^4)^5) = 3^60

3)      (x^i)/(x^j) = x^(i-j)

Examples:

(2^10)/(2^3) = 2^7

(3^7)/(3^6) = 3

4)      (x^i) * (y^i) = (x*y)^i

Examples:

(2^5) * (3^5) = 6^5

(2^8) * (7^8) * (11^8) = 154^8

Factorials:

The factorial of a non-negative number n, denoted by n!, is the product of n * (n-1) * …1. Note that 0! = 1.

Examples:

5! = 5*4*3*2*1 = 120

7! = 7*6*5*4*3*2*1 = 5040

Videos:

Why is 0! = 1?

Step-by-step solution of a problem:

Problems:

1)      Solve the following:

1. a)       How can you rewrite (3^5) * (3^7) * (3^8) as a single number raised to a power?
2. b)      Rewrite the following as a single number raised to a power: ((2^8)/(2^5)) * 2^10

2)      Evaluate the following: (5!/3!) * 4!

3)      Evaluate the following: ((9!^10)/(9!^8))/9!

Permutations

A permutation of a set of symbols is one of potentially many rearrangements of the symbols where the order of the symbols matters. For example, consider the letters a, b, and c. One permutation of these letters is (b, a, c), another is (a, b, c), and another is (c, a, b).

If you are given x unique symbols, there are x! permutations of the symbols if the permutations are of length x. Here is an example using the numbers 1, 2, and 3. For this example, I am omitting commas and not putting the numbers in parentheses. Also, I am ordering the permutations according to how the numbers are ordered in the sequence of natural numbers.

123

132

213

231

312

321

Notice that since there are 3 numbers, there are 3! permutations.

If the symbols making up a set of permutations can be ordered, then the permutations themselves can be ordered. For instance, consider the numbers 1, 2, 3, and 4. We want to order the permutations using all 4 numbers.

The permutations in ascending order – starting from the smallest in the order to the largest – are the following:

1234    2134    3124    4123

1243    2143    3142    4132

1324    2314    3214    4213

1342    2341    3241    4231

1423    2413    3412    4312

1432    2431    3421    4321

Notice that there are 24 numbers in the list, or 4! numbers (Remember: the number of permutations of a set of n symbols is n! if the permutations have a length of n). The number in the leftmost space for each permutation changes after every 6 times, or 3!. The number in the space next to it changes after every 2 times, or 2!. The number in the space next to it changes after every 1 time, or 1!. Finally, the number in the rightmost space changes after every 1 time, or 0!. In general, if there are n symbols in a permutation taken from a set of n symbols and the symbols can be ordered, for the ordered list of permutations for these symbols, you know that the leftmost space will change after every (n-1)! times. The number to its right will change every (n-2)! times, and so on, all the way to 0! times for the rightmost space.

There are cases, however, when you want to get the permutations of a set of symbols, where each permutation has a length smaller than the total number of symbols. For example, consider the set of numbers 1, 2, 3, and 4. We want the list of permutations of length 2 using all of the symbols. They are below:

12        21        31        41

13        23        32        42

14        24        34        43

In this case, there are not 4! permutations. Instead, there are only 12. There is a formula for finding the total number of permutations of length x from a set with n symbols, where x < n and x > 0. This formula is the following:

n!/(n – x)!

Here are some examples:

How many permutations of length 3 are there from the set containing 1, 2, 3, 4, and 5?

5!/(5 – 3)! = 5!/2! = (5*4*3*2*1)/(2*1) = 60

How many permutations of length 4 are there from the set containing 0, 1, 5, 6, 7, 8, and 10?

7!/(7-4)! = 7!/3! = (7*6*5*4*3*2*1)/(3*2*1) = 840

Videos:

Another explanation