1.1 --- a/src/HOL/Divides.thy Tue Mar 27 15:53:48 2012 +0200
1.2 +++ b/src/HOL/Divides.thy Tue Mar 27 16:04:51 2012 +0200
1.3 @@ -283,6 +283,15 @@
1.4 by (simp only: mod_mult_eq [symmetric])
1.5 qed
1.6
1.7 +text {* Exponentiation respects modular equivalence. *}
1.8 +
1.9 +lemma power_mod: "(a mod b)^n mod b = a^n mod b"
1.10 +apply (induct n, simp_all)
1.11 +apply (rule mod_mult_right_eq [THEN trans])
1.12 +apply (simp (no_asm_simp))
1.13 +apply (rule mod_mult_eq [symmetric])
1.14 +done
1.15 +
1.16 lemma mod_mod_cancel:
1.17 assumes "c dvd b"
1.18 shows "a mod b mod c = a mod c"
1.19 @@ -2179,13 +2188,6 @@
1.20 using zmod_zdiv_equality[where a="m" and b="n"]
1.21 by (simp add: algebra_simps) (* FIXME: generalize *)
1.22
1.23 -lemma zpower_zmod: "((x::int) mod m)^y mod m = x^y mod m"
1.24 -apply (induct "y", auto)
1.25 -apply (rule mod_mult_right_eq [THEN trans])
1.26 -apply (simp (no_asm_simp))
1.27 -apply (rule mod_mult_eq [symmetric])
1.28 -done (* FIXME: generalize *)
1.29 -
1.30 lemma zdiv_int: "int (a div b) = (int a) div (int b)"
1.31 apply (subst split_div, auto)
1.32 apply (subst split_zdiv, auto)
1.33 @@ -2228,7 +2230,7 @@
1.34 mod_add_right_eq [symmetric]
1.35 mod_mult_right_eq[symmetric]
1.36 mod_mult_left_eq [symmetric]
1.37 - zpower_zmod
1.38 + power_mod
1.39 zminus_zmod zdiff_zmod_left zdiff_zmod_right
1.40
1.41 text {* Distributive laws for function @{text nat}. *}