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

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions