derivation-mko-natural-divisibility-01 · production-20261019-adopted-96
From the MKO's definition (a∣b ⇔ there is a natural k with b=a·k): (1) prove 6∣84; (2) prove 6∤87; (3) prove 4∤10, although 10/4=5/2 is a number; (4) prove that every a divides 0; (5) prove 0∣b ⇔ b=0, and explain why the witness for 0∣0 is not unique and why 0∤5; (6) prove that for a>0 there is at most one witness (and when a∣b that existing witness is unique); (7) prove reflexivity and transitivity of divisibility, and from 3∣6 and 6∣84 find a witness for 3∣84.
Works in the natural numbers including 0 (MKO assumption a1), with natural witnesses only (a2). To decide the case a>0, the guide proves 'a∣b ⇔ the remainder is 0' from the division algorithm (a cited prerequisite). Divisibility of negative integers, greatest common divisors and primes are not treated; the canonical MKO and its English edition are not changed.
division_algorithmorder_basicsmul_zeromul_assocnumeric_evaluationG1 — ℕ includes 0; multiplication is natural-number multiplication, and sums and products of naturals are natural (MKO assumption a1).G2 — The witness k must be a natural number; a noninteger quotient is not a witness (MKO assumption a2).G3 — Pairs to decide: (6,84), (6,87), (4,10), (3,6), (0,0), (0,5).a\mid b — a divides ba\nmid b — a does not divide bk — the multiplier witness, which must be naturalb\bmod a — the remainder of b on division by a (a>0)\mathbb{N} — the natural numbers, including 0division_algorithm · prerequisite — Division algorithm: for an integer a and a positive integer b there are unique integers q, r with a=bq+r and 0≤r<b.order_basics · prerequisite — Order of the reals: exactly one of u<v, u=v, u>v holds; u<v and v<w give u<w; u<v gives u+w<v+w; u<v and w>0 give uw<vw; u<v and w<0 give uw>vw.mul_zero · prerequisite — Multiplying by zero: u·0=0. Reason: u·0=u·(0+0)=u·0+u·0; subtracting u·0 from both sides gives 0=u·0.mul_assoc · prerequisite — Associativity of multiplication: (uv)w=u(vw).numeric_evaluation · prerequisite — Exact evaluation of an explicit integer or rational expression; independently recomputable.def_unfold · prerequisite — Unfolding a definition: replacing a defined term by its definition (or folding it back) does not change whether a statement is true.exists_intro · prerequisite — ∃-introduction: if some a∈D satisfies P(a), then ∃x∈D, P(x).contradiction · prerequisite — Proof by contradiction: if assuming ¬P leads to a contradiction (a statement and its negation both hold), then P holds.add_zero · prerequisite — Additive identity: u+0=u.mul_inverse_nonzero · prerequisite — Inverse of a nonzero number: in ℚ, ℝ or ℂ, if u≠0 there is 1/u with u·(1/u)=1, and v/u means v·(1/u). 0 has no inverse, so v/0 is undefined.frac_rules · prerequisite — Fraction rules (all denominators nonzero): a/c+b/c=(a+b)/c; (a/b)(c/d)=(ac)/(bd); (a/b)/(c/d)=(ad)/(bc) (also needing c≠0); a/b=(ak)/(bk) for k≠0.forall_intro · prerequisite — ∀-introduction (generalization): if a statement is proved for an arbitrary element x, with no extra assumption on x, it holds for every x in the domain.mul_comm · prerequisite — Commutativity of multiplication: uv=vu (in commutative number systems such as ℤ, ℚ, ℝ, ℂ).case_analysis · prerequisite — Proof by cases: if P∨Q holds and both P⇒R and Q⇒R are proved, then R holds. The cases must cover every possibility.mul_one · prerequisite — Multiplicative identity: 1·u=u.exists_elim · prerequisite — ∃-elimination: from ∃x∈D, P(x) we may name some element a with P(a) by a fresh name; reasoning with a is allowed as long as the final conclusion does not mention a.eq_replace · prerequisite — Replacement of equals: an expression inside a statement may be replaced by an equal expression without changing whether the statement is true.forall_elim · prerequisite — ∀-elimination (instantiation): if ∀x∈D, P(x) holds and a∈D, then P(a) holds.mko_dvd_def · cited — For natural numbers a and b, a∣b exactly when there is a natural number k such that b=a·k. · mko-natural-divisibilitynat_discrete · prerequisite — Naturals have no values in between: for naturals k and n, either k≤n or k≥n+1.L_rem_test · lemma — For a natural b and a positive natural a: a∣b ⇔ the remainder r of b on division by a is 0.Before
a\mid b
After
\exists k\in\mathbb{N}:\ b=a\cdot kConditions: a,b\in\mathbb{N}
Rule: mko_dvd_def · Uses: G1, G2, mko_dvd_def
Leaf basis: mko_dvd_def + def_unfold
By the MKO's definition, a∣b means there is a natural number k (a multiplier witness) with b=a·k. To prove a∣b one must exhibit such a k; to prove a∤b one must show that no natural k works.
Before
84=6\cdot 14,\ 14\in\mathbb{N}After
6\mid 84
Conditions: none
Rule: exists_intro · Uses: S01, G3
Leaf basis: exists_intro + numeric_evaluation
6·14=84 (N1) and 14 is natural, so k=14 is a witness and 6∣84.
Before
a\mid b\quad(a>0)
After
b\bmod a=0
Conditions: a>0
Rule: L_rem_test · Uses: S01, L_rem_test
Leaf basis: division_algorithm + exists_intro + order_basics
For a>0, divisibility can be decided by the remainder: by Lemma L_rem_test (proved in S03.1 to S03.3), a∣b exactly when the remainder of b on division by a is 0. This replaces 'search for a witness' by one recomputable division with remainder.
Before
87=6\cdot 14+3,\ 0\le 3<6
After
6\nmid 87
Conditions: 6>0
Rule: L_rem_test · Uses: S03, G3
Leaf basis: division_algorithm + nat_discrete + order_basics + numeric_evaluation
The remainder of 87 on division by 6 is 3≠0 (N2, N3), so by the equivalence of S03, 6∤87. A direct check agrees: 6·14=84<87<90=6·15, and every natural k has k≤14 (then 6k≤84) or k≥15 (then 6k≥90), so no k gives 6k=87. In the rationals 87/6=29/2=14.5, which is not natural.
Before
10=4k,\ k\in\mathbb{N}\ ?After
4\nmid 10
Conditions: 4\neq 0
Rule: mul_inverse_nonzero · Uses: S01, S03, G2
Leaf basis: mul_inverse_nonzero + frac_rules + numeric_evaluation
In the rationals the only solution of 4k=10 is k=10/4=5/2 (division is allowed since 4≠0). 5/2 is not natural, so by G2 it is not a witness; there is no natural witness, and 4∤10. Check with S03: 10=4·2+2 with remainder 2≠0, the same conclusion.
Before
a\in\mathbb{N}After
0=a\cdot 0,\ \text{so}\ a\mid 0Conditions: none
Rule: exists_intro · Uses: S01, mul_zero
Leaf basis: mul_zero + exists_intro + forall_intro
For any natural a, a·0=0 and 0 is natural, so k=0 is a witness and a∣0. a was arbitrary, including a=0.
Before
0\mid b
After
b=0
Conditions: none
Rule: mul_zero · Uses: S01, mul_zero
Leaf basis: mul_zero + mul_comm + exists_intro
0∣b means there is a natural k with b=0·k. But 0·k=0 for every k, so this says exactly that b=0.
Before
0=0\cdot 0=0\cdot 5,\quad 5\neq 0
After
0\mid 0\ \text{with non-unique witness};\ 0\nmid 5Conditions: none
Rule: mul_zero · Uses: S07, G3
Leaf basis: mul_zero + numeric_evaluation
0∣0 holds, and both k=0 and k=5 are witnesses (0·5=0, N9), so the witness is not unique. Since 5≠0, S07 gives 0∤5. So 'zero never divides any number' is wrong: 0∣0 is true.
Before
b=a k=a k',\ a>0,\ k,k'\in\mathbb{N}After
k=k'
Conditions: a>0
Rule: order_basics · Uses: S01, order_basics
Leaf basis: order_basics + case_analysis + contradiction
By trichotomy exactly one of k<k′, k=k′, k>k′ holds. If k<k′, then a>0 gives ak<ak′, contradicting ak=ak′; likewise for k>k′. So k=k′: an existing witness is unique, or equivalently there is at most one witness when a>0. This contrasts with the case a=0 in S08.
Before
a\in\mathbb{N}After
a=a\cdot 1,\ \text{so}\ a\mid aConditions: none
Rule: exists_intro · Uses: S01, mul_one
Leaf basis: mul_one + mul_comm + exists_intro
Reflexivity: a·1=a and 1 is natural, so a∣a; this includes 0∣0 (0=0·1).
Before
a\mid b,\ b\mid c
After
a\mid c
Conditions: none
Rule: exists_elim · Uses: S01
Leaf basis: exists_elim + mul_assoc + exists_intro
Transitivity: from a∣b take a witness k with b=ak; from b∣c take a witness l with c=bl (S11.1). Substituting and using associativity gives c=a(kl), with kl natural (S11.2), so a∣c with witness kl.
Before
6=3\cdot 2,\ 84=6\cdot 14
After
84=3\cdot 28,\ 3\mid 84
Conditions: none
Rule: forall_elim · Uses: S11, G3
Leaf basis: forall_elim + numeric_evaluation
3∣6 has witness k=2 and 6∣84 has witness l=14; by S11, 3∣84 has witness kl=28. Check: 3·28=84 and 84 leaves remainder 0 on division by 3 (N10 to N12).
Before
(a,b)\in\mathbb{N}^2After
a=0:\ a\mid b\iff b=0;\quad a>0:\ a\mid b\iff b\bmod a=0
Conditions: none
Rule: case_analysis · Uses: S03, S07, S02, S04, S05, S08
Leaf basis: case_analysis + order_basics
Decision procedure: first check a=0, where a∣b ⇔ b=0 (S07); otherwise a>0 and a∣b ⇔ the remainder is 0 (S03). The two cases cover every natural a. Applied: (6,84) remainder 0, divides; (6,87) remainder 3, does not; (4,10) remainder 2, does not; (0,0) divides; (0,5) does not.
Before
b=aq+r,\ 0\le r<a,\ q\in\mathbb{Z},\ b\ge 0After
q\ge 0,\ \text{so}\ q\in\mathbb{N}Conditions: a>0
Rule: order_basics · Uses: division_algorithm, order_basics
Leaf basis: division_algorithm + order_basics + contradiction
The division algorithm gives integers q and r. If q≤−1, then aq≤−a, so b=aq+r≤−a+r<−a+a=0, contradicting b≥0. Hence q≥0 and q is natural.
Before
b=aq+0,\ q\in\mathbb{N}After
a\mid b
Conditions: r=0
Rule: exists_intro · Uses: S03.1, S01
Leaf basis: exists_intro + add_zero
(The ⇐ direction) If the remainder r=0, then b=aq with q natural (S03.1), so q is a witness and a∣b.
Before
b=a\cdot k,\ k\in\mathbb{N}After
b\bmod a=0
Conditions: a>0
Rule: division_algorithm · Uses: S01, division_algorithm
Leaf basis: division_algorithm + add_zero
(The ⇒ direction) If b=ak, then b=a·k+0 with 0≤0<a. The quotient and remainder of the division algorithm are unique, so the remainder of b on division by a is 0 (and the quotient is k). S03.1 to S03.3 together prove Lemma L_rem_test.
Before
b=ak,\ c=bl
After
c=(ak)l
Conditions: none
Rule: eq_replace · Uses: S01, exists_elim
Leaf basis: eq_replace
Replace b in c=bl by the equal expression ak.
Before
c=(ak)l
After
c=a(kl),\ kl\in\mathbb{N}Conditions: none
Rule: mul_assoc · Uses: S11.1, G1
Leaf basis: mul_assoc
Associativity gives (ak)l=a(kl); a product of naturals is natural (G1), so kl is a legitimate witness.
S13 · sufficient_goal_reduction · S03, S07, case_analysis — Goal G: decide every pair correctly. Sufficient condition H: each of the cases a=0 and a>0 has a proved criterion; H⇒G by proof by cases. H is proved forwards in S03 and S07.S12 · premise_audit · S11, forall_elim, numeric_evaluation — An instance of S11 with a numeric check; it cannot replace the general proof.S11.2 · premise_audit · mul_assoc, G1 — It needs ℕ to be closed under multiplication; over the rationals this step would allow non-natural witnesses.S11.1 · premise_audit · eq_replace — Replacement of equals.S11 · premise_audit · S01, exists_elim, mul_assoc — The conclusion does not mention the temporary names k and l, so ∃-elimination is legitimate. No converse is claimed: a∣c does not give a∣b.S10 · premise_audit · mul_one, exists_intro — Only the multiplicative identity is used.S09 · premise_audit · order_basics, case_analysis — a>0 is needed to preserve strict inequality; for a=0 the conclusion fails (S08).S08 · premise_audit · S07, mul_zero — Two instances of S07 and one example of a non-unique witness.S07 · inverse_equivalence · mul_zero, exists_intro — Backward: if b=0, take k=0 to get b=0·0, so 0∣b. Both directions hold.S06 · premise_audit · S01, mul_zero, exists_intro, forall_intro — Only multiplication by zero is used; it holds for every a, so the statement generalizes.S05 · premise_audit · S01, S03, G2, mul_inverse_nonzero — The argument relies on the rational solution being unique: if the only solution is not natural, there is no natural solution. Having a numerical quotient does not mean divisibility.S04 · premise_audit · S03, nat_discrete, order_basics — A negative answer must exclude every k; the equivalence of S03, or the two-sided squeeze with nat_discrete, does so. Checking a few values of k would not be enough.S03.3 · premise_audit · division_algorithm — The key is uniqueness in the division algorithm; existence alone would not let one representation determine the remainder. The lemma itself is not used.S03.2 · premise_audit · S03.1, exists_intro — Only the fact that q is a natural number is used; the lemma itself is not used.S03.1 · premise_audit · division_algorithm, order_basics — It needs a>0 and b≥0; this ensures the quotient can serve as a natural witness.S03 · inverse_equivalence · L_rem_test — Both directions of the lemma (S03.2, S03.3) are proved; the premise a>0 is what the division algorithm needs.S02 · premise_audit · S01, exists_intro, numeric_evaluation — Existence needs only one witness; uniqueness is not claimed here (see S09).S01 · premise_audit · G1, G2, mko_dvd_def — This step only unfolds the definition; the witness is restricted to naturals (G2), not rationals.The misconception the MKO names: claiming a∣b because b/a is a number. 10/4=5/2 is a rational number, but the witness must be natural, so 4∤10 (S05). Decide by a natural witness or by whether the remainder is 0.
The other misconception the MKO names: ruling that zero never divides any number. By the definition 0∣b ⇔ b=0 (S07), so 0∣0 holds and 0∤5. Note that no 'division by 0' is performed; one only looks for a multiplier witness.
To prove 6∤87, trying k=14 and 15 is not enough; the remainder lemma or the squeeze with nat_discrete must exclude every k (S04). Likewise 6∣3 fails: in 3=6·(1/2) the factor 1/2 is not natural, and 3 leaves remainder 3 on division by 6.
reject — The witness must be natural; 10=4·2+2 with remainder 2≠0.reject — 0=0·0, so 0∣0.reject — For every k, 0·k=0≠5.reject — 1/2 is not natural; 3=6·0+3 with remainder 3≠0.reject — 0=0·0=0·5, so k=0 and k=5 are both witnesses.6∣84 (witness 14); 6∤87 (remainder 3); 4∤10 (the only rational solution 5/2 is not natural; remainder 2); every a divides 0 (witness 0); 0∣b ⇔ b=0, so 0∣0 but 0∤5, and the witness for 0∣0 is not unique; for a>0 there is at most one witness, unique when it exists; divisibility is reflexive and transitive, and 3∣84 has witness 2·14=28.
14 declared checks for this guide; only the listed expressions are covered.
b28a5edbd46279b1db2a3f3f48bb3f447e18899fc7700b425af628e5a943830098f9039a8ba739a667d2577ec46189e0e21243241b68c27c071f5fe0cfe48fffd7605f00b4dfae82833e7c47a8a473157438e68fNOT_MEASUREDSame-source full JSON (formulas, ASTs, controls and revision log)