The Central Idea
Every positive integer greater than \(1\) belongs to one of two categories: prime or composite.
A positive integer \(p>1\) is prime when its only positive divisors are
\[ \boxed{1\text{ and }p}. \]A positive integer \(n>1\) is composite when it has at least one positive divisor other than \(1\) and itself.
Prime Numbers
Consider \(7\). Its positive divisors are
\[ 1,\qquad7. \]There are no others. Therefore,
\[ \boxed{7\text{ is prime}}. \]The same is true of numbers such as
\[ 2,\ 3,\ 5,\ 11,\ 13,\ 17,\ 19. \]Composite Numbers
Consider \(12\). Its positive divisors are
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 12. \]Because \(12\) has positive divisors other than \(1\) and \(12\),
\[ \boxed{12\text{ is composite}}. \]Equivalently, \(12\) can be written as a product of two smaller positive integers:
\[ 12=3\cdot4. \]A Composite Number Has a Nontrivial Factorization
For an integer \(n>1\), the following two ideas are equivalent:
- \(n\) is composite;
- \(n=ab\) for positive integers \(a,b\) satisfying \(1
For example,
\[ 35=5\cdot7, \]so \(35\) is composite.
Why \(1\) Is Neither Prime nor Composite
The number \(1\) has only one positive divisor:
\[ 1. \]A prime number must have exactly two positive divisors, and a composite number must have a nontrivial factorization into smaller positive integers.
Therefore,
\[ \boxed{1\text{ is neither prime nor composite}}. \]Why the Definition Starts Above \(1\)
Excluding \(1\) from the prime numbers is essential to the structure of arithmetic.
If \(1\) were considered prime, then inserting arbitrary factors of \(1\) would destroy the useful uniqueness of prime factorizations. For example,
\[ 6=2\cdot3 \]could also be written as
\[ 6=1\cdot2\cdot3 \]or with any number of additional factors of \(1\).
Treating \(1\) separately preserves a clean arithmetic structure.
The Number \(2\) Is Special
The positive divisors of \(2\) are
\[ 1,\qquad2. \]Therefore \(2\) is prime.
It is also the only even prime number. Every even integer greater than \(2\) is divisible by \(2\) and therefore has a positive divisor other than \(1\) and itself.
\[ \boxed{2\text{ is the only even prime}}. \]All Other Primes Are Odd
If \(p>2\) were even, then
\[ 2\mid p. \]Since \(2\neq1\) and \(2\neq p\), that would make \(p\) composite.
Therefore every prime greater than \(2\) is odd.
The converse is not true: many odd numbers are composite. For example,
\[ 9=3\cdot3. \]Small Prime Numbers
The prime numbers below \(50\) are
\[ \boxed{ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47 }. \]Memorizing a short initial list can make later factorization and divisibility work faster, but primality should ultimately be justified from the divisor structure.
Examples of Composite Numbers
The first several composite positive integers are
\[ \boxed{ 4,\ 6,\ 8,\ 9,\ 10,\ 12,\ 14,\ 15,\ 16,\ 18,\ 20,\ldots }. \]Each has at least one nontrivial factor pair:
\[ 4=2\cdot2,\qquad 9=3\cdot3,\qquad 15=3\cdot5. \]Prime Does Not Mean Odd
Oddness and primality are different properties.
The number \(21\) is odd, but
\[ 21=3\cdot7. \]Therefore,
\[ \boxed{21\text{ is composite}}. \]Being odd only tells us that \(2\) is not a divisor.
Prime Does Not Mean “Not Divisible by \(2\), \(3\), or \(5\)”
A number may avoid several small divisors and still be composite.
For example,
\[ 77=7\cdot11. \]The number \(77\) is not divisible by \(2\), \(3\), or \(5\), but it is still composite.
A valid primality test must rule out every possible nontrivial divisor that could occur.
Factor Pairs Reveal Compositeness
To prove that a positive integer \(n>1\) is composite, it is enough to find one nontrivial factor pair.
For example,
\[ 91=7\cdot13. \]Therefore,
\[ \boxed{91\text{ is composite}}. \]We do not need to list every divisor once one nontrivial factorization has been found.
How Far Must We Test?
Suppose \(n\) is composite. Then
\[ n=ab \]
for positive integers \(a,b\) with \(1
At least one of \(a\) or \(b\) must satisfy
Otherwise, if both were greater than \(\sqrt n\), then
which is impossible.
The Square-Root Primality Test
To determine whether \(n>1\) is prime, it is enough to test possible prime divisors up to
\[ \sqrt n. \]If none of those primes divides \(n\), then \(n\) is prime.
This dramatically reduces the amount of checking required.
Why We Only Need to Test Prime Divisors
Suppose a composite number such as \(12\) divides \(n\). Then every prime factor of \(12\) also divides \(n\).
Since
\[ 12=2^2\cdot3, \]divisibility by \(12\) cannot occur without divisibility by \(2\) and \(3\).
Therefore, when testing primality, composite trial divisors do not provide fundamentally new information beyond their prime factors.
Example: Is \(37\) Prime?
Compute
\[ \sqrt{37}\approx6.08. \]The prime numbers not exceeding \(6.08\) are
\[ 2,\qquad3,\qquad5. \]The number \(37\) is not divisible by \(2\), \(3\), or \(5\).
Therefore,
\[ \boxed{37\text{ is prime}}. \]Example: Is \(91\) Prime?
Compute
\[ \sqrt{91}\approx9.54. \]The prime trial divisors up to \(9.54\) are
\[ 2,\ 3,\ 5,\ 7. \]Since
\[ 91=7\cdot13, \]we find a nontrivial divisor. Therefore,
\[ \boxed{91\text{ is composite}}. \]Example: Is \(97\) Prime?
Since
\[ \sqrt{97}\approx9.85, \]test the primes
\[ 2,\ 3,\ 5,\ 7. \]The number \(97\) is not divisible by any of them.
Therefore,
\[ \boxed{97\text{ is prime}}. \]Example: A Larger Composite Number
Determine whether \(221\) is prime.
Since
\[ \sqrt{221}\approx14.87, \]possible prime divisors to test are
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13. \]We find
\[ 221=13\cdot17. \]Therefore,
\[ \boxed{221\text{ is composite}}. \]Using Divisibility Tests First
Before performing trial division, apply quick divisibility tests.
For example, consider \(513\). The digit sum is
\[ 5+1+3=9. \]Since \(9\) is divisible by \(3\),
\[ 3\mid513. \]Therefore,
\[ \boxed{513\text{ is composite}}. \]Ending Digits Can Eliminate Cases Quickly
For integers greater than \(5\):
- an even final digit proves divisibility by \(2\);
- a final digit of \(0\) or \(5\) proves divisibility by \(5\).
Therefore, any prime greater than \(5\) must end in
\[ \boxed{1,\ 3,\ 7,\text{ or }9}. \]This is a necessary condition, not a sufficient one. For example,
\[ 21,\ 27,\ 39,\ 49 \]all end in one of these digits but are composite.
Primes Greater Than \(3\) Have a Useful Form
Every integer can be placed into one of the residue patterns
\[ 6k,\ 6k+1,\ 6k+2,\ 6k+3,\ 6k+4,\ 6k+5. \]If a prime is greater than \(3\), it cannot be divisible by \(2\) or \(3\). That leaves only
\[ \boxed{6k-1\text{ or }6k+1}. \]Again, this is necessary but not sufficient. For example,
\[ 25=6(4)+1 \]but \(25\) is composite.
Prime Squares
The square of a prime number is always composite.
If \(p\) is prime, then
\[ p^2=p\cdot p. \]Since \(p>1\), the number \(p\) is a nontrivial divisor of \(p^2\).
Thus
\[ \boxed{p^2\text{ is composite}}. \]Examples include
\[ 4,\ 9,\ 25,\ 49,\ 121. \]A Number Can Have Many Divisors
Composite numbers vary greatly in how many positive divisors they have.
For example,
\[ 14 \]has the positive divisors
\[ 1,\ 2,\ 7,\ 14, \]while
\[ 24 \]has
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 8,\ 12,\ 24. \]Both are composite even though their divisor counts differ.
Prime Numbers Are Building Blocks
Composite numbers can be broken into smaller integer factors. Repeating that process eventually produces prime factors.
For example,
\[ 60=6\cdot10 \]and then
\[ 6=2\cdot3,\qquad10=2\cdot5. \]Thus
\[ 60=2\cdot2\cdot3\cdot5. \]The next lessons will develop this factorization structure systematically.
The Fundamental Theorem of Arithmetic
One of the central facts of elementary number theory is that every integer greater than \(1\) can be expressed as a product of prime numbers, and that this factorization is unique apart from the order of the factors.
For example,
\[ 84=2^2\cdot3\cdot7. \]This theorem explains why prime numbers function as the multiplicative building blocks of the positive integers.
There Are Infinitely Many Prime Numbers
The prime numbers never end.
A classical argument begins by assuming there are only finitely many primes,
\[ p_1,p_2,\ldots,p_n. \]Form the number
\[ N=p_1p_2\cdots p_n+1. \]None of the listed primes divides \(N\) evenly, because division by any \(p_i\) leaves remainder \(1\). Thus \(N\) is prime or has a prime divisor not on the list.
Either possibility contradicts the claim that the list contained every prime. Therefore,
\[ \boxed{\text{there are infinitely many primes}}. \]The Sieve Idea
One practical way to find many small primes is to begin with a list of integers greater than \(1\) and repeatedly remove multiples of known primes.
Starting with \(2\):
- keep \(2\) and remove larger multiples of \(2\);
- keep \(3\) and remove larger multiples of \(3\);
- keep \(5\) and remove larger multiples of \(5\);
- continue through the required square-root bound.
The numbers that remain are prime. This method is known as the Sieve of Eratosthenes.
Common Error: Calling \(1\) Prime
The number \(1\) has only one positive divisor.
A prime number must have exactly two distinct positive divisors:
\[ 1\text{ and itself}. \]Therefore,
\[ \boxed{1\text{ is not prime}}. \]Common Error: Calling Every Odd Number Prime
Odd numbers are merely numbers not divisible by \(2\).
For example,
\[ 45=5\cdot9. \]Thus \(45\) is odd and composite.
Common Error: Testing Divisors Too Far
To determine whether \(101\) is prime, it is unnecessary to test every integer below \(101\).
Since
\[ \sqrt{101}\approx10.05, \]only the prime divisors
\[ 2,\ 3,\ 5,\ 7 \]need to be checked.
Common Error: Stopping Before the Square-Root Bound
Consider \(143\).
It is not divisible by \(2\), \(3\), \(5\), or \(7\). But
\[ \sqrt{143}\approx11.96, \]so \(11\) must also be tested.
In fact,
\[ 143=11\cdot13. \]Therefore \(143\) is composite.
Common Error: Assuming a Large Number Is Probably Composite
Size alone does not determine primality.
Some relatively large integers are prime, while much smaller integers may be composite.
The classification must be based on divisibility, not appearance or size.
A Reliable Procedure for Classifying an Integer
- Confirm that the integer is greater than \(1\).
- Apply quick divisibility tests for small primes such as \(2\), \(3\), and \(5\).
- Compute or estimate \(\sqrt n\).
- Test prime divisors no larger than \(\sqrt n\).
- If one divides \(n\), classify \(n\) as composite.
- If none divides \(n\), classify \(n\) as prime.
Example: Full Primality Workflow
Determine whether \(173\) is prime.
First,
\[ \sqrt{173}\approx13.15. \]The prime trial divisors are
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13. \]The number \(173\) is odd, its digit sum is \(11\), it does not end in \(0\) or \(5\), and direct checks show it is not divisible by \(7\), \(11\), or \(13\).
Therefore,
\[ \boxed{173\text{ is prime}}. \]Example: Full Composite Workflow
Determine whether \(187\) is prime.
Since
\[ \sqrt{187}\approx13.67, \]test the prime divisors
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13. \]We find
\[ 187=11\cdot17. \]Therefore,
\[ \boxed{187\text{ is composite}}. \]Practice 1: Classify Small Integers
Classify each number as prime, composite, or neither:
\[ 1,\qquad2,\qquad9,\qquad17,\qquad21. \]Practice 2: Find a Nontrivial Factor
Show that
\[ 77 \]is composite by finding a nontrivial factorization.
Practice 3: Apply the Square-Root Bound
Which prime divisors must be tested to determine whether
\[ 113 \]is prime?
Practice 4: Test Primality
Determine whether
\[ 113 \]is prime.
Practice 5: Detect a Composite Number Quickly
Determine whether
\[ 2{,}475 \]is prime or composite without extensive trial division.
Practice 6: Another Primality Test
Determine whether
\[ 127 \]is prime.
Practice 7: Find the Hidden Factor
Determine whether
\[ 169 \]is prime or composite.
Practice 8: Explain the Logic
Why is it sufficient to test possible divisors only up to \(\sqrt n\) when determining whether \(n\) is prime?
Practice 9: Prime Form
A student says:
“Every number of the form \(6k+1\) is prime.”
Give a counterexample.
Practice 10: Prime or Composite?
Classify
\[ 211. \]Practice Answers
Practice 1
\[ \boxed{ 1:\text{ neither},\quad 2:\text{ prime},\quad 9:\text{ composite},\quad 17:\text{ prime},\quad 21:\text{ composite} }. \]Practice 2
\[ 77=7\cdot11. \]Therefore,
\[ \boxed{77\text{ is composite}}. \]Practice 3
Since
\[ \sqrt{113}\approx10.63, \]test
\[ \boxed{2,\ 3,\ 5,\ 7}. \]Practice 4
The number \(113\) is not divisible by \(2\), \(3\), \(5\), or \(7\). Since these are all primes not exceeding \(\sqrt{113}\),
\[ \boxed{113\text{ is prime}}. \]Practice 5
The number ends in \(5\), so
\[ 5\mid2475. \]Since \(2475>5\),
\[ \boxed{2475\text{ is composite}}. \]Practice 6
Since
\[ \sqrt{127}\approx11.27, \]test
\[ 2,\ 3,\ 5,\ 7,\ 11. \]None divides \(127\), so
\[ \boxed{127\text{ is prime}}. \]Practice 7
\[ 169=13^2. \]Therefore,
\[ \boxed{169\text{ is composite}}. \]Practice 8
If \(n=ab\) is composite and both \(a\) and \(b\) were greater than \(\sqrt n\), then
\[ ab>\sqrt n\sqrt n=n, \]which is impossible. Therefore at least one nontrivial factor must be no larger than \(\sqrt n\).
Practice 9
One counterexample is
\[ 25=6(4)+1. \]But
\[ 25=5^2, \]so \(25\) is composite.
Practice 10
Since
\[ \sqrt{211}\approx14.53, \]test
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13. \]None divides \(211\). Therefore,
\[ \boxed{211\text{ is prime}}. \]What to Remember
- A prime number is a positive integer greater than \(1\) with exactly two positive divisors.
- A composite number is a positive integer greater than \(1\) with a nontrivial factorization.
- The number \(1\) is neither prime nor composite.
- The number \(2\) is the only even prime.
- Every prime greater than \(2\) is odd, but not every odd number is prime.
- To prove compositeness, one nontrivial factor is enough.
- To test primality, it is enough to test prime divisors up to \(\sqrt n\).
- Prime numbers serve as the multiplicative building blocks of the positive integers.
The most important distinction is structural: prime numbers cannot be decomposed into smaller positive integer factors, while composite numbers can.
Where We Go Next
Prime and composite numbers describe the basic factor structure of integers. The next lesson, Greatest Common Divisors and Least Common Multiples, compares the divisibility structure of two or more integers and develops systematic ways to identify their largest shared divisor and smallest shared positive multiple.