Theorem 1.3.2.
The Fundamental Theorem of Arithmetic
Any integer greater than \(1\) is either prime or it is a product of prime numbers. Furthermore, this prime decomposition is unique up to the order of the factors.
Section 1.3 Lesson Three
In the hustle and bustle of a typical college semester, with a lot of demands on your time and very little time to think, it becomes very easy to see each problem you solve as a small, isolated victory and then move on to the next challenge. This is understandable. Each problem you solve is a small victory and you’ve every right to be proud of it. But it is not isolated and it is a mistake to think that it is.
In his book How to Solve It the mathematician and teacher George Polya gave four steps for problem solving. The steps may be paraphrased as
- Understand the problem.
- Formulate a plan.
- Execute the plan.
- Reflect on what you’ve done.
This process is iterative. That is, once a plan is formulated and executed we often find that our plan was not up to the task. So we have to ask what went wrong, form a new plan and try again. This is the fourth step: Reflect on what you’ve done.
Almost everyone remembers this fourth step when their plan doesn’t work. After all, you’ve got to try again so you have to ask what went wrong. But it is all too easy to neglect that crucial fourth step when the plan succeeds. In that case, flush with success we usually move on to the next problem and start over from scratch.
This is a mistake. Having solved a problem is no reason to stop thinking about it.
That fourth step is at least as important when we have succeeded as when we have failed. Each time you solve a problem stop and ask yourself a few questions:
- Are there any easy consequences that follow from the result?
- How does it fit into the broader scheme of other problems you have solved?
- How might it be used in the future?
Also, notice the structure of the problem. Some assumptions had to be made. What were they? Were they all necessary? That is, did your solution use everything that was assumed? If not, you may have something considerably more general than it at first appears. What is that more general statement? Even if you used all of the assumptions, was that really necessary? Can you solve a similar problem with weaker assumptions?
Take a moment to pack all of these questions (and their answers) away in your mind so that when you see something similar in the future you will be reminded of it. Don’t solve any problem and then forget it and move on. The nature of mathematics is cumulative. Remember, you are not here to accumulate grade points. You are here to learn and understand the concepts and methods of mathematics, to gain “mathematical maturity.” Part of that maturation process is the accumulation of a body of facts (theorems), and techniques that can be used to prove new theorems (solve new problems).
This text has been written with the maturation process in mind. You will frequently find that the problems you solve today can be used to good effect in the ones you attempt tomorrow, but only if you remember them. So take a moment after you’ve solved each problem to think about how it fits into the patterns you already know. This is important enough to bear repeating: A problem, once solved, becomes a tool for solving subsequent problems!
The purpose of the following sequence of problems is to help you become accustomed to this notion (if you aren’t already). It is a progression of results about prime numbers. As you probably recall, a prime number is any integer greater than \(1\) whose only factors are itself and \(1\text{.}\) For example, \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(7\text{,}\) \(11\) are prime, while \(4\text{,}\) \(6\text{,}\) \(9\) are not. A major result about prime numbers is the following:
We will not prove this, but we will use it as a starting point to examine the following problems. As you do these problems, notice how subsequent problems make use of the previous results.
Notice that the notation \(p\,|a\) simply means that the integer \(p\) divides the integer \(a\) with no remainder.
Problem 1.3.3. Fermat’s Little Theorem, step 1.
Let \(p\) be a prime number and \(a, b\) positive integers such that \(p\, | (a\cdot b)\text{.}\) Show that \(p\,|a\) or \(p\,|b\text{.}\)
Hint.
If \(p\,|a\) then we are done. If not then notice that \(p\) is a prime factor of \(a\cdot b\text{.}\) What does the Fundamental Theorem of Arithmetic say about the prime factors of \(a\cdot b\) compared to the prime factors of \(a\) and \(b?\)
Problem 1.3.4. Fermat’s Little Theorem, step 2.
Let \(p\) be a prime number and let \(a_1, a_2, \ldots,
a_n\) be positive integers such that \(p\,|\left(a_1\cdot
a_2\cdot a_3\cdot\ldots\cdot a_n\right)\text{.}\) Show that \(p\,|a_k\) for some \(k\in\{1, 2, 3, \ldots, n\}\text{.}\)
Hint.
Use induction on \(n\) and the result of the previous problem.
Problem 1.3.5. Fermat’s Little Theorem, step 3.
Let \(p\) be a prime number and let \(k\) be an integer with \(1\le k\le p-1\text{.}\) Prove that \(p\left|{p \choose{}k}\right.\text{,}\) where \({p \choose{}k}\) is the binomial coefficient \(\frac{p!}{k!(p-k)!}\text{.}\)
Hint.
We know \(p\,|p\,!\text{,}\) so \(p\,|{p
\choose{}k}k!(p-k)!\text{.}\) How does the previous result apply?
We now have all the machinery in place to prove one of the really cool theorems from number theory.
Theorem 1.3.6.
Fermat’s Little Theorem
Let \(p\) be any prime number. Then \(p\,|(n^p-n)\) for all positive integers \(n\text{.}\)
Problem 1.3.7. Fermat’s Little Theorem.
Prove Fermat’s Little Theorem.
Hint.
Use induction on \(n\text{.}\) To get from \(n\) to \(n+1\text{,}\) use the binomial theorem on \((n+1)^p\text{.}\)
Fermat’s Little Theorem is the foundational basis for a number of results in number theory and encryption.
