Problem 34 - Discrete Mathematics with Applications

Question

Let \(p\) be a prime and \(n \in \mathbb{N} .\) Prove that \(p^{n}\) is not a perfect number. (Hint: Prove by contradiction.)

Step-by-Step Solution

Answer

Assuming that \(p^n\) is a perfect number, we find the sum of its divisors using the sum of a geometric series: \(\frac{p^{n+1} - 1}{p - 1}\). We then equate this sum to \(p^n\) and simplify the equation to obtain \(p^{n+1} - p^n = 1\). This equation presents a contradiction since the left side is divisible by p, while the right side is not divisible by any prime number. Thus, we have proved by contradiction that \(p^n\) is not a perfect number.

Step 1: Assume p^n is a perfect number

Let's suppose that \(p^n\) is a perfect number, where p is prime and n is an integer. This means that the sum of its divisors, excluding itself, must be equal to \(p^n\).

Step 2: Find the sum of divisors of p^n

For any prime number p, its divisors are 1, p, p^2, ..., p^n. Now, we can find the sum of these divisors using the formula for the sum of a geometric series: Sum of divisors \(= 1 + p + p^2 + ... + p^n = \frac{p^{n+1} - 1}{p - 1}\)

Step 3: Compare the sum of divisors to p^n

Since \(p^n\) is assumed to be a perfect number, the sum of its divisors must be equal to \(p^n\): \(p^n = \frac{p^{n+1} - 1}{p - 1}\) Multiply both sides by (p - 1): \(p^n (p - 1) = p^{n+1} - 1\) It can be simplified as: \(p^{n+1} - p^n = 1\)

Step 4: Analyze the resulting equation for contradiction

Notice that the left side of the equation, \(p^{n+1} - p^n\), is a difference of two powers of a prime number, which means it is at least divisible by p. However, the right side of the equation is 1, which is not divisible by any prime number. This is a contradiction. Therefore, our initial assumption that \(p^n\) is a perfect number is incorrect. We have proved by contradiction that \(p^n\) is not a perfect number.

Key Concepts

Understanding Prime Numbers

Prime numbers are the building blocks of mathematics. They are the natural numbers greater than 1 that have no positive divisors other than 1 and themselves. For instance, the numbers 2, 3, 5, 7, 11, and 13 are all primes because they cannot be divided evenly by any other number (other than 1 and the number itself).

Prime numbers are crucial in various fields of mathematics and science, including cryptography, number theory, and more. The fundamental theorem of arithmetic states that every natural number greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This shows the central role of primes in the structure of the number system.

Understanding the nature of prime numbers is imperative when solving problems related to divisibility, such as determining if a number is a perfect number, as seen in the original exercise. Furthermore, working with primes often involves proving certain properties, sometimes using methods like 'proof by contradiction,' which is suggested in the given exercise hint.

Summing Up A Geometric Series

A geometric series is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example, in the series 1, 2, 4, 8, ..., the common ratio is 2.

The sum of a geometric series can be found using the formula: \[\frac{a_1 \times (1 - r^n)}{1 - r}\] where \(a_1\) is the first term, \(r\) is the common ratio, and \(n\) is the number of terms. When applied to the divisors of a power of a prime number, as in our exercise, the series’ sum formula provides a quick way to determine the sum of all divisors, which is necessary when exploring perfect numbers.

Understanding how to compute the sum of a geometric series is a valuable skill, particularly when dealing with series and sequences, and it becomes fundamental when assessing the perfection of a number.

The Proof by Contradiction Method

Reaching a Logical Impasse

Proof by contradiction is a logical method used to establish the validity of a proposition by showing that assuming the opposite leads to an absurd result, an inconsistency, or a contradiction. The process typically starts with the assumption that the statement to be proved is false. If this assumption inevitably leads to a contradiction, then the initial statement must be true.

The technique often involves a keen observation that the supposition, when followed through to its logical conclusion, does not align with well-known principles or facts. In our given exercise, the assumption that a power of a prime number is a perfect number led us to a logical impasse, discrediting the initial assumption and corroborating that the power of a prime is indeed not perfect.

By sharpening skills in proof by contradiction, students can tackle a wide array of mathematical problems, ranging from simple algebraic equations to complex theorems, and appreciate the underlying structures of mathematical reasoning.