proposition: Theorem phi_le_n_minus_1: forall n, 1 < n -> phi n <= n - 1.
proof: Proof. intros n H; replace (n-1) with ((1 + (n - 1) - 1) * 1); auto with zarith. rewrite <- Zsum_c; auto with zarith. unfold phi; apply Zsum_le; auto with zarith. intros x H1; case (rel_prime_dec x n); auto with zarith. Qed.
imports: ZArith Znumtheory Tactic ZSum