Require Export Lib_Mult.


Inductive even (n : nat) : Prop :=
    even_intro : ∀ q : nat, n = 2 × q → even n.

Inductive odd (n : nat) : Prop :=
    odd_intro : ∀ q : nat, n = 2 × q + 1 → odd n.


Lemma no_zero_div :
 ∀ n m : nat, 0 < n → ∀ q : nat, n = m × q → 0 < q.
simple induction q.
intro.
absurd (0 = n).
apply lt_O_neq; auto with v62.
rewrite (mult_n_O m); auto with v62.
auto with v62.
Qed.

Lemma lt_quotient2_n :
 ∀ n : nat, 0 < n → ∀ q : nat, n = 2 × q → q < n.
intros.
rewrite (plus_n_O q).
rewrite H0.
elim plus_mult.
apply plus_lt_compat_l.
apply (no_zero_div n 2 H q H0).
Qed.
Hint Resolve lt_quotient2_n.

Lemma less_div : ∀ n a b : nat, 0 < n → n = a × b → b ≤ n.
intros.
rewrite H0.
elim (mult_O_le b a); auto with v62.
intro.
absurd (n = 0).
unfold not in |- *; intro.
elim (lt_irrefl n).
pattern n at 1 in |- ×.
rewrite H2; auto with v62.
rewrite H0.
rewrite H1; auto with v62.
Qed.


Lemma even_or_odd : ∀ n : nat, {even n} + {odd n}.
simple induction n.
left; apply (even_intro 0 0); auto with v62.
intros y hrec.
elim hrec.
intro eveny.
right; elim eveny.
intros q hy; apply (odd_intro (S y) q).
elim hy.
elim plus_n_Sm.
auto with v62.
intro oddy; left.
elim oddy.
intros q hy; apply (even_intro (S y) (S q)).
rewrite hy.
rewrite plus_n_Sm.
elim (mult_comm (S q) 2).
elim (mult_comm q 2).
elim plus_comm.
auto with v62.
Qed.

Lemma even_odd : ∀ a : nat, even a → ¬ odd a.
unfold not in |- *; intros.
elim H0; elim H.
intros k1 evena k2 odda.
apply (le_Sn_n 1).
apply (less_div 1 (k1 - k2) 2); auto with v62.
rewrite mult_comm.
replace (2 × (k1 - k2)) with (2 × k1 - 2 × k2).
elim evena.
rewrite odda.
auto with v62.
elim mult_comm.
replace (2 × k1) with (k1 × 2).
2: apply mult_comm.
replace (2 × k2) with (k2 × 2).
2: apply mult_comm.
elim (mult_comm 2 k1); elim (mult_comm 2 k2).
apply sym_equal; auto with v62.
Qed.

Lemma odd_even : ∀ a : nat, odd a → ¬ even a.
unfold not in |- *; intros.
apply (even_odd a H0).
auto with v62.
Qed.


Lemma plus_even_even : ∀ a b : nat, even a → even b → even (a + b).
intros.
elim H0; elim H.
intros.
rewrite H2; rewrite H1.
elim (mult_plus_distr_left q q0 2).
apply (even_intro (2 × (q + q0)) (q + q0)).
auto with v62.
Qed.

Lemma S_odd_even : ∀ a : nat, odd a → even (S a).
intros.
elim H; intros.
rewrite H0.
rewrite (plus_n_Sm (2 × q) 1).
apply (plus_even_even (2 × q) 2).
apply (even_intro (2 × q) q); auto with v62.
apply (even_intro 2 1).
auto with v62.
Qed.

Lemma pred_odd_even : ∀ a : nat, odd a → even (pred a).
intros.
elim H; intros.
rewrite H0.
elim (plus_n_Sm (2 × q) 0).
elim (pred_Sn (2 × q + 0)).
elim (plus_n_O (2 × q)).
apply (even_intro (2 × q) q); auto with v62.
Qed.

Lemma plus_even_odd : ∀ a b : nat, even a → odd b → odd (a + b).
intros.
elim H0; elim H; intros.
rewrite H2; rewrite H1.
rewrite (plus_assoc (2 × q) (2 × q0) 1).
elim (mult_plus_distr_left q q0 2).
apply (odd_intro (2 × (q + q0) + 1) (q + q0)).
auto with v62.
Qed.
Hint Resolve plus_even_odd.

Lemma plus_odd_even : ∀ a b : nat, odd a → even b → odd (a + b).
intros.
rewrite plus_comm.
auto with v62.
Qed.

Lemma S_even_odd : ∀ a : nat, even a → odd (S a).
intros.
elim H; intros.
rewrite H0.
apply (odd_intro (S (2 × q)) q).
elim (plus_n_Sm (2 × q) 0).
auto with v62.
Qed.

Lemma plus_odd_odd : ∀ a b : nat, odd a → odd b → even (a + b).
intros.
elim H0; elim H; intros.
rewrite H2; rewrite H1; intros.
rewrite (plus_comm (2 × q0) 1).
rewrite (plus_assoc (2 × q + 1) 1 (2 × q0)).
rewrite (plus_assoc_reverse (2 × q) 1 1).
apply (plus_even_even (2 × q + (1 + 1)) (2 × q0)).
apply (plus_even_even (2 × q) (1 + 1)).
apply (even_intro (2 × q) q); auto with v62.
apply (even_intro (1 + 1) 1); auto with v62.
apply (even_intro (2 × q0) q0); auto with v62.
Qed.


Lemma mult_even : ∀ a b : nat, even a → even (a × b).
intros.
elim H.
intros.
apply (even_intro (a × b) (q × b)).
rewrite H0.
auto with v62.
Qed.

Lemma mult_odd_odd : ∀ a b : nat, odd a → odd b → odd (a × b).
intros.
elim H0; intros.
elim H; intros.
clear H0; clear H.
rewrite H2; rewrite H1.
rewrite (mult_plus_distr_r (2 × q0) 1 (2 × q + 1)).
apply (plus_even_odd (2 × q0 × (2 × q + 1)) (1 × (2 × q + 1))).
apply (mult_even (2 × q0) (2 × q + 1)).
apply (even_intro (2 × q0) q0); auto with v62.
apply (odd_intro (1 × (2 × q + 1)) q); auto with v62.
Qed.


Definition div (d a : nat) := ∃ k : nat, a = d × k.


Lemma div_odd_even : ∀ n d : nat, div d (2 × n) → odd d → div d n.
intros.
elim H.
intros.
cut (even x).
intro.
elim H2.
intros q evenx.
unfold div in |- ×.
∃ q.
apply (mult_reg_l_bis n (d × q) 2).
auto with v62.
rewrite H1.
rewrite evenx.
elim (mult_assoc_reverse 2 d q).
rewrite (mult_comm 2 d).
auto with v62.
elim (even_or_odd x).
auto with v62.
intros.
absurd (even (d × x)).
apply odd_even.
apply mult_odd_odd; auto with v62.
cut (d × x = 2 × n); auto with v62.
intro.
apply (even_intro (d × x) n).
auto with v62.
Qed.

Lemma div_odd_odd : ∀ n : nat, odd n → ∀ d : nat, div d n → odd d.
intros n oddn d divdn.
elim divdn.
intros.
 elim (even_or_odd d); auto with v62.
intros evend.
absurd (even n).
apply odd_even; auto with v62.
rewrite H.
apply mult_even; auto with v62.
Qed.

Lemma div_plus : ∀ n m d : nat, div d n → div d m → div d (n + m).
intros n m d divdn divdm.
elim divdm; intros; elim divdn; intros.
rewrite H0; rewrite H.
elim mult_plus_distr_left.
unfold div in |- ×.
∃ (x0 + x); auto with v62.
Qed.
Hint Resolve div_plus.

Lemma div_minus : ∀ n m d : nat, div d n → div d m → div d (n - m).
intros n m d divdn divdm.
elim divdm; intros; elim divdn; intros.
rewrite H0; rewrite H. elim (mult_minus_distr_left x0 x d).
unfold div in |- ×.
∃ (x0 - x); auto with v62.
Qed.
Hint Resolve div_minus.


Inductive Even (n : nat) : Set :=
    Even_intro : ∀ q : nat, n = 2 × q → Even n.

Inductive Odd (n : nat) : Set :=
    Odd_intro : ∀ q : nat, n = 2 × q + 1 → Odd n.


Lemma Even_or_Odd : ∀ n : nat, Even n + Odd n.
simple induction n.
left; apply (Even_intro 0 0); auto with v62.
intros y hrec.
elim hrec.
intro eveny.
right; elim eveny.
intros q hy; apply (Odd_intro (S y) q).
elim hy.
elim plus_n_Sm.
auto with v62.
intro oddy; left.
elim oddy.
intros q hy; apply (Even_intro (S y) (S q)).
rewrite hy.
rewrite plus_n_Sm.
elim (mult_comm (S q) 2).
elim (mult_comm q 2).
elim plus_comm.
auto with v62.
Qed.

Lemma Odd_odd : ∀ n : nat, Odd n → odd n.
intros.
elim H.
intros.
apply (odd_intro n q e).
Qed.
Hint Resolve Odd_odd.