[STATEMENT]
lemma qf1_prime_exists: "prime (4*k+1) \<Longrightarrow> is_sum2sq_nat (4*k+1)"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
proof -
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
let ?p = "4*k+1"
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
assume p: "prime ?p"
[PROOF STATE]
proof (state)
this:
prime (4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence "Legendre (-1) ?p = 1"
[PROOF STATE]
proof (prove)
using this:
prime (4 * k + 1)

goal (1 subgoal):
 1. Legendre (- 1) (int (4 * k + 1)) = 1
[PROOF STEP]
by (rule Legendre_1mod4)
[PROOF STATE]
proof (state)
this:
Legendre (- 1) (int (4 * k + 1)) = 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
Legendre (- 1) (int (4 * k + 1)) = 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
{
[PROOF STATE]
proof (state)
this:
Legendre (- 1) (int (4 * k + 1)) = 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
assume "\<not> QuadRes ?p (-1)"
[PROOF STATE]
proof (state)
this:
\<not> QuadRes (int (4 * k + 1)) (- 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence "Legendre (-1) ?p \<noteq> 1"
[PROOF STATE]
proof (prove)
using this:
\<not> QuadRes (int (4 * k + 1)) (- 1)

goal (1 subgoal):
 1. Legendre (- 1) (int (4 * k + 1)) \<noteq> 1
[PROOF STEP]
by (unfold Legendre_def, auto)
[PROOF STATE]
proof (state)
this:
Legendre (- 1) (int (4 * k + 1)) \<noteq> 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
\<not> QuadRes (int (4 * k + 1)) (- 1) \<Longrightarrow> Legendre (- 1) (int (4 * k + 1)) \<noteq> 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
Legendre (- 1) (int (4 * k + 1)) = 1
\<not> QuadRes (int (4 * k + 1)) (- 1) \<Longrightarrow> Legendre (- 1) (int (4 * k + 1)) \<noteq> 1
[PROOF STEP]
have "QuadRes ?p (-1)"
[PROOF STATE]
proof (prove)
using this:
Legendre (- 1) (int (4 * k + 1)) = 1
\<not> QuadRes (int (4 * k + 1)) (- 1) \<Longrightarrow> Legendre (- 1) (int (4 * k + 1)) \<noteq> 1

goal (1 subgoal):
 1. QuadRes (int (4 * k + 1)) (- 1)
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
QuadRes (int (4 * k + 1)) (- 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
QuadRes (int (4 * k + 1)) (- 1)
[PROOF STEP]
obtain s1 where s1: "[s1^2 = -1] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
QuadRes (int (4 * k + 1)) (- 1)

goal (1 subgoal):
 1. (\<And>s1. [s1\<^sup>2 = - 1] (mod int (4 * k + 1)) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (auto simp add: QuadRes_def)
[PROOF STATE]
proof (state)
this:
[s1\<^sup>2 = - 1] (mod int (4 * k + 1))

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence s1': "[s1^2 + 1 = 0] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
[s1\<^sup>2 = - 1] (mod int (4 * k + 1))

goal (1 subgoal):
 1. [s1\<^sup>2 + 1 = 0] (mod int (4 * k + 1))
[PROOF STEP]
by (simp add: cong_iff_dvd_diff)
[PROOF STATE]
proof (state)
this:
[s1\<^sup>2 + 1 = 0] (mod int (4 * k + 1))

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
define s2 where "s2 = nat \<bar>s1\<bar>"
[PROOF STATE]
proof (state)
this:
s2 = nat \<bar>s1\<bar>

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence "int (s2^2 + 1) = s1^2 + 1"
[PROOF STATE]
proof (prove)
using this:
s2 = nat \<bar>s1\<bar>

goal (1 subgoal):
 1. int (s2\<^sup>2 + 1) = s1\<^sup>2 + 1
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
int (s2\<^sup>2 + 1) = s1\<^sup>2 + 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
with s1'
[PROOF STATE]
proof (chain)
picking this:
[s1\<^sup>2 + 1 = 0] (mod int (4 * k + 1))
int (s2\<^sup>2 + 1) = s1\<^sup>2 + 1
[PROOF STEP]
have "[int (s2^2 + 1) = 0] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
[s1\<^sup>2 + 1 = 0] (mod int (4 * k + 1))
int (s2\<^sup>2 + 1) = s1\<^sup>2 + 1

goal (1 subgoal):
 1. [int (s2\<^sup>2 + 1) = 0] (mod int (4 * k + 1))
[PROOF STEP]
by presburger
[PROOF STATE]
proof (state)
this:
[int (s2\<^sup>2 + 1) = 0] (mod int (4 * k + 1))

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence s2: "[s2^2 + 1 = 0] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
[int (s2\<^sup>2 + 1) = 0] (mod int (4 * k + 1))

goal (1 subgoal):
 1. [s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[PROOF STEP]
using cong_int_iff
[PROOF STATE]
proof (prove)
using this:
[int (s2\<^sup>2 + 1) = 0] (mod int (4 * k + 1))
[int ?m = int ?q] (mod int ?n) = [?m = ?q] (mod ?n)

goal (1 subgoal):
 1. [s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[PROOF STEP]
by fastforce
[PROOF STATE]
proof (state)
this:
[s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
from p
[PROOF STATE]
proof (chain)
picking this:
prime (4 * k + 1)
[PROOF STEP]
have p0: "?p > 0"
[PROOF STATE]
proof (prove)
using this:
prime (4 * k + 1)

goal (1 subgoal):
 1. 0 < 4 * k + 1
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
0 < 4 * k + 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
0 < 4 * k + 1
[PROOF STEP]
obtain s where s0p: "0 \<le> s \<and> s < ?p \<and> [s2 = s] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
0 < 4 * k + 1

goal (1 subgoal):
 1. (\<And>s. 0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
using cong_less_unique_nat[of ?p]
[PROOF STATE]
proof (prove)
using this:
0 < 4 * k + 1
0 < 4 * k + 1 \<Longrightarrow> \<exists>!b. 0 \<le> b \<and> b < 4 * k + 1 \<and> [?a = b] (mod 4 * k + 1)

goal (1 subgoal):
 1. (\<And>s. 0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by fastforce
[PROOF STATE]
proof (state)
this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)
[PROOF STEP]
have "[s^2 = s2^2] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)

goal (1 subgoal):
 1. [s\<^sup>2 = s2\<^sup>2] (mod 4 * k + 1)
[PROOF STEP]
by (simp add: cong_sym cong_pow)
[PROOF STATE]
proof (state)
this:
[s\<^sup>2 = s2\<^sup>2] (mod 4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
with s2
[PROOF STATE]
proof (chain)
picking this:
[s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[s\<^sup>2 = s2\<^sup>2] (mod 4 * k + 1)
[PROOF STEP]
have s: "[s^2 + 1 = 0] (mod ?p)"
[PROOF STATE]
proof (prove)
using this:
[s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[s\<^sup>2 = s2\<^sup>2] (mod 4 * k + 1)

goal (1 subgoal):
 1. [s\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[PROOF STEP]
using cong_trans cong_add_rcancel_nat
[PROOF STATE]
proof (prove)
using this:
[s2\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[s\<^sup>2 = s2\<^sup>2] (mod 4 * k + 1)
\<lbrakk>[?b = ?c] (mod ?a); [?c = ?d] (mod ?a)\<rbrakk> \<Longrightarrow> [?b = ?d] (mod ?a)
[?x + ?a = ?y + ?a] (mod ?n) = [?x = ?y] (mod ?n)

goal (1 subgoal):
 1. [s\<^sup>2 + 1 = 0] (mod 4 * k + 1)
[PROOF STEP]
by blast
[PROOF STATE]
proof (state)
this:
[s\<^sup>2 + 1 = 0] (mod 4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence "?p dvd s^2 + 1"
[PROOF STATE]
proof (prove)
using this:
[s\<^sup>2 + 1 = 0] (mod 4 * k + 1)

goal (1 subgoal):
 1. 4 * k + 1 dvd s\<^sup>2 + 1
[PROOF STEP]
using cong_altdef_nat
[PROOF STATE]
proof (prove)
using this:
[s\<^sup>2 + 1 = 0] (mod 4 * k + 1)
?b \<le> ?a \<Longrightarrow> [?a = ?b] (mod ?m) = (?m dvd ?a - ?b)

goal (1 subgoal):
 1. 4 * k + 1 dvd s\<^sup>2 + 1
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
4 * k + 1 dvd s\<^sup>2 + 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
4 * k + 1 dvd s\<^sup>2 + 1
[PROOF STEP]
obtain t where t: "s^2 + 1 = ?p*t"
[PROOF STATE]
proof (prove)
using this:
4 * k + 1 dvd s\<^sup>2 + 1

goal (1 subgoal):
 1. (\<And>t. s\<^sup>2 + 1 = (4 * k + 1) * t \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (auto simp add: dvd_def)
[PROOF STATE]
proof (state)
this:
s\<^sup>2 + 1 = (4 * k + 1) * t

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence "?p*t = sum2sq_nat s 1"
[PROOF STATE]
proof (prove)
using this:
s\<^sup>2 + 1 = (4 * k + 1) * t

goal (1 subgoal):
 1. (4 * k + 1) * t = sum2sq_nat s 1
[PROOF STEP]
by (simp add: sum2sq_nat_def)
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * t = sum2sq_nat s 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence qf1pt: "is_sum2sq_nat (?p*t)"
[PROOF STATE]
proof (prove)
using this:
(4 * k + 1) * t = sum2sq_nat s 1

goal (1 subgoal):
 1. is_sum2sq_nat ((4 * k + 1) * t)
[PROOF STEP]
by (auto simp add: is_sum2sq_nat_def)
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat ((4 * k + 1) * t)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
have t_l_p: "t < ?p"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. t < 4 * k + 1
[PROOF STEP]
proof (rule ccontr)
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
assume "\<not> t < ?p"
[PROOF STATE]
proof (state)
this:
\<not> t < 4 * k + 1

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
hence "t > ?p - 1"
[PROOF STATE]
proof (prove)
using this:
\<not> t < 4 * k + 1

goal (1 subgoal):
 1. 4 * k + 1 - 1 < t
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
4 * k + 1 - 1 < t

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
with p0
[PROOF STATE]
proof (chain)
picking this:
0 < 4 * k + 1
4 * k + 1 - 1 < t
[PROOF STEP]
have "?p*(?p - 1) < ?p*t"
[PROOF STATE]
proof (prove)
using this:
0 < 4 * k + 1
4 * k + 1 - 1 < t

goal (1 subgoal):
 1. (4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * t
[PROOF STEP]
by (simp only: mult_less_mono2)
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * t

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * t

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
with t
[PROOF STATE]
proof (chain)
picking this:
s\<^sup>2 + 1 = (4 * k + 1) * t
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * t
[PROOF STEP]
have "\<dots> = s^2 + 1"
[PROOF STATE]
proof (prove)
using this:
s\<^sup>2 + 1 = (4 * k + 1) * t
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * t

goal (1 subgoal):
 1. (4 * k + 1) * t = s\<^sup>2 + 1
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * t = s\<^sup>2 + 1

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * t = s\<^sup>2 + 1

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
have "\<dots> \<le> ?p*(?p - 1) - ?p + 2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
proof -
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
from s0p
[PROOF STATE]
proof (chain)
picking this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)
[PROOF STEP]
have "s \<le> ?p - 1"
[PROOF STATE]
proof (prove)
using this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)

goal (1 subgoal):
 1. s \<le> 4 * k + 1 - 1
[PROOF STEP]
by (auto simp add: less_le)
[PROOF STATE]
proof (state)
this:
s \<le> 4 * k + 1 - 1

goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
with s0p
[PROOF STATE]
proof (chain)
picking this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)
s \<le> 4 * k + 1 - 1
[PROOF STEP]
have "s^2 \<le> (?p - 1)^2"
[PROOF STATE]
proof (prove)
using this:
0 \<le> s \<and> s < 4 * k + 1 \<and> [s2 = s] (mod 4 * k + 1)
s \<le> 4 * k + 1 - 1

goal (1 subgoal):
 1. s\<^sup>2 \<le> (4 * k + 1 - 1)\<^sup>2
[PROOF STEP]
by (simp only: power_mono)
[PROOF STATE]
proof (state)
this:
s\<^sup>2 \<le> (4 * k + 1 - 1)\<^sup>2

goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
s\<^sup>2 \<le> (4 * k + 1 - 1)\<^sup>2

goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
have "\<dots> = ?p*(?p - 1) - 1*(?p - 1)"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. (4 * k + 1 - 1)\<^sup>2 = (4 * k + 1) * (4 * k + 1 - 1) - 1 * (4 * k + 1 - 1)
[PROOF STEP]
by (simp only: power2_eq_square diff_mult_distrib)
[PROOF STATE]
proof (state)
this:
(4 * k + 1 - 1)\<^sup>2 = (4 * k + 1) * (4 * k + 1 - 1) - 1 * (4 * k + 1 - 1)

goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
finally
[PROOF STATE]
proof (chain)
picking this:
s\<^sup>2 \<le> (4 * k + 1) * (4 * k + 1 - 1) - 1 * (4 * k + 1 - 1)
[PROOF STEP]
show ?thesis
[PROOF STATE]
proof (prove)
using this:
s\<^sup>2 \<le> (4 * k + 1) * (4 * k + 1 - 1) - 1 * (4 * k + 1 - 1)

goal (1 subgoal):
 1. s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
s\<^sup>2 + 1 \<le> (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
finally
[PROOF STATE]
proof (chain)
picking this:
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2
[PROOF STEP]
have "?p < 2"
[PROOF STATE]
proof (prove)
using this:
(4 * k + 1) * (4 * k + 1 - 1) < (4 * k + 1) * (4 * k + 1 - 1) - (4 * k + 1) + 2

goal (1 subgoal):
 1. 4 * k + 1 < 2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
4 * k + 1 < 2

goal (1 subgoal):
 1. \<not> t < 4 * k + 1 \<Longrightarrow> False
[PROOF STEP]
with p
[PROOF STATE]
proof (chain)
picking this:
prime (4 * k + 1)
4 * k + 1 < 2
[PROOF STEP]
show False
[PROOF STATE]
proof (prove)
using this:
prime (4 * k + 1)
4 * k + 1 < 2

goal (1 subgoal):
 1. False
[PROOF STEP]
by (unfold prime_def, auto)
[PROOF STATE]
proof (state)
this:
False

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
t < 4 * k + 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
have tpos: "t \<ge> 1"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 1 \<le> t
[PROOF STEP]
proof (rule ccontr)
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
assume "\<not> t \<ge> 1"
[PROOF STATE]
proof (state)
this:
\<not> 1 \<le> t

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
hence "t < 1"
[PROOF STATE]
proof (prove)
using this:
\<not> 1 \<le> t

goal (1 subgoal):
 1. t < 1
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
t < 1

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
t < 1

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
{
[PROOF STATE]
proof (state)
this:
t < 1

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
assume "t = 0"
[PROOF STATE]
proof (state)
this:
t = 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
with t
[PROOF STATE]
proof (chain)
picking this:
s\<^sup>2 + 1 = (4 * k + 1) * t
t = 0
[PROOF STEP]
have "s^2 + 1 = 0"
[PROOF STATE]
proof (prove)
using this:
s\<^sup>2 + 1 = (4 * k + 1) * t
t = 0

goal (1 subgoal):
 1. s\<^sup>2 + 1 = 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
s\<^sup>2 + 1 = 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
t = 0 \<Longrightarrow> s\<^sup>2 + 1 = 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
t = 0 \<Longrightarrow> s\<^sup>2 + 1 = 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
{
[PROOF STATE]
proof (state)
this:
t = 0 \<Longrightarrow> s\<^sup>2 + 1 = 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
assume "t < 0"
[PROOF STATE]
proof (state)
this:
t < 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
with p0
[PROOF STATE]
proof (chain)
picking this:
0 < 4 * k + 1
t < 0
[PROOF STEP]
have "?p*t < ?p*0"
[PROOF STATE]
proof (prove)
using this:
0 < 4 * k + 1
t < 0

goal (1 subgoal):
 1. (4 * k + 1) * t < (4 * k + 1) * 0
[PROOF STEP]
by (simp only: zmult_zless_mono2)
[PROOF STATE]
proof (state)
this:
(4 * k + 1) * t < (4 * k + 1) * 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
with t
[PROOF STATE]
proof (chain)
picking this:
s\<^sup>2 + 1 = (4 * k + 1) * t
(4 * k + 1) * t < (4 * k + 1) * 0
[PROOF STEP]
have "s^2 + 1 < 0"
[PROOF STATE]
proof (prove)
using this:
s\<^sup>2 + 1 = (4 * k + 1) * t
(4 * k + 1) * t < (4 * k + 1) * 0

goal (1 subgoal):
 1. s\<^sup>2 + 1 < 0
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
s\<^sup>2 + 1 < 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
t < 0 \<Longrightarrow> s\<^sup>2 + 1 < 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
t < 0 \<Longrightarrow> s\<^sup>2 + 1 < 0

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
have "s^2 \<ge> 0"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 0 \<le> s\<^sup>2
[PROOF STEP]
by (simp only: zero_le_power2)
[PROOF STATE]
proof (state)
this:
0 \<le> s\<^sup>2

goal (1 subgoal):
 1. \<not> 1 \<le> t \<Longrightarrow> False
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
t < 1
t = 0 \<Longrightarrow> s\<^sup>2 + 1 = 0
t < 0 \<Longrightarrow> s\<^sup>2 + 1 < 0
0 \<le> s\<^sup>2
[PROOF STEP]
show False
[PROOF STATE]
proof (prove)
using this:
t < 1
t = 0 \<Longrightarrow> s\<^sup>2 + 1 = 0
t < 0 \<Longrightarrow> s\<^sup>2 + 1 < 0
0 \<le> s\<^sup>2

goal (1 subgoal):
 1. False
[PROOF STEP]
by (auto simp add: less_le)
[PROOF STATE]
proof (state)
this:
False

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
1 \<le> t

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
1 \<le> t

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
{
[PROOF STATE]
proof (state)
this:
1 \<le> t

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
assume t1: "t > 0"
[PROOF STATE]
proof (state)
this:
0 < t

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
0 < t
[PROOF STEP]
obtain tn where tn: "tn = t - 1"
[PROOF STATE]
proof (prove)
using this:
0 < t

goal (1 subgoal):
 1. (\<And>tn. tn = t - 1 \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
tn = t - 1

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
have "is_sum2sq_nat (?p*(1+ 0))" (is "?Q 0")
      \<comment> \<open>So, $Q~n =$ there exist $x,y$ such that $x^2+y^2 =(p*(1+ int(n)))$\<close>
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. is_sum2sq_nat ((4 * k + 1) * (1 + 0))
[PROOF STEP]
proof (rule ccontr)
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0)) \<Longrightarrow> False
[PROOF STEP]
assume nQ1: "\<not> ?Q 0"
[PROOF STATE]
proof (state)
this:
\<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0)) \<Longrightarrow> False
[PROOF STEP]
have "(1 + tn) < ?p \<Longrightarrow> \<not> ?Q tn"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 1 + tn < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + tn))
[PROOF STEP]
proof (induct tn rule: infinite_descent0)
[PROOF STATE]
proof (state)
goal (2 subgoals):
 1. 1 + 0 < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
 2. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
case 0
[PROOF STATE]
proof (state)
this:
1 + 0 < 4 * k + 1

goal (2 subgoals):
 1. 1 + 0 < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
 2. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
from nQ1
[PROOF STATE]
proof (chain)
picking this:
\<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
[PROOF STEP]
show "1+ 0 < ?p \<Longrightarrow> \<not> ?Q 0"
[PROOF STATE]
proof (prove)
using this:
\<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. 1 + 0 < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
1 + 0 < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
next
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
case (smaller n)
[PROOF STATE]
proof (state)
this:
0 < n
\<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
hence n0: "n > 0" and IH: "1+ n < ?p \<and> ?Q n"
[PROOF STATE]
proof (prove)
using this:
0 < n
\<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))

goal (1 subgoal):
 1. 0 < n &&& 1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
0 < n
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
0 < n
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
[PROOF STEP]
obtain x y where "x^2 + y^2 = int (?p*(1+ n))"
[PROOF STATE]
proof (prove)
using this:
0 < n
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))

goal (1 subgoal):
 1. (\<And>x y. x\<^sup>2 + y\<^sup>2 = int ((4 * k + 1) * (1 + n)) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
using is_sum2sq_int_nat_eq
[PROOF STATE]
proof (prove)
using this:
0 < n
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
is_sum2sq_nat ?n = is_sum2sq_int (int ?n)

goal (1 subgoal):
 1. (\<And>x y. x\<^sup>2 + y\<^sup>2 = int ((4 * k + 1) * (1 + n)) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (unfold is_sum2sq_int_def sum2sq_int_def, auto)
[PROOF STATE]
proof (state)
this:
x\<^sup>2 + y\<^sup>2 = int ((4 * k + 1) * (1 + n))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
hence xy: "x^2 + y^2 = (int ?p)*(int (1+ n))"
[PROOF STATE]
proof (prove)
using this:
x\<^sup>2 + y\<^sup>2 = int ((4 * k + 1) * (1 + n))

goal (1 subgoal):
 1. x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
[PROOF STEP]
unfolding of_nat_mult
[PROOF STATE]
proof (prove)
using this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)

goal (1 subgoal):
 1. x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
[PROOF STEP]
by presburger
[PROOF STATE]
proof (state)
this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
let ?n1 = "int (1 + n)"
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
from n0
[PROOF STATE]
proof (chain)
picking this:
0 < n
[PROOF STEP]
have n1pos: "?n1 > 0"
[PROOF STATE]
proof (prove)
using this:
0 < n

goal (1 subgoal):
 1. 0 < int (1 + n)
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
0 < int (1 + n)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
[PROOF STEP]
obtain r v where rv: "v = x-r*?n1 \<and> 2*\<bar>v\<bar> \<le> ?n1"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)

goal (1 subgoal):
 1. (\<And>v r. v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (frule_tac n="?n1" in best_division_abs, auto)
[PROOF STATE]
proof (state)
this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
from n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
[PROOF STEP]
obtain s w where sw: "w = y-s*?n1 \<and> 2*\<bar>w\<bar> \<le> ?n1"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)

goal (1 subgoal):
 1. (\<And>w s. w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (frule_tac n="?n1" in best_division_abs, auto)
[PROOF STATE]
proof (state)
this:
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
let ?C = "v^2 + w^2"
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
have "?n1 dvd ?C"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. int (1 + n) dvd v\<^sup>2 + w\<^sup>2
[PROOF STEP]
proof
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
from rv sw
[PROOF STATE]
proof (chain)
picking this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
[PROOF STEP]
have "?C = (x-r*?n1)^2 + (y-s*?n1)^2"
[PROOF STATE]
proof (prove)
using this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = (x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = (x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = (x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
have "\<dots> = x^2 + y^2 - 2*x*(r*?n1) - 2*y*(s*?n1) + (r*?n1)^2 + (s*?n1)^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. (x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2 = x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2
[PROOF STEP]
unfolding power2_eq_square
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. (x - r * int (1 + n)) * (x - r * int (1 + n)) + (y - s * int (1 + n)) * (y - s * int (1 + n)) = x * x + y * y - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + r * int (1 + n) * (r * int (1 + n)) + s * int (1 + n) * (s * int (1 + n))
[PROOF STEP]
by (simp add: algebra_simps)
[PROOF STATE]
proof (state)
this:
(x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2 = x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2 = x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
with xy
[PROOF STATE]
proof (chain)
picking this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
(x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2 = x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2
[PROOF STEP]
have "\<dots> = ?n1*?p - ?n1*(2*x*r) - ?n1*(2*y*s) + ?n1^2*r^2 + ?n1^2*s^2"
[PROOF STATE]
proof (prove)
using this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
(x - r * int (1 + n))\<^sup>2 + (y - s * int (1 + n))\<^sup>2 = x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2

goal (1 subgoal):
 1. x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2 = int (1 + n) * int (4 * k + 1) - int (1 + n) * (2 * x * r) - int (1 + n) * (2 * y * s) + (int (1 + n))\<^sup>2 * r\<^sup>2 + (int (1 + n))\<^sup>2 * s\<^sup>2
[PROOF STEP]
by (simp only: ac_simps power_mult_distrib)
[PROOF STATE]
proof (state)
this:
x\<^sup>2 + y\<^sup>2 - 2 * x * (r * int (1 + n)) - 2 * y * (s * int (1 + n)) + (r * int (1 + n))\<^sup>2 + (s * int (1 + n))\<^sup>2 = int (1 + n) * int (4 * k + 1) - int (1 + n) * (2 * x * r) - int (1 + n) * (2 * y * s) + (int (1 + n))\<^sup>2 * r\<^sup>2 + (int (1 + n))\<^sup>2 * s\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * ?k
[PROOF STEP]
finally
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * int (4 * k + 1) - int (1 + n) * (2 * x * r) - int (1 + n) * (2 * y * s) + (int (1 + n))\<^sup>2 * r\<^sup>2 + (int (1 + n))\<^sup>2 * s\<^sup>2
[PROOF STEP]
show "?C = ?n1*(?p - 2*x*r - 2*y*s + ?n1*(r^2 + s^2))"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * int (4 * k + 1) - int (1 + n) * (2 * x * r) - int (1 + n) * (2 * y * s) + (int (1 + n))\<^sup>2 * r\<^sup>2 + (int (1 + n))\<^sup>2 * s\<^sup>2

goal (1 subgoal):
 1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * (int (4 * k + 1) - 2 * x * r - 2 * y * s + int (1 + n) * (r\<^sup>2 + s\<^sup>2))
[PROOF STEP]
by (simp only: power_mult_distrib distrib_left ac_simps
              left_diff_distrib right_diff_distrib power2_eq_square)
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * (int (4 * k + 1) - 2 * x * r - 2 * y * s + int (1 + n) * (r\<^sup>2 + s\<^sup>2))

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
int (1 + n) dvd v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
int (1 + n) dvd v\<^sup>2 + w\<^sup>2
[PROOF STEP]
obtain m1 where m1: "?C = ?n1*m1"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) dvd v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. (\<And>m1. v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1 \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (auto simp add: dvd_def)
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
have mn: "m1 < ?n1"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. m1 < int (1 + n)
[PROOF STEP]
proof (rule ccontr)
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
assume "\<not> m1 < ?n1"
[PROOF STATE]
proof (state)
this:
\<not> m1 < int (1 + n)

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
hence "?n1-m1 \<le> 0"
[PROOF STATE]
proof (prove)
using this:
\<not> m1 < int (1 + n)

goal (1 subgoal):
 1. int (1 + n) - m1 \<le> 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
int (1 + n) - m1 \<le> 0

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
hence "4*?n1 - 4*m1 \<le> 0"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) - m1 \<le> 0

goal (1 subgoal):
 1. 4 * int (1 + n) - 4 * m1 \<le> 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
4 * int (1 + n) - 4 * m1 \<le> 0

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
with n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
4 * int (1 + n) - 4 * m1 \<le> 0
[PROOF STEP]
have "2*?n1 - 4*m1 < 0"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)
4 * int (1 + n) - 4 * m1 \<le> 0

goal (1 subgoal):
 1. 2 * int (1 + n) - 4 * m1 < 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
2 * int (1 + n) - 4 * m1 < 0

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
with n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
2 * int (1 + n) - 4 * m1 < 0
[PROOF STEP]
have "?n1*(2*?n1 - 4*m1) < ?n1*0"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)
2 * int (1 + n) - 4 * m1 < 0

goal (1 subgoal):
 1. int (1 + n) * (2 * int (1 + n) - 4 * m1) < int (1 + n) * 0
[PROOF STEP]
by (simp only: zmult_zless_mono2)
[PROOF STATE]
proof (state)
this:
int (1 + n) * (2 * int (1 + n) - 4 * m1) < int (1 + n) * 0

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
hence contr: "?n1*(2*?n1- 4*m1) < 0"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) * (2 * int (1 + n) - 4 * m1) < int (1 + n) * 0

goal (1 subgoal):
 1. int (1 + n) * (2 * int (1 + n) - 4 * m1) < 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
int (1 + n) * (2 * int (1 + n) - 4 * m1) < 0

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
have hlp: "2*\<bar>v\<bar> \<ge> 0 \<and> 2*\<bar>w\<bar> \<ge> 0"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
from m1
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
[PROOF STEP]
have "4*?n1*m1 = 4*v^2 + 4*w^2"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1

goal (1 subgoal):
 1. 4 * int (1 + n) * m1 = 4 * v\<^sup>2 + 4 * w\<^sup>2
[PROOF STEP]
by arith
[PROOF STATE]
proof (state)
this:
4 * int (1 + n) * m1 = 4 * v\<^sup>2 + 4 * w\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
4 * int (1 + n) * m1 = 4 * v\<^sup>2 + 4 * w\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
have "\<dots> = (2*\<bar>v\<bar>)^2 + (2*\<bar>w\<bar>)^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 4 * v\<^sup>2 + 4 * w\<^sup>2 = (2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2
[PROOF STEP]
by (auto simp add: power_mult_distrib)
[PROOF STATE]
proof (state)
this:
4 * v\<^sup>2 + 4 * w\<^sup>2 = (2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
4 * v\<^sup>2 + 4 * w\<^sup>2 = (2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
from rv hlp
[PROOF STATE]
proof (chain)
picking this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>
[PROOF STEP]
have "\<dots> \<le> ?n1^2 + (2*\<bar>w\<bar>)^2"
[PROOF STATE]
proof (prove)
using this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>

goal (1 subgoal):
 1. (2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2
[PROOF STEP]
using power_mono [of "2*\<bar>b\<bar>" "1 + int n" 2 for b]
[PROOF STATE]
proof (prove)
using this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>
\<lbrakk>2 * \<bar>?b2\<bar> \<le> 1 + int n; 0 \<le> 2 * \<bar>?b2\<bar>\<rbrakk> \<Longrightarrow> (2 * \<bar>?b2\<bar>)\<^sup>2 \<le> (1 + int n)\<^sup>2

goal (1 subgoal):
 1. (2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
(2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(2 * \<bar>v\<bar>)\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
from sw hlp
[PROOF STATE]
proof (chain)
picking this:
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>
[PROOF STEP]
have "\<dots> \<le> ?n1^2 + ?n1^2"
[PROOF STATE]
proof (prove)
using this:
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (int (1 + n))\<^sup>2
[PROOF STEP]
using power_mono [of "2*\<bar>b\<bar>" "1 + int n" 2 for b]
[PROOF STATE]
proof (prove)
using this:
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
0 \<le> 2 * \<bar>v\<bar> \<and> 0 \<le> 2 * \<bar>w\<bar>
\<lbrakk>2 * \<bar>?b2\<bar> \<le> 1 + int n; 0 \<le> 2 * \<bar>?b2\<bar>\<rbrakk> \<Longrightarrow> (2 * \<bar>?b2\<bar>)\<^sup>2 \<le> (1 + int n)\<^sup>2

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (int (1 + n))\<^sup>2
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 + (2 * \<bar>w\<bar>)\<^sup>2 \<le> (int (1 + n))\<^sup>2 + (int (1 + n))\<^sup>2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
finally
[PROOF STATE]
proof (chain)
picking this:
4 * int (1 + n) * m1 \<le> (int (1 + n))\<^sup>2 + (int (1 + n))\<^sup>2
[PROOF STEP]
have "?n1*m1*4 \<le> ?n1*?n1*2"
[PROOF STATE]
proof (prove)
using this:
4 * int (1 + n) * m1 \<le> (int (1 + n))\<^sup>2 + (int (1 + n))\<^sup>2

goal (1 subgoal):
 1. int (1 + n) * m1 * 4 \<le> int (1 + n) * int (1 + n) * 2
[PROOF STEP]
by (simp add: power2_eq_square ac_simps)
[PROOF STATE]
proof (state)
this:
int (1 + n) * m1 * 4 \<le> int (1 + n) * int (1 + n) * 2

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
hence "?n1*(2*?n1- 4*m1) \<ge> 0"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) * m1 * 4 \<le> int (1 + n) * int (1 + n) * 2

goal (1 subgoal):
 1. 0 \<le> int (1 + n) * (2 * int (1 + n) - 4 * m1)
[PROOF STEP]
by (simp only: right_diff_distrib ac_simps)
[PROOF STATE]
proof (state)
this:
0 \<le> int (1 + n) * (2 * int (1 + n) - 4 * m1)

goal (1 subgoal):
 1. \<not> m1 < int (1 + n) \<Longrightarrow> False
[PROOF STEP]
with contr
[PROOF STATE]
proof (chain)
picking this:
int (1 + n) * (2 * int (1 + n) - 4 * m1) < 0
0 \<le> int (1 + n) * (2 * int (1 + n) - 4 * m1)
[PROOF STEP]
show False
[PROOF STATE]
proof (prove)
using this:
int (1 + n) * (2 * int (1 + n) - 4 * m1) < 0
0 \<le> int (1 + n) * (2 * int (1 + n) - 4 * m1)

goal (1 subgoal):
 1. False
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
False

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
m1 < int (1 + n)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
have "?p*m1 = (r*v + s*w + m1)^2 + (r*w - s*v)^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
proof -
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
from m1 xy
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
[PROOF STEP]
have "(?p*?n1)*?C = (x^2+y^2)*(v^2+w^2)"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)

goal (1 subgoal):
 1. int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2)
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2)

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2)

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
have "\<dots> = (x*v + y*w)^2 + (x*w - y*v)^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. (x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2) = (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2
[PROOF STEP]
by (simp add: eval_nat_numeral field_simps)
[PROOF STATE]
proof (state)
this:
(x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2) = (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2) = (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
with rv sw
[PROOF STATE]
proof (chain)
picking this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
(x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2) = (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2
[PROOF STEP]
have "\<dots> = ((r*?n1+v)*v + (s*?n1+w)*w)^2 + ((r*?n1+v)*w - (s*?n1+w)*v)^2"
[PROOF STATE]
proof (prove)
using this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
(x\<^sup>2 + y\<^sup>2) * (v\<^sup>2 + w\<^sup>2) = (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2

goal (1 subgoal):
 1. (x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2 = ((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
(x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2 = ((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
(x * v + y * w)\<^sup>2 + (x * w - y * v)\<^sup>2 = ((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
have "\<dots> = (?n1*(r*v) + ?n1*(s*w) + (v^2+w^2))^2 + (?n1*(r*w) - ?n1*(s*v))^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. ((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2 = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + (v\<^sup>2 + w\<^sup>2))\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2
[PROOF STEP]
by (simp add: eval_nat_numeral field_simps)
[PROOF STATE]
proof (state)
this:
((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2 = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + (v\<^sup>2 + w\<^sup>2))\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
also
[PROOF STATE]
proof (state)
this:
((r * int (1 + n) + v) * v + (s * int (1 + n) + w) * w)\<^sup>2 + ((r * int (1 + n) + v) * w - (s * int (1 + n) + w) * v)\<^sup>2 = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + (v\<^sup>2 + w\<^sup>2))\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
from m1
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
[PROOF STEP]
have "\<dots> = (?n1*(r*v) + ?n1*(s*w) + ?n1*m1)^2 + (?n1*(r*w) - ?n1*(s*v))^2"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1

goal (1 subgoal):
 1. (int (1 + n) * (r * v) + int (1 + n) * (s * w) + (v\<^sup>2 + w\<^sup>2))\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2 = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + int (1 + n) * m1)\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
(int (1 + n) * (r * v) + int (1 + n) * (s * w) + (v\<^sup>2 + w\<^sup>2))\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2 = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + int (1 + n) * m1)\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
finally
[PROOF STATE]
proof (chain)
picking this:
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + int (1 + n) * m1)\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2
[PROOF STEP]
have "(?p*?n1)*?C = ?n1^2*(r*v + s*w + m1)^2 + ?n1^2*(r*w - s*v)^2"
[PROOF STATE]
proof (prove)
using this:
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n) * (r * v) + int (1 + n) * (s * w) + int (1 + n) * m1)\<^sup>2 + (int (1 + n) * (r * w) - int (1 + n) * (s * v))\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n))\<^sup>2 * (r * v + s * w + m1)\<^sup>2 + (int (1 + n))\<^sup>2 * (r * w - s * v)\<^sup>2
[PROOF STEP]
by (simp add: eval_nat_numeral field_simps)
[PROOF STATE]
proof (state)
this:
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n))\<^sup>2 * (r * v + s * w + m1)\<^sup>2 + (int (1 + n))\<^sup>2 * (r * w - s * v)\<^sup>2

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
with m1
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n))\<^sup>2 * (r * v + s * w + m1)\<^sup>2 + (int (1 + n))\<^sup>2 * (r * w - s * v)\<^sup>2
[PROOF STEP]
have "?n1^2*(?p*m1) = ?n1^2*((r*v + s*w + m1)^2 + (r*w - s*v)^2)"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
int (4 * k + 1) * int (1 + n) * (v\<^sup>2 + w\<^sup>2) = (int (1 + n))\<^sup>2 * (r * v + s * w + m1)\<^sup>2 + (int (1 + n))\<^sup>2 * (r * w - s * v)\<^sup>2

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1) = (int (1 + n))\<^sup>2 * ((r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2)
[PROOF STEP]
by (simp only: ac_simps power2_eq_square, simp add: distrib_left)
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1) = (int (1 + n))\<^sup>2 * ((r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2)

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
hence "?n1^2*(?p*m1 - (r*v+s*w+m1)^2 - (r*w-s*v)^2) = 0"
[PROOF STATE]
proof (prove)
using this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1) = (int (1 + n))\<^sup>2 * ((r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2)

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1 - (r * v + s * w + m1)\<^sup>2 - (r * w - s * v)\<^sup>2) = 0
[PROOF STEP]
by (auto simp add: distrib_left right_diff_distrib)
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1 - (r * v + s * w + m1)\<^sup>2 - (r * w - s * v)\<^sup>2) = 0

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1 - (r * v + s * w + m1)\<^sup>2 - (r * w - s * v)\<^sup>2) = 0

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
from n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
[PROOF STEP]
have "?n1^2 \<noteq> 0"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 \<noteq> 0
[PROOF STEP]
by (simp add: power2_eq_square)
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 \<noteq> 0

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1 - (r * v + s * w + m1)\<^sup>2 - (r * w - s * v)\<^sup>2) = 0
(int (1 + n))\<^sup>2 \<noteq> 0
[PROOF STEP]
show ?thesis
[PROOF STATE]
proof (prove)
using this:
(int (1 + n))\<^sup>2 * (int (4 * k + 1) * m1 - (r * v + s * w + m1)\<^sup>2 - (r * w - s * v)\<^sup>2) = 0
(int (1 + n))\<^sup>2 \<noteq> 0

goal (1 subgoal):
 1. int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
hence qf1pm1: "is_sum2sq_int ((int ?p)*m1)"
[PROOF STATE]
proof (prove)
using this:
int (4 * k + 1) * m1 = (r * v + s * w + m1)\<^sup>2 + (r * w - s * v)\<^sup>2

goal (1 subgoal):
 1. is_sum2sq_int (int (4 * k + 1) * m1)
[PROOF STEP]
by (unfold is_sum2sq_int_def sum2sq_int_def, auto)
[PROOF STATE]
proof (state)
this:
is_sum2sq_int (int (4 * k + 1) * m1)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
have m1pos: "m1 > 0"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
proof -
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
{
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
assume "v^2 + w^2 = 0"
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
hence "v = 0 \<and> w = 0"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = 0

goal (1 subgoal):
 1. v = 0 \<and> w = 0
[PROOF STEP]
using sum_power2_eq_zero_iff
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = 0
(?x\<^sup>2 + ?y\<^sup>2 = (0::?'a)) = (?x = (0::?'a) \<and> ?y = (0::?'a))

goal (1 subgoal):
 1. v = 0 \<and> w = 0
[PROOF STEP]
by blast
[PROOF STATE]
proof (state)
this:
v = 0 \<and> w = 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with rv sw
[PROOF STATE]
proof (chain)
picking this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
v = 0 \<and> w = 0
[PROOF STEP]
have "?n1 dvd x \<and> ?n1 dvd y"
[PROOF STATE]
proof (prove)
using this:
v = x - r * int (1 + n) \<and> 2 * \<bar>v\<bar> \<le> int (1 + n)
w = y - s * int (1 + n) \<and> 2 * \<bar>w\<bar> \<le> int (1 + n)
v = 0 \<and> w = 0

goal (1 subgoal):
 1. int (1 + n) dvd x \<and> int (1 + n) dvd y
[PROOF STEP]
by (unfold dvd_def, auto)
[PROOF STATE]
proof (state)
this:
int (1 + n) dvd x \<and> int (1 + n) dvd y

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
hence "?n1^2 dvd x^2 \<and> ?n1^2 dvd y^2"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) dvd x \<and> int (1 + n) dvd y

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 dvd x\<^sup>2 \<and> (int (1 + n))\<^sup>2 dvd y\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 dvd x\<^sup>2 \<and> (int (1 + n))\<^sup>2 dvd y\<^sup>2

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
hence "?n1^2 dvd x^2 + y^2"
[PROOF STATE]
proof (prove)
using this:
(int (1 + n))\<^sup>2 dvd x\<^sup>2 \<and> (int (1 + n))\<^sup>2 dvd y\<^sup>2

goal (1 subgoal):
 1. (int (1 + n))\<^sup>2 dvd x\<^sup>2 + y\<^sup>2
[PROOF STEP]
by (simp only: dvd_add)
[PROOF STATE]
proof (state)
this:
(int (1 + n))\<^sup>2 dvd x\<^sup>2 + y\<^sup>2

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with xy
[PROOF STATE]
proof (chain)
picking this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
(int (1 + n))\<^sup>2 dvd x\<^sup>2 + y\<^sup>2
[PROOF STEP]
have "?n1*?n1 dvd ?n1*?p"
[PROOF STATE]
proof (prove)
using this:
x\<^sup>2 + y\<^sup>2 = int (4 * k + 1) * int (1 + n)
(int (1 + n))\<^sup>2 dvd x\<^sup>2 + y\<^sup>2

goal (1 subgoal):
 1. int (1 + n) * int (1 + n) dvd int (1 + n) * int (4 * k + 1)
[PROOF STEP]
by (simp only: power2_eq_square ac_simps)
[PROOF STATE]
proof (state)
this:
int (1 + n) * int (1 + n) dvd int (1 + n) * int (4 * k + 1)

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
int (1 + n) * int (1 + n) dvd int (1 + n) * int (4 * k + 1)

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
from n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
[PROOF STEP]
have "?n1 \<noteq> 0"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)

goal (1 subgoal):
 1. int (1 + n) \<noteq> 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
int (1 + n) \<noteq> 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
int (1 + n) * int (1 + n) dvd int (1 + n) * int (4 * k + 1)
int (1 + n) \<noteq> 0
[PROOF STEP]
have "?n1 dvd ?p"
[PROOF STATE]
proof (prove)
using this:
int (1 + n) * int (1 + n) dvd int (1 + n) * int (4 * k + 1)
int (1 + n) \<noteq> 0

goal (1 subgoal):
 1. int (1 + n) dvd int (4 * k + 1)
[PROOF STEP]
by (rule zdvd_mult_cancel)
[PROOF STATE]
proof (state)
this:
int (1 + n) dvd int (4 * k + 1)

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
int (1 + n) dvd int (4 * k + 1)
[PROOF STEP]
have "?n1 \<ge> 0 \<and> ?n1 dvd ?p"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)
int (1 + n) dvd int (4 * k + 1)

goal (1 subgoal):
 1. 0 \<le> int (1 + n) \<and> int (1 + n) dvd int (4 * k + 1)
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
0 \<le> int (1 + n) \<and> int (1 + n) dvd int (4 * k + 1)

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with p
[PROOF STATE]
proof (chain)
picking this:
prime (4 * k + 1)
0 \<le> int (1 + n) \<and> int (1 + n) dvd int (4 * k + 1)
[PROOF STEP]
have "?n1 = 1 \<or> ?n1 = ?p"
[PROOF STATE]
proof (prove)
using this:
prime (4 * k + 1)
0 \<le> int (1 + n) \<and> int (1 + n) dvd int (4 * k + 1)

goal (1 subgoal):
 1. int (1 + n) = 1 \<or> int (1 + n) = int (4 * k + 1)
[PROOF STEP]
unfolding prime_nat_iff
[PROOF STATE]
proof (prove)
using this:
1 < 4 * k + 1 \<and> (\<forall>m. m dvd 4 * k + 1 \<longrightarrow> m = 1 \<or> m = 4 * k + 1)
0 \<le> int (1 + n) \<and> int (1 + n) dvd int (4 * k + 1)

goal (1 subgoal):
 1. int (1 + n) = 1 \<or> int (1 + n) = int (4 * k + 1)
[PROOF STEP]
by presburger
[PROOF STATE]
proof (state)
this:
int (1 + n) = 1 \<or> int (1 + n) = int (4 * k + 1)

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with IH
[PROOF STATE]
proof (chain)
picking this:
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
int (1 + n) = 1 \<or> int (1 + n) = int (4 * k + 1)
[PROOF STEP]
have "?Q 0"
[PROOF STATE]
proof (prove)
using this:
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
int (1 + n) = 1 \<or> int (1 + n) = int (4 * k + 1)

goal (1 subgoal):
 1. is_sum2sq_nat ((4 * k + 1) * (1 + 0))
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with nQ1
[PROOF STATE]
proof (chain)
picking this:
\<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
is_sum2sq_nat ((4 * k + 1) * (1 + 0))
[PROOF STEP]
have False
[PROOF STATE]
proof (prove)
using this:
\<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0))
is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. False
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
False

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = 0 \<Longrightarrow> False

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = 0 \<Longrightarrow> False

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
{
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + w\<^sup>2 = 0 \<Longrightarrow> False

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
assume "v^2 + 1*w^2 \<noteq> 0"
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
have "v^2 + w^2 \<ge> 0"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 0 \<le> v\<^sup>2 + w\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
0 \<le> v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0
0 \<le> v\<^sup>2 + w\<^sup>2
[PROOF STEP]
have vwpos: "v^2 + w^2 > 0"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0
0 \<le> v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. 0 < v\<^sup>2 + w\<^sup>2
[PROOF STEP]
by arith
[PROOF STATE]
proof (state)
this:
0 < v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
with m1
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
0 < v\<^sup>2 + w\<^sup>2
[PROOF STEP]
have "m1 \<noteq> 0"
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
0 < v\<^sup>2 + w\<^sup>2

goal (1 subgoal):
 1. m1 \<noteq> 0
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
m1 \<noteq> 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
m1 \<noteq> 0

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
have "m1 \<ge> 0"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 0 \<le> m1
[PROOF STEP]
proof (rule ccontr)
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. \<not> 0 \<le> m1 \<Longrightarrow> False
[PROOF STEP]
assume "\<not> m1 \<ge> 0"
[PROOF STATE]
proof (state)
this:
\<not> 0 \<le> m1

goal (1 subgoal):
 1. \<not> 0 \<le> m1 \<Longrightarrow> False
[PROOF STEP]
hence "m1 < 0"
[PROOF STATE]
proof (prove)
using this:
\<not> 0 \<le> m1

goal (1 subgoal):
 1. m1 < 0
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
m1 < 0

goal (1 subgoal):
 1. \<not> 0 \<le> m1 \<Longrightarrow> False
[PROOF STEP]
with n1pos
[PROOF STATE]
proof (chain)
picking this:
0 < int (1 + n)
m1 < 0
[PROOF STEP]
have "?n1*m1 < ?n1*0"
[PROOF STATE]
proof (prove)
using this:
0 < int (1 + n)
m1 < 0

goal (1 subgoal):
 1. int (1 + n) * m1 < int (1 + n) * 0
[PROOF STEP]
by (simp only: zmult_zless_mono2)
[PROOF STATE]
proof (state)
this:
int (1 + n) * m1 < int (1 + n) * 0

goal (1 subgoal):
 1. \<not> 0 \<le> m1 \<Longrightarrow> False
[PROOF STEP]
with m1 vwpos
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
0 < v\<^sup>2 + w\<^sup>2
int (1 + n) * m1 < int (1 + n) * 0
[PROOF STEP]
show False
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = int (1 + n) * m1
0 < v\<^sup>2 + w\<^sup>2
int (1 + n) * m1 < int (1 + n) * 0

goal (1 subgoal):
 1. False
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
False

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
0 \<le> m1

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
m1 \<noteq> 0
0 \<le> m1
[PROOF STEP]
have ?thesis
[PROOF STATE]
proof (prove)
using this:
m1 \<noteq> 0
0 \<le> m1

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
0 < m1

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0 \<Longrightarrow> 0 < m1

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
v\<^sup>2 + w\<^sup>2 = 0 \<Longrightarrow> False
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0 \<Longrightarrow> 0 < m1
[PROOF STEP]
show ?thesis
[PROOF STATE]
proof (prove)
using this:
v\<^sup>2 + w\<^sup>2 = 0 \<Longrightarrow> False
v\<^sup>2 + 1 * w\<^sup>2 \<noteq> 0 \<Longrightarrow> 0 < m1

goal (1 subgoal):
 1. 0 < m1
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
0 < m1

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
0 < m1

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
hence "1 + int((nat m1) - 1) = m1"
[PROOF STATE]
proof (prove)
using this:
0 < m1

goal (1 subgoal):
 1. 1 + int (nat m1 - 1) = m1
[PROOF STEP]
by arith
[PROOF STATE]
proof (state)
this:
1 + int (nat m1 - 1) = m1

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
with qf1pm1
[PROOF STATE]
proof (chain)
picking this:
is_sum2sq_int (int (4 * k + 1) * m1)
1 + int (nat m1 - 1) = m1
[PROOF STEP]
have Qm1: "?Q ((nat m1) - 1)"
[PROOF STATE]
proof (prove)
using this:
is_sum2sq_int (int (4 * k + 1) * m1)
1 + int (nat m1 - 1) = m1

goal (1 subgoal):
 1. is_sum2sq_nat ((4 * k + 1) * (1 + (nat m1 - 1)))
[PROOF STEP]
using is_sum2sq_int_nat_eq
[PROOF STATE]
proof (prove)
using this:
is_sum2sq_int (int (4 * k + 1) * m1)
1 + int (nat m1 - 1) = m1
is_sum2sq_nat ?n = is_sum2sq_int (int ?n)

goal (1 subgoal):
 1. is_sum2sq_nat ((4 * k + 1) * (1 + (nat m1 - 1)))
[PROOF STEP]
by (simp add: algebra_simps)
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat ((4 * k + 1) * (1 + (nat m1 - 1)))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
is_sum2sq_nat ((4 * k + 1) * (1 + (nat m1 - 1)))
[PROOF STEP]
obtain mm where tmp: "mm = (nat m1) - 1 \<and> ?Q mm"
[PROOF STATE]
proof (prove)
using this:
is_sum2sq_nat ((4 * k + 1) * (1 + (nat m1 - 1)))

goal (1 subgoal):
 1. (\<And>mm. mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm)) \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm))

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
have "mm<n"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. mm < n
[PROOF STEP]
using tmp mn m1pos
[PROOF STATE]
proof (prove)
using this:
mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm))
m1 < int (1 + n)
0 < m1

goal (1 subgoal):
 1. mm < n
[PROOF STEP]
by arith
[PROOF STATE]
proof (state)
this:
mm < n

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
moreover
[PROOF STATE]
proof (state)
this:
mm < n

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
with IH
[PROOF STATE]
proof (chain)
picking this:
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
mm < n
[PROOF STEP]
have "1 + int mm < ?p"
[PROOF STATE]
proof (prove)
using this:
1 + n < 4 * k + 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + n))
mm < n

goal (1 subgoal):
 1. 1 + int mm < int (4 * k + 1)
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
1 + int mm < int (4 * k + 1)

goal (1 subgoal):
 1. \<And>n. \<lbrakk>0 < n; \<not> (1 + n < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + n)))\<rbrakk> \<Longrightarrow> \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm))
mm < n
1 + int mm < int (4 * k + 1)
[PROOF STEP]
show ?case
[PROOF STATE]
proof (prove)
using this:
mm = nat m1 - 1 \<and> is_sum2sq_nat ((4 * k + 1) * (1 + mm))
mm < n
1 + int mm < int (4 * k + 1)

goal (1 subgoal):
 1. \<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
\<exists>m<n. \<not> (1 + m < 4 * k + 1 \<longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + m)))

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
1 + tn < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + tn))

goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0)) \<Longrightarrow> False
[PROOF STEP]
hence "\<not> is_sum2sq_nat (?p*t)"
[PROOF STATE]
proof (prove)
using this:
1 + tn < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + tn))

goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * t)
[PROOF STEP]
using tn tpos t_l_p
[PROOF STATE]
proof (prove)
using this:
1 + tn < 4 * k + 1 \<Longrightarrow> \<not> is_sum2sq_nat ((4 * k + 1) * (1 + tn))
tn = t - 1
1 \<le> t
t < 4 * k + 1

goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * t)
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
\<not> is_sum2sq_nat ((4 * k + 1) * t)

goal (1 subgoal):
 1. \<not> is_sum2sq_nat ((4 * k + 1) * (1 + 0)) \<Longrightarrow> False
[PROOF STEP]
with qf1pt
[PROOF STATE]
proof (chain)
picking this:
is_sum2sq_nat ((4 * k + 1) * t)
\<not> is_sum2sq_nat ((4 * k + 1) * t)
[PROOF STEP]
show False
[PROOF STATE]
proof (prove)
using this:
is_sum2sq_nat ((4 * k + 1) * t)
\<not> is_sum2sq_nat ((4 * k + 1) * t)

goal (1 subgoal):
 1. False
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
False

goal:
No subgoals!
[PROOF STEP]
qed
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
hence ?thesis
[PROOF STATE]
proof (prove)
using this:
is_sum2sq_nat ((4 * k + 1) * (1 + 0))

goal (1 subgoal):
 1. is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat (4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
}
[PROOF STATE]
proof (state)
this:
0 < t \<Longrightarrow> is_sum2sq_nat (4 * k + 1)

goal (1 subgoal):
 1. prime (4 * k + 1) \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
ultimately
[PROOF STATE]
proof (chain)
picking this:
1 \<le> t
0 < t \<Longrightarrow> is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
show ?thesis
[PROOF STATE]
proof (prove)
using this:
1 \<le> t
0 < t \<Longrightarrow> is_sum2sq_nat (4 * k + 1)

goal (1 subgoal):
 1. is_sum2sq_nat (4 * k + 1)
[PROOF STEP]
by (auto simp add: less_le)
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat (4 * k + 1)

goal:
No subgoals!
[PROOF STEP]
qed


[STATEMENT]
lemma fermat_two_squares: assumes "prime p" "(\<not> [p = 3] (mod 4))"
  shows "is_sum2sq_nat p"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. is_sum2sq_nat p
[PROOF STEP]
proof (cases "p=2")
[PROOF STATE]
proof (state)
goal (2 subgoals):
 1. p = 2 \<Longrightarrow> is_sum2sq_nat p
 2. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
case True
[PROOF STATE]
proof (state)
this:
p = 2

goal (2 subgoals):
 1. p = 2 \<Longrightarrow> is_sum2sq_nat p
 2. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
have "(2::nat)=1^2+1^2"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. 2 = 1\<^sup>2 + 1\<^sup>2
[PROOF STEP]
using power2_eq_square
[PROOF STATE]
proof (prove)
using this:
?a\<^sup>2 = ?a * ?a

goal (1 subgoal):
 1. 2 = 1\<^sup>2 + 1\<^sup>2
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
2 = 1\<^sup>2 + 1\<^sup>2

goal (2 subgoals):
 1. p = 2 \<Longrightarrow> is_sum2sq_nat p
 2. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
thus ?thesis
[PROOF STATE]
proof (prove)
using this:
2 = 1\<^sup>2 + 1\<^sup>2

goal (1 subgoal):
 1. is_sum2sq_nat p
[PROOF STEP]
unfolding is_sum2sq_nat_def sum2sq_nat_def
[PROOF STATE]
proof (prove)
using this:
2 = 1\<^sup>2 + 1\<^sup>2

goal (1 subgoal):
 1. \<exists>a b. p = a\<^sup>2 + b\<^sup>2
[PROOF STEP]
using True
[PROOF STATE]
proof (prove)
using this:
2 = 1\<^sup>2 + 1\<^sup>2
p = 2

goal (1 subgoal):
 1. \<exists>a b. p = a\<^sup>2 + b\<^sup>2
[PROOF STEP]
by fast
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat p

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
next
[PROOF STATE]
proof (state)
goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
case False
[PROOF STATE]
proof (state)
this:
p \<noteq> 2

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
hence "p > 2"
[PROOF STATE]
proof (prove)
using this:
p \<noteq> 2

goal (1 subgoal):
 1. 2 < p
[PROOF STEP]
using assms(1)
[PROOF STATE]
proof (prove)
using this:
p \<noteq> 2
prime p

goal (1 subgoal):
 1. 2 < p
[PROOF STEP]
unfolding prime_nat_iff
[PROOF STATE]
proof (prove)
using this:
p \<noteq> 2
1 < p \<and> (\<forall>m. m dvd p \<longrightarrow> m = 1 \<or> m = p)

goal (1 subgoal):
 1. 2 < p
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
2 < p

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
hence h1: "odd p"
[PROOF STATE]
proof (prove)
using this:
2 < p

goal (1 subgoal):
 1. odd p
[PROOF STEP]
using assms(1) prime_odd_nat
[PROOF STATE]
proof (prove)
using this:
2 < p
prime p
\<lbrakk>prime ?p; 2 < ?p\<rbrakk> \<Longrightarrow> odd ?p

goal (1 subgoal):
 1. odd p
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
odd p

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
hence h2: "\<not> [p = 0] (mod 4)"
[PROOF STATE]
proof (prove)
using this:
odd p

goal (1 subgoal):
 1. [p \<noteq> 0] (mod 4)
[PROOF STEP]
unfolding cong_def
[PROOF STATE]
proof (prove)
using this:
odd p

goal (1 subgoal):
 1. p mod 4 \<noteq> 0 mod 4
[PROOF STEP]
by fastforce
[PROOF STATE]
proof (state)
this:
[p \<noteq> 0] (mod 4)

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
have h3: "\<not> [p = 2] (mod 4)"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. [p \<noteq> 2] (mod 4)
[PROOF STEP]
using h1 cong_dvd_iff [of p 2 2] cong_dvd_modulus_nat
[PROOF STATE]
proof (prove)
using this:
odd p
[p = 2] (mod 2) \<Longrightarrow> even p = even 2
\<lbrakk>[?x = ?y] (mod ?m); ?n dvd ?m\<rbrakk> \<Longrightarrow> [?x = ?y] (mod ?n)

goal (1 subgoal):
 1. [p \<noteq> 2] (mod 4)
[PROOF STEP]
by auto
[PROOF STATE]
proof (state)
this:
[p \<noteq> 2] (mod 4)

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
obtain x where h4: "[p = x] (mod 4) \<and> x<4"
[PROOF STATE]
proof (prove)
goal (1 subgoal):
 1. (\<And>x. [p = x] (mod 4) \<and> x < 4 \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by (meson cong_less_unique_nat zero_less_numeral)
[PROOF STATE]
proof (state)
this:
[p = x] (mod 4) \<and> x < 4

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
from h1 h2 h3 h4 assms
[PROOF STATE]
proof (chain)
picking this:
odd p
[p \<noteq> 0] (mod 4)
[p \<noteq> 2] (mod 4)
[p = x] (mod 4) \<and> x < 4
prime p
[p \<noteq> 3] (mod 4)
[PROOF STEP]
have "x\<noteq>0 \<and> x\<noteq>2 \<and> x\<noteq>3 \<and> x<4"
[PROOF STATE]
proof (prove)
using this:
odd p
[p \<noteq> 0] (mod 4)
[p \<noteq> 2] (mod 4)
[p = x] (mod 4) \<and> x < 4
prime p
[p \<noteq> 3] (mod 4)

goal (1 subgoal):
 1. x \<noteq> 0 \<and> x \<noteq> 2 \<and> x \<noteq> 3 \<and> x < 4
[PROOF STEP]
by meson
[PROOF STATE]
proof (state)
this:
x \<noteq> 0 \<and> x \<noteq> 2 \<and> x \<noteq> 3 \<and> x < 4

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
hence "x=1"
[PROOF STATE]
proof (prove)
using this:
x \<noteq> 0 \<and> x \<noteq> 2 \<and> x \<noteq> 3 \<and> x < 4

goal (1 subgoal):
 1. x = 1
[PROOF STEP]
by linarith
[PROOF STATE]
proof (state)
this:
x = 1

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
from this h4
[PROOF STATE]
proof (chain)
picking this:
x = 1
[p = x] (mod 4) \<and> x < 4
[PROOF STEP]
have "[p = 1] (mod 4)"
[PROOF STATE]
proof (prove)
using this:
x = 1
[p = x] (mod 4) \<and> x < 4

goal (1 subgoal):
 1. [p = 1] (mod 4)
[PROOF STEP]
by simp
[PROOF STATE]
proof (state)
this:
[p = 1] (mod 4)

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
then
[PROOF STATE]
proof (chain)
picking this:
[p = 1] (mod 4)
[PROOF STEP]
obtain k where "p = 4*k+1"
[PROOF STATE]
proof (prove)
using this:
[p = 1] (mod 4)

goal (1 subgoal):
 1. (\<And>k. p = 4 * k + 1 \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
using aux_lemma
[PROOF STATE]
proof (prove)
using this:
[p = 1] (mod 4)
\<lbrakk>[?a = ?b] (mod ?c); ?b < ?c\<rbrakk> \<Longrightarrow> \<exists>k. ?a = ?c * k + ?b

goal (1 subgoal):
 1. (\<And>k. p = 4 * k + 1 \<Longrightarrow> thesis) \<Longrightarrow> thesis
[PROOF STEP]
by fastforce
[PROOF STATE]
proof (state)
this:
p = 4 * k + 1

goal (1 subgoal):
 1. p \<noteq> 2 \<Longrightarrow> is_sum2sq_nat p
[PROOF STEP]
thus ?thesis
[PROOF STATE]
proof (prove)
using this:
p = 4 * k + 1

goal (1 subgoal):
 1. is_sum2sq_nat p
[PROOF STEP]
using qf1_prime_exists assms
[PROOF STATE]
proof (prove)
using this:
p = 4 * k + 1
prime (4 * ?k + 1) \<Longrightarrow> is_sum2sq_nat (4 * ?k + 1)
prime p
[p \<noteq> 3] (mod 4)

goal (1 subgoal):
 1. is_sum2sq_nat p
[PROOF STEP]
by blast
[PROOF STATE]
proof (state)
this:
is_sum2sq_nat p

goal:
No subgoals!
[PROOF STEP]
qed