A prime number is a whole number greater than \(1\) that has exactly two positive divisors:
\(1\) and itself. A composite number is a whole number greater than \(1\) that has at least one additional divisor.
1. Prime numbers
An integer \(p\) is prime if
\[
\begin{aligned}
p &> 1
\end{aligned}
\]
and its only positive divisors are
\[
\begin{aligned}
1 \quad \text{and} \quad p.
\end{aligned}
\]
Examples of prime numbers are
\[
\begin{aligned}
2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ldots
\end{aligned}
\]
The number \(2\) is prime and is the only even prime.
2. Composite numbers
A number \(n\) is composite if it can be written as a product of two smaller positive integers:
\[
\begin{aligned}
n &= ab,
\end{aligned}
\]
where
\[
\begin{aligned}
1
For example:
\[
\begin{aligned}
91 &= 7\cdot 13.
\end{aligned}
\]
Therefore, \(91\) is composite.
3. Why \(1\) is neither prime nor composite
The number \(1\) has exactly one positive divisor: \(1\).
A prime number must have exactly two positive divisors, and a composite number must have more than two.
Therefore:
\[
\begin{aligned}
1 &\text{ is neither prime nor composite.}
\end{aligned}
\]
4. Trial division
Trial division tests whether \(n\) is divisible by smaller integers.
If any divisor \(d\) satisfies
\[
\begin{aligned}
n \bmod d &= 0,
\end{aligned}
\]
then \(d\) divides \(n\), so \(n\) is composite.
A basic trial division test checks
\[
\begin{aligned}
d=2,\ 3,\ 5,\ 7,\ldots
\end{aligned}
\]
and stops when the divisor limit is reached.
5. Why checking up to \(\sqrt n\) is enough
If \(n\) is composite, then
\[
\begin{aligned}
n &= ab
\end{aligned}
\]
for some factors \(a\) and \(b\), with \(1
\[
\begin{aligned}
a>\sqrt n,\quad b>\sqrt n
\quad &\Rightarrow \quad
ab>n.
\end{aligned}
\]
That is impossible if \(ab=n\). Therefore, at least one factor must be less than or equal to \(\sqrt n\).
So, if no integer divisor from \(2\) through \(\lfloor\sqrt n\rfloor\) divides \(n\), then \(n\) is prime.
6. Example: proving \(97\) is prime
To test \(97\), calculate:
\[
\begin{aligned}
\sqrt{97} &\approx 9.85.
\end{aligned}
\]
So it is enough to test possible prime divisors up to \(9\):
\[
\begin{aligned}
2,\ 3,\ 5,\ 7.
\end{aligned}
\]
Check divisibility:
\[
\begin{aligned}
97 \bmod 2 &\ne 0,\\
97 \bmod 3 &\ne 0,\\
97 \bmod 5 &\ne 0,\\
97 \bmod 7 &\ne 0.
\end{aligned}
\]
No divisor is found, so
\[
\begin{aligned}
\boxed{97\text{ is prime}.}
\end{aligned}
\]
7. Example: proving \(91\) is composite
To test \(91\), calculate:
\[
\begin{aligned}
\sqrt{91} &\approx 9.54.
\end{aligned}
\]
Check divisibility by small primes:
\[
\begin{aligned}
91 \bmod 2 &\ne 0,\\
91 \bmod 3 &\ne 0,\\
91 \bmod 5 &\ne 0,\\
91 \bmod 7 &= 0.
\end{aligned}
\]
Since \(7\) divides \(91\),
\[
\begin{aligned}
91 &= 7\cdot 13.
\end{aligned}
\]
Therefore:
\[
\begin{aligned}
\boxed{91\text{ is composite}.}
\end{aligned}
\]
8. Prime factorization
If a number is composite, it can be written as a product of primes.
For example:
\[
\begin{aligned}
360 &= 2^3\cdot3^2\cdot5.
\end{aligned}
\]
Prime factorization is useful because it completely describes the multiplicative structure of a positive integer.
9. Deterministic and probabilistic tests
Trial division is deterministic: if it checks all necessary divisors up to \(\sqrt n\), the result is exact.
For very large numbers, trial division becomes slow.
Faster tests, such as the Miller–Rabin primality test, use modular arithmetic to check whether a number behaves like a prime.
Miller–Rabin is often probabilistic when random bases are used, but it can be deterministic over certain size ranges if enough known bases are tested.
This calculator keeps the student explanation grounded in exact trial division and uses the Miller–Rabin option as a fast preview/check.
10. Common divisibility shortcuts
| Divisor |
Shortcut |
Example |
| \(2\) |
The number is even. |
\(48\) is divisible by \(2\). |
| \(3\) |
The digit sum is divisible by \(3\). |
\(123\): \(1+2+3=6\), so \(123\) is divisible by \(3\). |
| \(5\) |
The number ends in \(0\) or \(5\). |
\(95\) is divisible by \(5\). |
| \(10\) |
The number ends in \(0\). |
\(120\) is divisible by \(10\). |
11. Formula summary
| Concept |
Rule or formula |
Meaning |
| Prime |
\(p>1\), divisors only \(1,p\) |
Exactly two positive divisors |
| Composite |
\(n=ab\), \(1<a,b<n\) |
Has a proper factor |
| Trial limit |
\(\lfloor\sqrt n\rfloor\) |
Largest divisor that must be tested |
| Divisibility |
\(n\bmod d=0\) |
\(d\) divides \(n\) |
| Prime conclusion |
No divisor \(2\le d\le\sqrt n\) |
The number is prime |
| Composite conclusion |
Some divisor \(d\) is found |
The number is composite |
12. Common mistakes
- Counting \(1\) as a prime number.
- Forgetting that \(2\) is prime.
- Assuming every odd number is prime.
- Testing divisors beyond \(\sqrt n\) unnecessarily.
- Calling a number composite without showing at least one proper divisor.
- Forgetting that a single divisor is enough to prove compositeness.
Key idea: to prove a number is composite, find one proper divisor. To prove it is prime, show no divisor exists up to \(\sqrt n\).
