023. Number theory

Question: `q001. There are 13 questions in this assignment.

The number 12 is evenly divisible by 1, 2, 3, 4, 6, and 12. We therefore say that 1, 2, 3, 4, 6 and 12 are the divisors of 12.

Each of these divisors can be multiplied by another to get 12. e.g., 2 * 6 = 12, 1 * 12 = 12, 3 * 4 = 12.

List the numbers from 2 to 20 and list all the divisors of each.

Your solution:

Confidence Assessment:

Given Solution:

The divisors of 2 are 1 and 2.

The divisors of 3 are 1 and 3.

The divisors of 4 are 1, 2 and 4.

The divisors of 5 are 1 and 5.

The divisors of 6 are 1, 2, 3 and 6.

The divisors of 7 are 1 and 7.

The divisors of 8 are 1, 2, 4, hence 8.

The divisors of 9 are 1, 3 and 9.

The divisors of 10 are 1, 2, 5 and 10.

The divisors of 11 are 1 and 11.

The divisors of 12 are 1, 2, 3, 4, 6, 12.

The divisors of 13 are 1 and 13.

The divisors of 14 are 1, 2, 7 and 14.

The divisors of 15 are 1, 3, 5 and 15.

The divisors of 16 are 1, 2, 4, 8 and 16.

The divisors of 17 are 1 and 17.

The divisors of 18 are 1, 2, 3, 6, 9 and 18.

The divisors of 19 are 1 and 19.

The divisors of 20 are 1, 2, 4, 5, 10 and 20.

Self-critique (if necessary):

Self-critique Rating:

Question: `q002. Some of the numbers you listed have exactly two divisors. Which are these?

Your solution:

Confidence Assessment:

Given Solution:

The numbers with exactly two divisors are

• 2, with divisors 1 and 2

• 3, with divisors 1 and 3

• 5, with divisors 1 and 5

• 7, with divisors 1 and 7

• 11, with divisors 1 and 11

• 13, with divisors 1 and 13

• 17, with divisors 1 and 17

• 19, with divisors 1 and 19

Self-critique (if necessary):

Self-critique Rating:

Question: `q003. These numbers with exactly two divisors are called prime numbers. List the prime numbers between 21 and 40.

Your solution:

Confidence Assessment:

Given Solution:

Every counting number except 1 has at least 2 divisors, since every counting number is divisible by itself and by 1. Therefore if a counting number is divisible by any number other than itself and 1 it has more than 2 divisors and is therefore prime.

• Since 21 is divisible by 3, it has more than 2 divisors and is not prime.

• Since 22 is divisible by 2, it has more than 2 divisors and is not prime. Since this will be the case for all even numbers, we will not consider any more even numbers as candidates for prime numbers.

• Since 23 is not divisible by any number except itself and 1, it has exactly 2 divisors and is prime.

• Since 25 is divisible by 5, it has more than 2 divisors and is not prime.

• Since 27 is divisible by 3, it has more than 2 divisors and is not prime.

• Since 29 is not divisible by any number except itself and 1, it has exactly 2 divisors and is prime.

• Since 31 is not divisible by any number except itself and 1, it has exactly 2 divisors and is prime.

• Since 33 is divisible by 3, it has more than 2 divisors and is not prime.

• Since 35 is divisible by 5, it has more than 2 divisors and is not prime.

• Since 37 is not divisible by any number except itself and 1, it has exactly 2 divisors and is prime.

• Since 39 is divisible by 3, it has more than 2 divisors and is not prime.

The primes between 21 and 40 are therefore 23, 29, 31 and 37.

Self-critique (if necessary):

Self-critique Rating:

Question: `q004. The primes through 40 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37.

Twin primes are consecutive odd numbers which are both prime.

Are there any twin primes in the set of primes through 40?

Your solution:

Confidence Assessment:

Given Solution:

17 and 19 are consecutive odd numbers, and both are prime. The same is true of 5 and 7, and of 11 and 13.

Self-critique (if necessary):

Self-critique Rating:

Question: `q006. We can prove that 89 is prime as follows:

• 89 is odd and is hence not divisible by 2.

• If we divide 89 by 3 we get a remainder of 2 so 89 is not divisible by 3.

• Since 89 is not divisible by 2 it cannot be divisible by 4 (if we could divide it evenly by 4 then, since 2 goes into 4 we could divide evenly by 2; but as we just saw we can't do that).

• Since 89 doesn't end in 0 or 5 it isn't divisible by 5.

• If we divide 89 by 7 we get a remainder of 5 so 89 is divisible by 7.

• Since 89 isn't divisible by 2 it isn't divisible by 8, and since it isn't this will by 3 it isn't divisible by 9.

At this point it might seem like we have a long way to go--lots more numbers to before get to 89. However it's not as bad as it might seem.

For example once we get past 44 we're more than halfway to 89 so the result of any division would be less than 2, so there's no way it could be a whole number. So nothing greater than 44 is a candidate, and we won't have to test any number greater than 44.

We can in fact to even better than that. If we went even as far as dividing by 10, it's easy to see that the quotient would be less than 10:

• since 10 * 10 is greater than 89, it follows that 89 / 10 must be less than 10.

So if 10 or anything greater than 10 was going to divide 89, in the result would be one of the numbers we have already tried.  Since we were unsuccessful in our previous attempts, there is no reason to test any number which is 10 or greater.

It follows that after trying without success to divide 89 by all the numbers through 9.  (And we didn't really have to try 9 anyway because 9 is divisible by 3 which we already checked, so we are now sure that 89 is indeed prime).

What is the largest number you would have to divide by to see whether 119 is prime?

Your solution:

Confidence Assessment:

Given Solution:

After we get to 7, we don't have to try 8, 9 or 10 because we've already checked numbers that divide those numbers (that is, we checked 2 and it didn't work so neither 8 nor 10 could possibly work, and 3 didn't work either so we know 9 won't).

The next number we might consider trying is 11. However 11 * 11 = 121, which is greater than 119.  So any quotient we get by dividing by 11, or by any number greater than 11, would be less than 11.  Since we have already have eliminated the possibility that any number less than 11 is a divisor, division by 11 or any greater number is unnecessary.

So 7 is the largest number we would have to try.

Self-critique (if necessary):

Self-critique Rating:

Question: `q007. Precisely what numbers would we have to try in order to determine whether 119 is prime?

Your solution:

Confidence Assessment:

Given Solution:

We would have to check whether 119 was divisible by 2, by 3, by 5 and by 7.

We wouldn't have to check 4 or 6 because both are divisible by 2, which we would have already checked.

Self-critique (if necessary):

Self-critique Rating:

Question: `q008. Is 119 prime?

Your solution:

Confidence Assessment:

Given Solution:

119 isn't divisible by 2 because 119 is odd. 119 isn't divisible by 3 because 120 is. 119 isn't divisible by 5 because 119 doesn't end in 5.

119 is, however, divisible by 7, as you can easily verify.

Self-critique (if necessary):

Self-critique Rating:

Question: `q009. We can 'break down' the number 54 into the product 2 * 27, which can further be broken down to give us 2 * 3 * 9, which can be broken down one more step to give us 2 * 3 * 3 * 3.

We could have broken down 54 into different way as 6 * 9, which could have been broken down into 6 * 3 * 3, which can be broken down one more step to give us 2 * 3 * 3 * 3.

No matter how we break 54 down into factors, the process ends with a single factor 2 and 3 repetitions of the factor 3.

Break down each of the following in this manner, until it is not possible to break it down any further:

63, 36, and 58.

Your solution:

Confidence Assessment:

Given Solution:

We see that

63 = 9 * 7 = 3 * 3 * 7,

36 = 9 * 4 = 3 * 3 * 4 = 3 * 3 * 2 * 2, which we rearrange in increasing order of factors as 2 * 2 * 3 * 3, and

58 = 2 * 29.

Self-critique (if necessary):

Self-critique Rating:

Question: `q010. The results that we obtained in the preceding exercise are called the 'prime factorizations' of the given numbers. We have broken the numbers down until we are left with just prime numbers. Why is it that this process always ends with prime numbers?

Your solution:

Confidence Assessment:

Given Solution:

We break the numbers down until they can't be broken down any further. If any number in the product is not prime, then it has more than two factors, which means it has to be divisible by something other than itself or 1. In that case we would have to divide it by that number or some other. So the process cannot end until all the factors are prime.

Self-critique (if necessary):

Self-critique Rating:

Question: `q011. Find the prime factorization of 819, then list all the factors of 819.

Your solution:

Confidence Assessment:

Given Solution:

We start by dividing by 3. We get 819 = 3 * 273 = 3 * 3 * 91.

Since 91 isn't divisible by 3, we need to 5 and 7, after which the next prime is 11 and which we will not need to try since 11 * 11 > 91.

91 isn't divisible by 5 since it doesn't end in 0 or 5, but it is divisible by 7 with quotient 13. So 91 = 7 * 13.

Thus we have 819 = 3 * 3 * 91 = 3 * 3 * 7 * 13.

In addition to 1 and 819, the factors of 819 will include the following:

• 3, 7, 13, which are all of the prime factors

• 3 * 3 = 9, 3 * 7 = 21, 3 * 13 = 39 and 7 * 13 = 91, which are all of the possible products of two of the prime factors. 

Note that 3 * 3 is OK, since the prime factorization 3 * 3 * 7 * 13 includes two 3's, but neither 7 * 7 nor 13 * 13 is OK, since the prime factorization includes only one of each of these numbers.

• 3 * 3 * 7 = 63, 3 * 3 * 13 = 117, and 3 * 7 * 13 = 273, which are all of the possible products of three of the prime factors.

Self-critique (if necessary):

Self-critique Rating:

Question: `q012. List all the factors of 168.

Your solution:

Confidence Assessment:

Given Solution:

First we find the prime factorization:

168 = 2 * 84 = 2 * 2 * 42 = 2 * 2 * 2 * 21 = 2 * 2 * 2 * 3 * 7. This number has several factors:

• We have the prime factors themselves: 2, 3, 7.

• We have the products of exactly 2 of the prime factors: 2 * 2 = 4, 2 * 3 = 6, 2 * 7 = 14, 3 * 7 = 21.

• We have products of exactly 3 of the prime factors: 2 * 2 * 2 = 8; 2 * 2 * 3 = 12; 2 * 2 * 7 = 28; 2 * 3 * 7 = 42.

• We have products of exactly 4 of the prime factors: 2 * 2 * 2 * 3 = 24; 2 * 2 * 2 * 7 = 56; and 2 * 2 * 3 * 7 = 84.

• And we finally have 168 itself (which is the product of all 5 prime factors) and 1.

Note that using exponential notation we can write the prime factorizations of 168 as 2^3 * 3^1 * 7^1. We have 2 as a factor 3 times, and 3 and 7 each one time. If we add 1 to the power of each prime factor we get 3 + 1 = 4, 1 + 1 = 2 and 1 + 1 = 2. If we then multiply the resulting numbers together we get 4 * 2 * 2 = 16. Note that there are 16 factors of 168.

This process always works: if we add 1 to the power of each prime factor then multiply the results we get the total number of factors of the original number.