Skip to content

The explanation for the proof of edivnP #148

@akr

Description

@akr

I found that the explanation of the proof of edivnP on p. 110 is not updated.
I read the book version 1.0.2.

The proof of edivnP is changed in the commit:
3448f11

The current proof is as follows.

(* 1 *) rewrite -[m]/(0 * d + m).
(* 2 *) case: d => [//= | d /=] in ed *.
(* 3 *) rewrite -[edivn m d.+1]/(edivn_rec d m 0) in ed *.
(* 4 *) case: (ubnPgeq m) @ed; elim: m 0 => [|m IHm] q [/=|n] leq_nm //.
(* 5 *) rewrite edivn_recE subn_if_gt; case: ifP => [le_dm ed|lt_md]; last first.
(* 6 *)   by rewrite /= ltnS ltnNge lt_md eqxx.
(* 7 *) rewrite -ltnS in le_dm; rewrite -(subnKC le_dm) addnA -mulSnr subSS.
(* 8 *) by apply: IHm q.+1 (n-d) _; apply: leq_trans (leq_subr d n) leq_nm.

The old proof is follows.

(* 1 *) case: d => [//=|d /=] in ed *.
(* 2 *) rewrite -[edivn m d.+1]/(edivn_rec d m 0) in ed *.
(* 3 *) rewrite -[m]/(0 * d.+1 + m).
(* 4 *) elim: m {-2}m 0 (leqnn m) @ed => [[]//=|n IHn [//=|m]] q le_mn.
(* 5 *) rewrite edivn_recE subn_if_gt; case: ifP => [le_dm|lt_md]; last first.
(* 6 *)   by rewrite /= ltnS ltnNge lt_md eqxx.
(* 7 *) have /(IHn _ q.+1) : m - d <= n by rewrite (leq_trans (leq_subr d m)).
(* 8 *) by rewrite /= mulSnr -addnA -subSS subnKC.

"Line 1 handles the case of d being zero." refers to the first "case" line
but it wrongly refers to the first "rewrite" line now.
"Line 1" should be changed to "Line 2".

"Lines 2 and 3 prepare the induction ..." refers
first two "rewrite" lines.
"Lines 2 and 3" should be changed to "Line 1 and 3".

"replacing m by (0 * d.+1 + m). Recall the case d being 0 has already been handled."
is not appropriate now because m is replaced by (0 * d + m) in the current proof.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions