208 apply(metis dvd_diffD1 dvd_triv_right le_extend_mult linorder_linear linorder_not_less mult_commute nat_dvd_not_less neq0_conv) |
208 apply(metis dvd_diffD1 dvd_triv_right le_extend_mult linorder_linear linorder_not_less mult_commute nat_dvd_not_less neq0_conv) |
209 done |
209 done |
210 |
210 |
211 lemma p_fac_forw: "[| (m::nat) > 0; k>0; k < p^a; (p^r) dvd (p^a)* m - k |] |
211 lemma p_fac_forw: "[| (m::nat) > 0; k>0; k < p^a; (p^r) dvd (p^a)* m - k |] |
212 ==> (p^r) dvd (p^a) - k" |
212 ==> (p^r) dvd (p^a) - k" |
213 apply (frule_tac k1 = k and i = p in p_fac_forw_lemma [THEN le_imp_power_dvd], auto) |
213 apply (frule p_fac_forw_lemma [THEN le_imp_power_dvd, of _ k p], auto) |
214 apply (subgoal_tac "p^r dvd p^a*m") |
214 apply (subgoal_tac "p^r dvd p^a*m") |
215 prefer 2 apply (blast intro: dvd_mult2) |
215 prefer 2 apply (blast intro: dvd_mult2) |
216 apply (drule dvd_diffD1) |
216 apply (drule dvd_diffD1) |
217 apply assumption |
217 apply assumption |
218 prefer 2 apply (blast intro: dvd_diff) |
218 prefer 2 apply (blast intro: nat_dvd_diff) |
219 apply (drule gr0_implies_Suc, auto) |
219 apply (drule gr0_implies_Suc, auto) |
220 done |
220 done |
221 |
221 |
222 |
222 |
223 lemma r_le_a_forw: |
223 lemma r_le_a_forw: |
224 "[| (k::nat) > 0; k < p^a; p>0; (p^r) dvd (p^a) - k |] ==> r <= a" |
224 "[| (k::nat) > 0; k < p^a; p>0; (p^r) dvd (p^a) - k |] ==> r <= a" |
225 by (rule_tac m = "Suc 0" in p_fac_forw_lemma, auto) |
225 by (rule_tac m = "Suc 0" in p_fac_forw_lemma, auto) |
226 |
226 |
227 lemma p_fac_backw: "[| m>0; k>0; (p::nat)\<noteq>0; k < p^a; (p^r) dvd p^a - k |] |
227 lemma p_fac_backw: "[| m>0; k>0; (p::nat)\<noteq>0; k < p^a; (p^r) dvd p^a - k |] |
228 ==> (p^r) dvd (p^a)*m - k" |
228 ==> (p^r) dvd (p^a)*m - k" |
229 apply (frule_tac k1 = k and i = p in r_le_a_forw [THEN le_imp_power_dvd], auto) |
229 apply (frule_tac k1 = k and p1 = p in r_le_a_forw [THEN le_imp_power_dvd], auto) |
230 apply (subgoal_tac "p^r dvd p^a*m") |
230 apply (subgoal_tac "p^r dvd p^a*m") |
231 prefer 2 apply (blast intro: dvd_mult2) |
231 prefer 2 apply (blast intro: dvd_mult2) |
232 apply (drule dvd_diffD1) |
232 apply (drule dvd_diffD1) |
233 apply assumption |
233 apply assumption |
234 prefer 2 apply (blast intro: dvd_diff) |
234 prefer 2 apply (blast intro: nat_dvd_diff) |
235 apply (drule less_imp_Suc_add, auto) |
235 apply (drule less_imp_Suc_add, auto) |
236 done |
236 done |
237 |
237 |
238 lemma exponent_p_a_m_k_equation: "[| m>0; k>0; (p::nat)\<noteq>0; k < p^a |] |
238 lemma exponent_p_a_m_k_equation: "[| m>0; k>0; (p::nat)\<noteq>0; k < p^a |] |
239 ==> exponent p (p^a * m - k) = exponent p (p^a - k)" |
239 ==> exponent p (p^a * m - k) = exponent p (p^a - k)" |