# Number Theory Homework

Problem H1
Prime numbers have exactly two factors. Now find some numbers that have exactly three factors. What do these numbers have in common? That is, how would you categorize these numbers? Look for numbers with three factors, not three prime factors. The number itself and 1 are always factors, so there must be exactly one other factor. When we factor a number, we typically get two distinct factors. How could we get only one new factor?

Problem H2
There is a way to find the number of factors of a positive integer without writing out all the factors, and it requires finding the prime factorization first. This problem will help you discover that rule.

Go through the table, and list all the factors for each number. Then in the table enter the total number of factors (including the number itself and 1). Look for patterns, and try to write a general rule for the number of factors for any integer. Problem H3
A number is called a perfect number if the sum of all of its factors is equal to twice the value of the number. What are the two smallest perfect numbers?

Problem H4
An abundant number is one in which the sum of its factors is greater than twice the number. A deficient number is one in which the sum of its factors is less than twice the number. Which numbers less than 25 are abundant and which are deficient?

Problem H5
You have seen that every prime number greater than 3 is one less or one more than a multiple of 6. It is also true that every prime number greater than 2 is one more or one less than a multiple of 4. How would you prove this fact?

### Solutions

Problem H1
The number must be a square; otherwise, it would have an even number of factors. Try some square numbers:

1: 1 (one factor)
4: 1, 2, 4 (three factors)
9: 1, 3, 9 (three factors)
16: 1, 2, 4, 8, 16 (five factors)
25: 1, 5, 25 (three factors)
36: 1, 2, 3, 4, 6, 9, 12, 18, 36 (nine factors)
49: 1, 7, 49 (three factors)

The first four numbers with this property are 4, 9, 25, and 49. The next three after that are 121, 169, and 289. In general, the way to categorize these numbers is that they are squares of the prime numbers.

Problem H2

Here is the completed table: Problem H3

So, for 72 = 23 • 32, the exponents are 3 and 2. One more than each exponent gives the numbers 4 and 3. The number of factors is 4 • 3, or 12.

For this problem and the next, we need the following list of numbers and the sum of their factors: Problem H4
The first two perfect numbers are 6 and 28, since their factors add to exactly twice the value of the number.

Refer to the table for Problem H3.
Abundant numbers less than 25 are 12, 18, 20, and 24. All others (besides 6, which is perfect) are deficient.

Problem H5
You could use a sieve-like table similar to the one used in this session: You can see that the first and the third columns get crossed out immediately. Thus, the prime numbers will be located in the second or fourth columns.

Alternatively, you could argue that every number is either zero, one, two, or three more than a multiple of 4. If a number is zero or two more, then it can’t be prime (unless it’s 2), for such numbers are divisible by 2. This leaves “one more” and “three more” as the only choices. Three more than a multiple of 4 is the same as one less than the next multiple of 4. So again, the prime numbers will be located in the columns that are one more or one less than a multiple of 4.