Theorem plydivalg

Description: The division algorithm on polynomials over a subfield S of the complex numbers. If F and G =/= 0 are polynomials over S , then there is a unique quotient polynomial q such that the remainder F - G x. q is either zero or has degree less than G . (Contributed by Mario Carneiro, 26-Jul-2014)

	Ref	Expression
Hypotheses	plydiv.pl	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 + 𝑦 ) ∈ 𝑆 )
	plydiv.tm	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 · 𝑦 ) ∈ 𝑆 )
	plydiv.rc	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑥 ≠ 0 ) ) → ( 1 / 𝑥 ) ∈ 𝑆 )
	plydiv.m1	⊢ ( 𝜑 → - 1 ∈ 𝑆 )
	plydiv.f	⊢ ( 𝜑 → 𝐹 ∈ ( Poly ‘ 𝑆 ) )
	plydiv.g	⊢ ( 𝜑 → 𝐺 ∈ ( Poly ‘ 𝑆 ) )
	plydiv.z	⊢ ( 𝜑 → 𝐺 ≠ 0𝑝 )
	plydiv.r	⊢ 𝑅 = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) )
Assertion	plydivalg	⊢ ( 𝜑 → ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) )

Proof

Step	Hyp	Ref	Expression
1		plydiv.pl	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 + 𝑦 ) ∈ 𝑆 )
2		plydiv.tm	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 · 𝑦 ) ∈ 𝑆 )
3		plydiv.rc	⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑥 ≠ 0 ) ) → ( 1 / 𝑥 ) ∈ 𝑆 )
4		plydiv.m1	⊢ ( 𝜑 → - 1 ∈ 𝑆 )
5		plydiv.f	⊢ ( 𝜑 → 𝐹 ∈ ( Poly ‘ 𝑆 ) )
6		plydiv.g	⊢ ( 𝜑 → 𝐺 ∈ ( Poly ‘ 𝑆 ) )
7		plydiv.z	⊢ ( 𝜑 → 𝐺 ≠ 0𝑝 )
8		plydiv.r	⊢ 𝑅 = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) )
9	1 2 3 4 5 6 7 8	plydivex	⊢ ( 𝜑 → ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) )
10		simpll	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝜑 )
11	10 1	sylan	⊢ ( ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 + 𝑦 ) ∈ 𝑆 )
12	10 2	sylan	⊢ ( ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑦 ∈ 𝑆 ) ) → ( 𝑥 · 𝑦 ) ∈ 𝑆 )
13	10 3	sylan	⊢ ( ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) ∧ ( 𝑥 ∈ 𝑆 ∧ 𝑥 ≠ 0 ) ) → ( 1 / 𝑥 ) ∈ 𝑆 )
14	10 4	syl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → - 1 ∈ 𝑆 )
15	10 5	syl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝐹 ∈ ( Poly ‘ 𝑆 ) )
16	10 6	syl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝐺 ∈ ( Poly ‘ 𝑆 ) )
17	10 7	syl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝐺 ≠ 0𝑝 )
18		eqid	⊢ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) )
19		simplrr	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝑝 ∈ ( Poly ‘ 𝑆 ) )
20		simprr	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) )
21		simplrl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝑞 ∈ ( Poly ‘ 𝑆 ) )
22		simprl	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) )
23	11 12 13 14 15 16 17 18 19 20 8 21 22	plydiveu	⊢ ( ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) ∧ ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → 𝑞 = 𝑝 )
24	23	ex	⊢ ( ( 𝜑 ∧ ( 𝑞 ∈ ( Poly ‘ 𝑆 ) ∧ 𝑝 ∈ ( Poly ‘ 𝑆 ) ) ) → ( ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) → 𝑞 = 𝑝 ) )
25	24	ralrimivva	⊢ ( 𝜑 → ∀ 𝑞 ∈ ( Poly ‘ 𝑆 ) ∀ 𝑝 ∈ ( Poly ‘ 𝑆 ) ( ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) → 𝑞 = 𝑝 ) )
26		oveq2	⊢ ( 𝑞 = 𝑝 → ( 𝐺 ∘f · 𝑞 ) = ( 𝐺 ∘f · 𝑝 ) )
27	26	oveq2d	⊢ ( 𝑞 = 𝑝 → ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) )
28	8 27	syl5eq	⊢ ( 𝑞 = 𝑝 → 𝑅 = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) )
29	28	eqeq1d	⊢ ( 𝑞 = 𝑝 → ( 𝑅 = 0𝑝 ↔ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ) )
30	28	fveq2d	⊢ ( 𝑞 = 𝑝 → ( deg ‘ 𝑅 ) = ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) )
31	30	breq1d	⊢ ( 𝑞 = 𝑝 → ( ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ↔ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) )
32	29 31	orbi12d	⊢ ( 𝑞 = 𝑝 → ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ↔ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
33	32	reu4	⊢ ( ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ↔ ( ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ∀ 𝑞 ∈ ( Poly ‘ 𝑆 ) ∀ 𝑝 ∈ ( Poly ‘ 𝑆 ) ( ( ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ∧ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑝 ) ) ) < ( deg ‘ 𝐺 ) ) ) → 𝑞 = 𝑝 ) ) )
34	9 25 33	sylanbrc	⊢ ( 𝜑 → ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) )