src/HOL/ex/Sqrt_Script.thy
author haftmann
Tue, 01 Sep 2009 15:39:33 +0200
changeset 32479 521cc9bf2958
parent 28952 15a4b2cf8c34
child 36778 739a9379e29b
permissions -rw-r--r--
some reorganization of number theory
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
28952
15a4b2cf8c34 made repository layout more coherent with logical distribution structure; stripped some $Id$s
haftmann
parents: 28001
diff changeset
     1
(*  Title:      HOL/ex/Sqrt_Script.thy
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     3
    Copyright   2001  University of Cambridge
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     4
*)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     5
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     6
header {* Square roots of primes are irrational (script version) *}
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
     7
15149
c5c4884634b7 new import syntax
nipkow
parents: 14288
diff changeset
     8
theory Sqrt_Script
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
     9
imports Complex_Main "~~/src/HOL/Number_Theory/Primes"
15149
c5c4884634b7 new import syntax
nipkow
parents: 14288
diff changeset
    10
begin
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    11
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    12
text {*
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    13
  \medskip Contrast this linear Isabelle/Isar script with Markus
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    14
  Wenzel's more mathematical version.
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    15
*}
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    16
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    17
subsection {* Preliminaries *}
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    18
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    19
lemma prime_nonzero:  "prime (p::nat) \<Longrightarrow> p \<noteq> 0"
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    20
  by (force simp add: prime_nat_def)
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    21
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    22
lemma prime_dvd_other_side:
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    23
    "(n::nat) * n = p * (k * k) \<Longrightarrow> prime p \<Longrightarrow> p dvd n"
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    24
  apply (subgoal_tac "p dvd n * n", blast dest: prime_dvd_mult_nat)
27651
16a26996c30e moved op dvd to theory Ring_and_Field; generalized a couple of lemmas
haftmann
parents: 21404
diff changeset
    25
  apply auto
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    26
  done
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    27
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    28
lemma reduction: "prime (p::nat) \<Longrightarrow>
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    29
    0 < k \<Longrightarrow> k * k = p * (j * j) \<Longrightarrow> k < p * j \<and> 0 < j"
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    30
  apply (rule ccontr)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    31
  apply (simp add: linorder_not_less)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    32
  apply (erule disjE)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    33
   apply (frule mult_le_mono, assumption)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    34
   apply auto
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    35
  apply (force simp add: prime_nat_def)
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    36
  done
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    37
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    38
lemma rearrange: "(j::nat) * (p * j) = k * k \<Longrightarrow> k * k = p * (j * j)"
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    39
  by (simp add: mult_ac)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    40
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    41
lemma prime_not_square:
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    42
    "prime (p::nat) \<Longrightarrow> (\<And>k. 0 < k \<Longrightarrow> m * m \<noteq> p * (k * k))"
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    43
  apply (induct m rule: nat_less_induct)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    44
  apply clarify
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    45
  apply (frule prime_dvd_other_side, assumption)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    46
  apply (erule dvdE)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    47
  apply (simp add: nat_mult_eq_cancel_disj prime_nonzero)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    48
  apply (blast dest: rearrange reduction)
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    49
  done
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    50
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    51
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    52
subsection {* Main theorem *}
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    53
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    54
text {*
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    55
  The square root of any prime number (including @{text 2}) is
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    56
  irrational.
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    57
*}
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    58
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    59
theorem prime_sqrt_irrational:
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    60
    "prime (p::nat) \<Longrightarrow> x * x = real p \<Longrightarrow> 0 \<le> x \<Longrightarrow> x \<notin> \<rat>"
28001
4642317e0deb Defined rationals (Rats) globally in Rational.
nipkow
parents: 27651
diff changeset
    61
  apply (rule notI)
4642317e0deb Defined rationals (Rats) globally in Rational.
nipkow
parents: 27651
diff changeset
    62
  apply (erule Rats_abs_nat_div_natE)
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    63
  apply (simp del: real_of_nat_mult
28001
4642317e0deb Defined rationals (Rats) globally in Rational.
nipkow
parents: 27651
diff changeset
    64
              add: real_abs_def divide_eq_eq prime_not_square real_of_nat_mult [symmetric])
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    65
  done
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    66
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    67
lemmas two_sqrt_irrational =
32479
521cc9bf2958 some reorganization of number theory
haftmann
parents: 28952
diff changeset
    68
  prime_sqrt_irrational [OF two_is_prime_nat]
13957
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    69
10dbf16be15f new session Complex for the complex numbers
paulson
parents:
diff changeset
    70
end