This is an inofficial mirror of http://metamath.tirix.org for personal testing of a visualizer extension only.

Metamath Proof Explorer

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 eqtrid ⊢ ( 𝑞 = 𝑝 → 𝑅 = ( 𝐹 ∘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 ‘ 𝐺 ) ) )