Prime natural number

Mathematical statement

A natural number p is prime exactly when 2≤p and every natural divisor d of p satisfies d=1 or d=p. Neither 0 nor 1 is prime.

Representative formula (exact TeX)

p\in N

Assumptions

• The numbers p and d are natural, including 0; the prime condition additionally requires 2≤p.
• Use natural-number divisibility, not approximate square roots or floating-point division, to check factors.

Symbol scope

• p — candidate prime
• N — natural-number domain

Intuition, definition, and misconceptions

For a finite candidate p, enumerate every positive divisor, or check every candidate from 2 through floor(sqrt(p)): a composite number has a nontrivial factor no greater than its square root.

The divisor behavior of 0 and 1 does not satisfy the prime definition. The number 2 is the smallest prime and the only even prime.

One nontrivial factor provides a composite witness. Failure to find a factor in an incomplete candidate list alone is not a primality proof.

Mistakes include listing 1 as prime or claiming a large number prime after checking only a few small factors.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Natural-number divisibility — Primality is defined through the structure of natural-number factors.

Verification boundary

This slice uses complete divisor or square-root-bound checks inside a safe-integer range; it is not a formal primality proof for arbitrary large integers.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind Nat.Prime, Nat.dvd_prime, least factors and decidability; develop a separate certificate route for large integers.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.