Primality verification • 2026 number theory
| Property | Value | Description |
|---|---|---|
| Primality | Prime | Whether number is prime |
| Divisors | 1, 17 | All positive divisors |
| Sum of Divisors | 18 | 1 + 17 = 18 |
| Digit Sum | 8 | 1 + 7 = 8 |
| Category | Information | Classification |
|---|---|---|
| Prime Classification | Regular Prime | Type of prime number |
| Modulo 4 | 1 (mod 4) | Remainder when divided by 4 |
| Special Form | None | Fermat, Mersenne, etc. |
| Prime Gap | 2 | Distance to next prime |
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
Various algorithms exist for testing primality, each with different computational complexities:
Where n is the number being tested and k is the number of iterations for probabilistic tests.
Primes can be classified in various ways:
Which of the following numbers is NOT prime?
The answer is C) 33. To determine if a number is prime, we check for divisibility by primes up to its square root.
For 33: √33 ≈ 5.7, so we check divisibility by 2, 3, and 5.
33 ÷ 3 = 11, so 33 = 3 × 11. Therefore, 33 is composite.
For verification: 23, 29, and 37 are all prime numbers.
This question tests the fundamental understanding of prime numbers. The key insight is that we only need to check for divisibility by primes up to the square root of the number. This is because if a number n has a factor greater than √n, it must also have a corresponding factor less than √n. For 33, we quickly find that it's divisible by 3, confirming it's not prime. This demonstrates the importance of understanding divisibility rules and factorization in primality testing.
Prime Number: Natural number > 1 with exactly two divisors (1 and itself)
Composite Number: Natural number > 1 with more than two divisors
Divisor: Number that divides another number evenly
• Check divisibility up to √n only
• Only check prime divisors
• 1 is neither prime nor composite
• Quick check: Even numbers > 2 are not prime
• Sum of digits divisible by 3 means number is divisible by 3
• End in 5 means divisible by 5 (except 5 itself)
• Forgetting that 1 is not prime
• Checking unnecessary divisors beyond √n
• Not testing all primes up to √n
Find the prime factorization of 84 and calculate the sum of its prime factors.
We start by dividing 84 by the smallest prime numbers:
84 ÷ 2 = 42
42 ÷ 2 = 21
21 ÷ 3 = 7
7 is prime
So: 84 = 2² × 3 × 7
Prime factors: 2, 2, 3, 7
Sum of prime factors: 2 + 2 + 3 + 7 = 14
This problem demonstrates the systematic approach to prime factorization. We repeatedly divide by the smallest prime divisor until we reach 1. The prime factorization is unique (Fundamental Theorem of Arithmetic). The sum of prime factors is sometimes used in number theory problems. This process helps understand the internal structure of composite numbers and is foundational for many cryptographic algorithms.
Prime Factorization: Expressing a number as product of primes
Fundamental Theorem: Every integer has unique prime factorization
Canonical Form: Prime factorization with exponents
• Always divide by smallest prime first
• Use exponents for repeated factors
• Result is unique for each number
• Use divisibility rules to find factors quickly
• Write factors in ascending order
• Check your work: multiply factors back together
• Including 1 in prime factorization
• Forgetting to use exponents for repeated factors
• Not continuing until all factors are prime
Two twin primes have a sum of 60. Find the two primes and verify they are indeed twin primes.
Let the twin primes be p and p+2.
Then: p + (p + 2) = 60
2p + 2 = 60
2p = 58
p = 29
So the twin primes are 29 and 31.
Verification: 29 + 31 = 60 ✓
Check if both are prime: 29 is prime, 31 is prime ✓
Difference: 31 - 29 = 2 ✓
The twin primes are 29 and 31.
This problem combines algebra with number theory. Twin primes are pairs of primes that differ by exactly 2. The solution uses algebra to find the primes and then verifies both are actually prime numbers. This demonstrates how different mathematical concepts can be combined to solve problems. Twin primes are of particular interest in number theory, with the Twin Prime Conjecture being one of the oldest unsolved problems in mathematics.
Twin Primes: Primes that differ by 2 (e.g., 3,5 or 11,13)
Twin Prime Conjecture: Infinitely many twin primes exist
Prime Pair: Two primes with specific relationship
• Twin primes always differ by 2
• Both numbers in pair must be prime
• First twin prime is always odd (except 3,5)
• Represent twin primes as p and p+2
• Always verify both numbers are prime
• Remember 3,5 is the only twin prime with 3
• Forgetting to verify both numbers are prime
• Not checking that difference is exactly 2
• Missing the special case of 3,5
The prime gap is the difference between two consecutive prime numbers. Find the first occurrence of a prime gap of 6 and identify the two consecutive primes.
We examine consecutive primes and their differences:
2, 3 (gap: 1)
3, 5 (gap: 2)
5, 7 (gap: 2)
7, 11 (gap: 4)
11, 13 (gap: 2)
13, 17 (gap: 4)
17, 19 (gap: 2)
19, 23 (gap: 4)
23, 29 (gap: 6) ← Found!
The first occurrence of a prime gap of 6 is between 23 and 29.
This problem explores prime gaps, which are fundamental in understanding the distribution of prime numbers. The sequence of prime gaps reveals patterns in how primes are distributed. The first gap of 6 occurs between 23 and 29, meaning there are 5 consecutive composite numbers (24, 25, 26, 27, 28) between these two primes. This demonstrates that prime gaps can vary significantly and that primes become less frequent as numbers increase.
Prime Gap: Difference between consecutive primes
Consecutive Primes: Primes with no other primes between
Prime Distribution: How primes are spread across integers
• Prime gaps are always even (except gap of 1)
• Gaps tend to increase as numbers get larger
• Arbitrarily large gaps exist
• List primes in order to find gaps
• Remember gaps are always even (except first)
• Use prime tables or calculators for large numbers
• Forgetting to check consecutive primes only
• Miscounting the gap size
• Not starting from beginning of sequence
Which of the following is a Mersenne prime?
A Mersenne prime is a prime number that is one less than a power of two: M = 2^p - 1 where p is also prime.
Let's check each option:
A) 15 = 2⁴ - 1 = 16 - 1 = 15. But 15 = 3×5, so not prime.
B) 31 = 2⁵ - 1 = 32 - 1 = 31. 31 is prime, and 5 is prime. ✓
C) 63 = 2⁶ - 1 = 64 - 1 = 63. But 63 = 7×9, so not prime.
D) 127 = 2⁷ - 1 = 128 - 1 = 127. 127 is prime, and 7 is prime. ✓
Both B and D are Mersenne primes, but the question asks for "a" Mersenne prime. The answer is B) 31.
This question introduces Mersenne primes, which are primes of the form 2^p - 1 where p is also prime. It's important to note that not all numbers of the form 2^p - 1 are prime even when p is prime. For example, 2¹¹ - 1 = 2047 = 23×89, which is not prime. Mersenne primes are significant in number theory and are often the largest known primes due to efficient testing algorithms like the Lucas-Lehmer test.
Mersenne Prime: Prime of the form 2^p - 1 where p is prime
Lucas-Lehmer Test: Efficient primality test for Mersenne numbers
Large Primes: Mersenne primes often hold records
• Mersenne primes have form 2^p - 1
• Exponent p must also be prime
• Not all 2^p - 1 are prime when p is prime
• Check if exponent is prime first
• Verify the resulting number is also prime
• Mersenne primes are rare but large
• Assuming all 2^p - 1 are prime when p is prime
• Not checking if exponent is prime
• Forgetting to verify the result is prime
A natural number greater than 1 that has no positive divisors other than 1 and itself. Formula: n > 1 ∧ ∀d ∈ ℕ, (d | n) ⇒ (d = 1 ∨ d = n).
Common algorithms: Trial division (O(√n)), Fermat test (probabilistic), Miller-Rabin (probabilistic), AKS (deterministic polynomial).
For large numbers, use probabilistic tests like Miller-Rabin for efficiency.
Q: Why is 1 not considered a prime number?
A: 1 is excluded from primes to preserve the Fundamental Theorem of Arithmetic: "every integer greater than 1 has a unique prime factorization." If 1 were prime, factorizations wouldn't be unique (e.g., 6 = 2×3 = 1×2×3 = 1²×2×3).
Q: What's the largest known prime number?
A: As of 2023, it's 2^82,589,933 - 1 (24,862,048 digits). Discovered by Patrick Laroche through GIMPS project. Mersenne primes (2^p - 1) often hold records due to efficient testing algorithms.