Prime & Composite Numbers Explained

[EXEC: MICRO_CORE]

✖️ 1. Defining primes, composites, and understanding why 1 is neither

🔢 What Makes a Number Prime?

A prime number has exactly two divisors: 1 and itself.
A composite number has more than two divisors.
The number 1 is neither prime nor composite (it has only one divisor).
Every whole number greater than 1 is either prime or composite.
Examples: 2, 3, 5, 7 are prime; 4, 6, 8, 9 are composite.

Is 11 prime? Yes, because only 1 and 11 divide it evenly.

💡 Prime = exactly 2 doors in, composite = 3 or more doors, 1 = solo act.

[EXEC: DEEP_COMPUTE]

1. Defining primes, composites, and understanding why 1 is neither

Prime and Composite Numbers

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. A composite number is a natural number greater than 1 that has more than two positive divisors.

Primes are the "building blocks" of all natural numbers because every composite can be expressed as a product of primes. Composites have at least one divisor other than 1 and themselves.

Core Rules:

A prime $p > 1$ satisfies: if $p = a \times b$ where $a, b$ are positive integers, then $a = 1$ or $b = 1$ .
A composite $n > 1$ can be written as $n = a \times b$ where $1 < a, b < n$ .
The number 1 is neither prime nor composite by convention, because it has only one positive divisor (itself), not two.
The smallest prime is 2, which is also the only even prime.

This distinction ensures that prime factorization remains unique and well-defined.

Example: 7 is prime (divisors: 1, 7). 6 is composite (divisors: 1, 2, 3, 6). 1 is neither.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

STRC: CLASSIFY

Based on the rules of prime and composite numbers, how is the number 1 classified?

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 2. Executing the Sieve of Eratosthenes and introducing the infinity of primes

🕳️ The Sieve Method

Write all numbers from 2 up to your target.
Circle 2, then cross out all multiples of 2 (4, 6, 8...).
Circle the next uncrossed number (3), then cross out its multiples.
Repeat until you pass the square root of your target.
All circled numbers are prime; there are infinitely many primes.

Sieve to 20: Circle 2, cross 4,6,8,10,12,14,16,18,20. Circle 3, cross 9,15. Circle 5, cross nothing new. Primes: 2,3,5,7,11,13,17,19.

💡 Sieve = filter out the composites, keep the primes forever.

[EXEC: DEEP_COMPUTE]

2. Executing the Sieve of Eratosthenes and introducing the infinity of primes

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm to systematically identify all prime numbers up to a given limit $N$ . It eliminates multiples of each prime, leaving only primes unmarked.

The method exploits the fact that every composite number has a prime divisor no greater than its square root. This makes the sieve efficient for finding primes in a range.

Core Rules:

List all integers from 2 to $N$ .
Starting with $p = 2$ , mark all multiples of $p$ (except $p$ itself) as composite.
Move to the next unmarked number and repeat until $p^2 > N$ .
All unmarked numbers are prime.

There are infinitely many primes. Euclid proved this by showing that for any finite list of primes, a new prime can always be constructed.

Example: Sieve up to 10: Start with [2,3,4,5,6,7,8,9,10]. Mark multiples of 2: [2,3,~~4~~,5,~~6~~,7,~~8~~,~~9~~,~~10~~]. Mark multiples of 3: [2,3,~~4~~,5,~~6~~,7,~~8~~,~~9~~,~~10~~]. Primes: 2, 3, 5, 7.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

You are applying the Sieve of Eratosthenes to find all primes up to $20$ . After crossing out all multiples of $2$ , you move to the next unmarked number, which is $3$ . What is the smallest number that gets crossed out for the FIRST time during the step for multiples of $3$ ?

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 3. Prime factorization using factor trees and the multiplicity of factors

🌳 Breaking Numbers into Primes

Every composite splits into two smaller factors (branches).
Keep splitting until all branches end in prime numbers.
Write the result using exponents for repeated primes (multiplicity).
Different trees give the same prime factors (order does not matter).
Example: $36 = 2^2 \times 3^2$ .

Factor tree for 60: Split 60 into 6 and 10, then 6 into 2 and 3, and 10 into 2 and 5. Result: $60 = 2^2 \times 3 \times 5$ .

💡 Tree branches always end at primes, no matter which path you take.

[EXEC: DEEP_COMPUTE]

3. Prime factorization using factor trees and the multiplicity of factors

Prime Factorization and Factor Trees

Prime factorization is the process of expressing a composite number as a product of prime numbers. A factor tree is a visual method to systematically break down a number into its prime factors.

Each composite number can be repeatedly divided by primes until only prime factors remain. The multiplicity of a prime $p$ in the factorization of $n$ is the exponent of $p$ when $n$ is written in the form $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$ .

Core Rules:

Start with the composite number and divide by the smallest prime divisor.
Continue dividing each quotient by primes until all factors are prime.
Write the result using exponents: $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$ .
Multiplicity $a_i$ counts how many times prime $p_i$ appears.

This representation is compact and reveals divisibility properties.

Example: Factor tree for 60: $60 = 2 \times 30 = 2 \times 2 \times 15 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$ . Multiplicity of 2 is 2.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Find the multiplicity of the prime factor $2$ in the prime factorization of $40$ .

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 4. The Fundamental Theorem of Arithmetic (unique prime factorization)

🔐 Every Number Has One Prime Recipe

Every integer greater than 1 has exactly one prime factorization (ignoring order).
This means primes are the building blocks of all numbers.
No two different sets of primes multiply to the same number.
Convention: write prime factors in ascending order with exponents.
Example: $100 = 2^2 \times 5^2$ is the only way.

Why is $12 = 2^2 \times 3$ unique? You cannot write 12 using any other primes.

💡 Primes are atomic: one number, one prime DNA.

[EXEC: DEEP_COMPUTE]

4. The Fundamental Theorem of Arithmetic (unique prime factorization)

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers in exactly one way, up to the order of factors. This uniqueness is the cornerstone of number theory.

No matter which method is used to factor a number, the same set of primes with the same multiplicities will always appear. This guarantees consistency across all mathematical operations involving factorization.

Core Rules:

Every $n > 1$ has a unique prime factorization: $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$ where $p_1 < p_2 < \cdots < p_k$ are primes and $a_i \geq 1$ .
Uniqueness holds up to reordering: $2 \times 3 \times 5$ and $5 \times 2 \times 3$ represent the same factorization.
This theorem justifies why 1 is excluded from primes (otherwise factorization would not be unique).

This result underpins algorithms in cryptography, computer science, and algebra.

Example: $60 = 2^2 \times 3 \times 5$ is the unique factorization. No other combination of primes produces 60.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

STRC: CLASSIFY

According to the Fundamental Theorem of Arithmetic, why is the number 1 excluded from being classified as a prime number?

DEEP_COMPUTE

ULTRA

[EXEC: MICRO_CORE]

✖️ 5. Applications: Prime factorization as the foundation of RSA public-key encryption

🔒 Primes Protect Your Secrets

RSA encryption multiplies two huge primes to create a public key.
Factoring that product back into primes is extremely hard (takes centuries).
Your private key uses the original primes, which only you know.
This asymmetry lets anyone encrypt, but only you decrypt.
Example: If $n = 77 = 7 \times 11$ , knowing 7 and 11 is the secret.

Public key: 77. Attacker must factor 77 to break it. With 200-digit primes, factoring is nearly impossible.

💡 Easy to multiply primes, nightmare to factor them back.

[EXEC: DEEP_COMPUTE]

5. Applications: Prime factorization as the foundation of RSA public-key encryption

Prime Factorization in RSA Encryption

RSA encryption is a widely-used public-key cryptosystem that relies on the computational difficulty of factoring large composite numbers into their prime factors. The security of RSA depends on the Fundamental Theorem of Arithmetic.

In RSA, two large primes $p$ and $q$ are multiplied to form $n = p \times q$ . While computing $n$ is fast, recovering $p$ and $q$ from $n$ is computationally infeasible for sufficiently large primes (e.g., hundreds of digits).

Core Rules:

Key generation: Choose two large primes $p$ and $q$ ; compute $n = p \times q$ .
Public key includes $n$ ; private key requires knowledge of $p$ and $q$ .
Security assumption: Factoring $n$ into $p$ and $q$ is hard when $n$ is very large (e.g., 2048 bits).
Breaking RSA requires solving the prime factorization problem, which has no known efficient algorithm.

This application demonstrates how pure number theory enables modern secure communication.

Example: If $p = 61$ and $q = 53$ , then $n = 3233$ . Factoring 3233 is easy here, but for 600-digit $n$ , it becomes practically impossible.

EXECUTION_BLOCK

TASK_1[0 / 3]

LVL_2

EXEC: ALGORITHM

Given $p = 17$ and $q = 19$ , compute the public key component $n$ .

DEEP_COMPUTE

ULTRA

Prime and composite numbers (Sieve of Eratosthenes)

✖️ 1. Defining primes, composites, and understanding why 1 is neither

🔢 What Makes a Number Prime?

1. Defining primes, composites, and understanding why 1 is neither

Prime and Composite Numbers

✖️ 2. Executing the Sieve of Eratosthenes and introducing the infinity of primes

🕳️ The Sieve Method

2. Executing the Sieve of Eratosthenes and introducing the infinity of primes

The Sieve of Eratosthenes

✖️ 3. Prime factorization using factor trees and the multiplicity of factors

🌳 Breaking Numbers into Primes

3. Prime factorization using factor trees and the multiplicity of factors

Prime Factorization and Factor Trees

✖️ 4. The Fundamental Theorem of Arithmetic (unique prime factorization)

🔐 Every Number Has One Prime Recipe

4. The Fundamental Theorem of Arithmetic (unique prime factorization)

The Fundamental Theorem of Arithmetic

✖️ 5. Applications: Prime factorization as the foundation of RSA public-key encryption

🔒 Primes Protect Your Secrets

5. Applications: Prime factorization as the foundation of RSA public-key encryption

Prime Factorization in RSA Encryption

AWAITING_CONFIRMATION