# Theory QuotRem

Up to index of Isabelle/HOL/Extraction

theory QuotRem
imports Main
begin

    (*  Title:      HOL/Extraction/QuotRem.thy
        ID:         $Id: QuotRem.thy,v 1.6 2005/09/23 14:05:42 nipkow Exp $
        Author:     Stefan Berghofer, TU Muenchen
    *)

    header {* Quotient and remainder *}

    theory QuotRem imports Main begin
    text {* Derivation of quotient and remainder using program extraction. *}

    lemma nat_eq_dec: "!!n::nat. m = n ∨ m ≠ n"
      apply (induct m)
      apply (case_tac n)
      apply (case_tac [3] n)
      apply (simp only: nat.simps, iprover?)+
      done

    theorem division: "∃r q. a = Suc b * q + r ∧ r ≤ b"
    proof (induct a)
      case 0
      have "0 = Suc b * 0 + 0 ∧ 0 ≤ b" by simp
      thus ?case by iprover
    next
      case (Suc a)
      then obtain r q where I: "a = Suc b * q + r" and "r ≤ b" by iprover
      from nat_eq_dec show ?case
      proof
        assume "r = b"
        with I have "Suc a = Suc b * (Suc q) + 0 ∧ 0 ≤ b" by simp
        thus ?case by iprover
      next
        assume "r ≠ b"
        hence "r < b" by (simp add: order_less_le)
        with I have "Suc a = Suc b * q + (Suc r) ∧ (Suc r) ≤ b" by simp
        thus ?case by iprover
      qed
    qed

    extract division

    text {*
      The program extracted from the above proof looks as follows
      @{thm [display] division_def [no_vars]}
      The corresponding correctness theorem is
      @{thm [display] division_correctness [no_vars]}
    *}

    code_module Div
    contains
      test = "division 9 2"

    end

lemma nat_eq_dec:

      m = n ∨ m ≠ n

theorem division:

      ∃r q. a = Suc b * q + r ∧ r ≤ b