Step-by-step derivation
S001 · implies
Before
natural-number prime protocol;0 and1 are not prime
After
a failed candidate witness alone is not a primality proof
Conditions: none
Naturals include0.Primality retains both n≥2 and a complete factor bound.A failed single factor candidate only invalidates that witness;it does not certify primality.
Step identifiers and dependencies
Rule: prime_complete_evidence_scope · Uses: G001
S002 · implies
Before
phase=interval value0;n=0
After
n>=2=No
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S001
S003 · implies
Before
phase=interval value1;n=1
After
n>=2=No
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S002
S004 · implies
Before
phase=interval value2;n=2
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S003
S005 · implies
Before
phase=interval value2;tried ascending divisors=[];sqrt floor=1
After
least factor at least2=2;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S004
S006 · implies
Before
phase=interval value3;n=3
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S005
S007 · implies
Before
phase=interval value3;tried ascending divisors=[];sqrt floor=1
After
least factor at least2=3;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S006
S008 · implies
Before
phase=interval value4;n=4
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S007
S009 · implies
Before
interval value4 trial divisor2:natural dividend=4;positive divisor=2
After
4=2·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S008
S010 · implies
Before
phase=interval value4;tried ascending divisors=[2];sqrt floor=2
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S009
S011 · implies
Before
phase=interval value5;n=5
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S010
S012 · implies
Before
interval value5 trial divisor2:natural dividend=5;positive divisor=2
After
5=2·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S011
S013 · implies
Before
phase=interval value5;tried ascending divisors=[2];sqrt floor=2
After
least factor at least2=5;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S012
S014 · implies
Before
phase=interval value6;n=6
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S013
S015 · implies
Before
interval value6 trial divisor2:natural dividend=6;positive divisor=2
After
6=3·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S014
S016 · implies
Before
phase=interval value6;tried ascending divisors=[2];sqrt floor=2
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S015
S017 · implies
Before
phase=interval value7;n=7
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S016
S018 · implies
Before
interval value7 trial divisor2:natural dividend=7;positive divisor=2
After
7=3·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S017
S019 · implies
Before
phase=interval value7;tried ascending divisors=[2];sqrt floor=2
After
least factor at least2=7;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S018
S020 · implies
Before
phase=interval value8;n=8
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S019
S021 · implies
Before
interval value8 trial divisor2:natural dividend=8;positive divisor=2
After
8=4·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S020
S022 · implies
Before
phase=interval value8;tried ascending divisors=[2];sqrt floor=2
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S021
S023 · implies
Before
phase=interval value9;n=9
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S022
S024 · implies
Before
interval value9 trial divisor2:natural dividend=9;positive divisor=2
After
9=4·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S023
S025 · implies
Before
interval value9 trial divisor3:natural dividend=9;positive divisor=3
After
9=3·3+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S024
S026 · implies
Before
phase=interval value9;tried ascending divisors=[2, 3];sqrt floor=3
After
least factor at least2=3;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S025
S027 · implies
Before
phase=interval value10;n=10
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S026
S028 · implies
Before
interval value10 trial divisor2:natural dividend=10;positive divisor=2
After
10=5·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S027
S029 · implies
Before
phase=interval value10;tried ascending divisors=[2];sqrt floor=3
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S028
S030 · implies
Before
phase=interval value11;n=11
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S029
S031 · implies
Before
interval value11 trial divisor2:natural dividend=11;positive divisor=2
After
11=5·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S030
S032 · implies
Before
interval value11 trial divisor3:natural dividend=11;positive divisor=3
After
11=3·3+2
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S031
S033 · implies
Before
phase=interval value11;tried ascending divisors=[2, 3];sqrt floor=3
After
least factor at least2=11;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S032
S034 · implies
Before
phase=interval value12;n=12
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S033
S035 · implies
Before
interval value12 trial divisor2:natural dividend=12;positive divisor=2
After
12=6·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S034
S036 · implies
Before
phase=interval value12;tried ascending divisors=[2];sqrt floor=3
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S035
S037 · implies
Before
phase=interval value13;n=13
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S036
S038 · implies
Before
interval value13 trial divisor2:natural dividend=13;positive divisor=2
After
13=6·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S037
S039 · implies
Before
interval value13 trial divisor3:natural dividend=13;positive divisor=3
After
13=4·3+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S038
S040 · implies
Before
phase=interval value13;tried ascending divisors=[2, 3];sqrt floor=3
After
least factor at least2=13;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S039
S041 · implies
Before
phase=interval value14;n=14
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S040
S042 · implies
Before
interval value14 trial divisor2:natural dividend=14;positive divisor=2
After
14=7·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S041
S043 · implies
Before
phase=interval value14;tried ascending divisors=[2];sqrt floor=3
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S042
S044 · implies
Before
phase=interval value15;n=15
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S043
S045 · implies
Before
interval value15 trial divisor2:natural dividend=15;positive divisor=2
After
15=7·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S044
S046 · implies
Before
interval value15 trial divisor3:natural dividend=15;positive divisor=3
After
15=5·3+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S045
S047 · implies
Before
phase=interval value15;tried ascending divisors=[2, 3];sqrt floor=3
After
least factor at least2=3;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S046
S048 · implies
Before
phase=interval value16;n=16
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S047
S049 · implies
Before
interval value16 trial divisor2:natural dividend=16;positive divisor=2
After
16=8·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S048
S050 · implies
Before
phase=interval value16;tried ascending divisors=[2];sqrt floor=4
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S049
S051 · implies
Before
phase=interval value17;n=17
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S050
S052 · implies
Before
interval value17 trial divisor2:natural dividend=17;positive divisor=2
After
17=8·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S051
S053 · implies
Before
interval value17 trial divisor3:natural dividend=17;positive divisor=3
After
17=5·3+2
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S052
S054 · implies
Before
interval value17 trial divisor4:natural dividend=17;positive divisor=4
After
17=4·4+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S053
S055 · implies
Before
phase=interval value17;tried ascending divisors=[2, 3, 4];sqrt floor=4
After
least factor at least2=17;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S054
S056 · implies
Before
phase=interval value18;n=18
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S055
S057 · implies
Before
interval value18 trial divisor2:natural dividend=18;positive divisor=2
After
18=9·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S056
S058 · implies
Before
phase=interval value18;tried ascending divisors=[2];sqrt floor=4
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S057
S059 · implies
Before
phase=interval value19;n=19
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S058
S060 · implies
Before
interval value19 trial divisor2:natural dividend=19;positive divisor=2
After
19=9·2+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S059
S061 · implies
Before
interval value19 trial divisor3:natural dividend=19;positive divisor=3
After
19=6·3+1
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S060
S062 · implies
Before
interval value19 trial divisor4:natural dividend=19;positive divisor=4
After
19=4·4+3
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S061
S063 · implies
Before
phase=interval value19;tried ascending divisors=[2, 3, 4];sqrt floor=4
After
least factor at least2=19;prime=Yes
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S062
S064 · implies
Before
phase=interval value20;n=20
After
n>=2=Yes
Conditions: none
A prime must be at least2.Exclude0 and1 first rather than treating an absence of trial factors as primality.
Step identifiers and dependencies
Rule: prime_lower_bound_guard · Uses: G001, S063
S065 · implies
Before
interval value20 trial divisor2:natural dividend=20;positive divisor=2
After
20=10·2+0
Conditions: none
With a positive divisor show the complete quotient/remainder equality and0≤r<divisor.Modulo zero is not evaluated.
Step identifiers and dependencies
Rule: positive_euclidean_division · Uses: G001, S064
S066 · implies
Before
phase=interval value20;tried ascending divisors=[2];sqrt floor=4
After
least factor at least2=2;prime=No
Conditions: none
If n=uv is composite with u,v≥2,one factor is≤sqrt(n).The first zero remainder in ascending order gives the least factor;if none exists through the full bound,n itself is the least factor≥2 and is prime.
Step identifiers and dependencies
Rule: complete_small_factor_bound · Uses: G001, S065
S067 · implies
Before
inclusive interval=[0, 20]
After
all primes=[2, 3, 5, 7, 11, 13, 17, 19];count=8
Conditions: none
Check both interval endpoints and retain exactly those values passing the complete primality test.This finite enumeration makes no distribution claim outside the interval.
Step identifiers and dependencies
Rule: complete_inclusive_prime_interval · Uses: G001, S066