src/HOL/ex/Sqrt_Script.thy
author haftmann
Fri Oct 10 19:55:32 2014 +0200 (2014-10-10)
changeset 58646 cd63a4b12a33
parent 57514 bdc2c6b40bf2
child 58889 5b7a9633cfa8
permissions -rw-r--r--
specialized specification: avoid trivial instances
haftmann@28952
     1
(*  Title:      HOL/ex/Sqrt_Script.thy
paulson@13957
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@13957
     3
    Copyright   2001  University of Cambridge
paulson@13957
     4
*)
paulson@13957
     5
paulson@13957
     6
header {* Square roots of primes are irrational (script version) *}
paulson@13957
     7
nipkow@15149
     8
theory Sqrt_Script
haftmann@32479
     9
imports Complex_Main "~~/src/HOL/Number_Theory/Primes"
nipkow@15149
    10
begin
paulson@13957
    11
paulson@13957
    12
text {*
paulson@13957
    13
  \medskip Contrast this linear Isabelle/Isar script with Markus
paulson@13957
    14
  Wenzel's more mathematical version.
paulson@13957
    15
*}
paulson@13957
    16
paulson@13957
    17
subsection {* Preliminaries *}
paulson@13957
    18
haftmann@32479
    19
lemma prime_nonzero:  "prime (p::nat) \<Longrightarrow> p \<noteq> 0"
haftmann@32479
    20
  by (force simp add: prime_nat_def)
paulson@13957
    21
paulson@13957
    22
lemma prime_dvd_other_side:
haftmann@32479
    23
    "(n::nat) * n = p * (k * k) \<Longrightarrow> prime p \<Longrightarrow> p dvd n"
haftmann@32479
    24
  apply (subgoal_tac "p dvd n * n", blast dest: prime_dvd_mult_nat)
haftmann@27651
    25
  apply auto
paulson@13957
    26
  done
paulson@13957
    27
haftmann@32479
    28
lemma reduction: "prime (p::nat) \<Longrightarrow>
paulson@13957
    29
    0 < k \<Longrightarrow> k * k = p * (j * j) \<Longrightarrow> k < p * j \<and> 0 < j"
paulson@13957
    30
  apply (rule ccontr)
paulson@13957
    31
  apply (simp add: linorder_not_less)
paulson@13957
    32
  apply (erule disjE)
paulson@13957
    33
   apply (frule mult_le_mono, assumption)
paulson@13957
    34
   apply auto
haftmann@32479
    35
  apply (force simp add: prime_nat_def)
paulson@13957
    36
  done
paulson@13957
    37
paulson@13957
    38
lemma rearrange: "(j::nat) * (p * j) = k * k \<Longrightarrow> k * k = p * (j * j)"
haftmann@57514
    39
  by (simp add: ac_simps)
paulson@13957
    40
paulson@13957
    41
lemma prime_not_square:
haftmann@32479
    42
    "prime (p::nat) \<Longrightarrow> (\<And>k. 0 < k \<Longrightarrow> m * m \<noteq> p * (k * k))"
paulson@13957
    43
  apply (induct m rule: nat_less_induct)
paulson@13957
    44
  apply clarify
paulson@13957
    45
  apply (frule prime_dvd_other_side, assumption)
paulson@13957
    46
  apply (erule dvdE)
paulson@13957
    47
  apply (simp add: nat_mult_eq_cancel_disj prime_nonzero)
paulson@13957
    48
  apply (blast dest: rearrange reduction)
paulson@13957
    49
  done
paulson@13957
    50
paulson@13957
    51
paulson@13957
    52
subsection {* Main theorem *}
paulson@13957
    53
paulson@13957
    54
text {*
paulson@13957
    55
  The square root of any prime number (including @{text 2}) is
paulson@13957
    56
  irrational.
paulson@13957
    57
*}
paulson@13957
    58
paulson@13957
    59
theorem prime_sqrt_irrational:
haftmann@32479
    60
    "prime (p::nat) \<Longrightarrow> x * x = real p \<Longrightarrow> 0 \<le> x \<Longrightarrow> x \<notin> \<rat>"
nipkow@28001
    61
  apply (rule notI)
nipkow@28001
    62
  apply (erule Rats_abs_nat_div_natE)
paulson@13957
    63
  apply (simp del: real_of_nat_mult
huffman@36778
    64
              add: abs_if divide_eq_eq prime_not_square real_of_nat_mult [symmetric])
paulson@13957
    65
  done
paulson@13957
    66
paulson@13957
    67
lemmas two_sqrt_irrational =
haftmann@32479
    68
  prime_sqrt_irrational [OF two_is_prime_nat]
paulson@13957
    69
paulson@13957
    70
end