Metamath Proof Explorer

Theorem quotlem

Description: Lemma for properties of the polynomial quotient function. (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𝑝 )
quotlem.8 ⊢ 𝑅 = ( 𝐹 ∘f − ( 𝐺 ∘f · ( 𝐹 quot 𝐺 ) ) )
Assertion quotlem ( 𝜑 → ( ( 𝐹 quot 𝐺 ) ∈ ( 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 quotlem.8 ⊢ 𝑅 = ( 𝐹 ∘f − ( 𝐺 ∘f · ( 𝐹 quot 𝐺 ) ) )
9 eqid ⊢ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) )
10 9 quotval ⊢ ( ( 𝐹 ∈ ( Poly ‘ 𝑆 ) ∧ 𝐺 ∈ ( Poly ‘ 𝑆 ) ∧ 𝐺 ≠ 0𝑝 ) → ( 𝐹 quot 𝐺 ) = ( ℩ 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
11 5 6 7 10 syl3anc ⊢ ( 𝜑 → ( 𝐹 quot 𝐺 ) = ( ℩ 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
12 1 2 3 4 5 6 7 9 plydivalg ⊢ ( 𝜑 → ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
13 reurex ⊢ ( ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) → ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
14 12 13 syl ⊢ ( 𝜑 → ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
15 addcl ⊢ ( ( 𝑥 ∈ ℂ ∧ 𝑦 ∈ ℂ ) → ( 𝑥 + 𝑦 ) ∈ ℂ )
16 15 adantl ⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ ℂ ∧ 𝑦 ∈ ℂ ) ) → ( 𝑥 + 𝑦 ) ∈ ℂ )
17 mulcl ⊢ ( ( 𝑥 ∈ ℂ ∧ 𝑦 ∈ ℂ ) → ( 𝑥 · 𝑦 ) ∈ ℂ )
18 17 adantl ⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ ℂ ∧ 𝑦 ∈ ℂ ) ) → ( 𝑥 · 𝑦 ) ∈ ℂ )
19 reccl ⊢ ( ( 𝑥 ∈ ℂ ∧ 𝑥 ≠ 0 ) → ( 1 / 𝑥 ) ∈ ℂ )
20 19 adantl ⊢ ( ( 𝜑 ∧ ( 𝑥 ∈ ℂ ∧ 𝑥 ≠ 0 ) ) → ( 1 / 𝑥 ) ∈ ℂ )
21 neg1cn ⊢ - 1 ∈ ℂ
22 21 a1i ⊢ ( 𝜑 → - 1 ∈ ℂ )
23 plyssc ⊢ ( Poly ‘ 𝑆 ) ⊆ ( Poly ‘ ℂ )
24 23 5 sseldi ⊢ ( 𝜑 → 𝐹 ∈ ( Poly ‘ ℂ ) )
25 23 6 sseldi ⊢ ( 𝜑 → 𝐺 ∈ ( Poly ‘ ℂ ) )
26 16 18 20 22 24 25 7 9 plydivalg ⊢ ( 𝜑 → ∃! 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
27 id ⊢ ( ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) → ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
28 27 rgenw ⊢ ∀ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) → ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) )
29 riotass2 ⊢ ( ( ( ( Poly ‘ 𝑆 ) ⊆ ( Poly ‘ ℂ ) ∧ ∀ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) → ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) ∧ ( ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ∧ ∃! 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) ) → ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) = ( ℩ 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
30 23 28 29 mpanl12 ⊢ ( ( ∃ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ∧ ∃! 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) → ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) = ( ℩ 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
31 14 26 30 syl2anc ⊢ ( 𝜑 → ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) = ( ℩ 𝑞 ∈ ( Poly ‘ ℂ ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
32 11 31 eqtr4d ⊢ ( 𝜑 → ( 𝐹 quot 𝐺 ) = ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) )
33 riotacl2 ⊢ ( ∃! 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) → ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) ∈ { 𝑞 ∈ ( Poly ‘ 𝑆 ) ∣ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) } )
34 12 33 syl ⊢ ( 𝜑 → ( ℩ 𝑞 ∈ ( Poly ‘ 𝑆 ) ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ) ∈ { 𝑞 ∈ ( Poly ‘ 𝑆 ) ∣ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) } )
35 32 34 eqeltrd ⊢ ( 𝜑 → ( 𝐹 quot 𝐺 ) ∈ { 𝑞 ∈ ( Poly ‘ 𝑆 ) ∣ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) } )
36 oveq2 ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( 𝐺 ∘f · 𝑞 ) = ( 𝐺 ∘f · ( 𝐹 quot 𝐺 ) ) )
37 36 oveq2d ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = ( 𝐹 ∘f − ( 𝐺 ∘f · ( 𝐹 quot 𝐺 ) ) ) )
38 37 8 eqtr4di ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 𝑅 )
39 38 eqeq1d ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ↔ 𝑅 = 0𝑝 ) )
40 38 fveq2d ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) = ( deg ‘ 𝑅 ) )
41 40 breq1d ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ↔ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) )
42 39 41 orbi12d ⊢ ( 𝑞 = ( 𝐹 quot 𝐺 ) → ( ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) ↔ ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ) )
43 42 elrab ⊢ ( ( 𝐹 quot 𝐺 ) ∈ { 𝑞 ∈ ( Poly ‘ 𝑆 ) ∣ ( ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) = 0𝑝 ∨ ( deg ‘ ( 𝐹 ∘f − ( 𝐺 ∘f · 𝑞 ) ) ) < ( deg ‘ 𝐺 ) ) } ↔ ( ( 𝐹 quot 𝐺 ) ∈ ( Poly ‘ 𝑆 ) ∧ ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ) )
44 35 43 sylib ⊢ ( 𝜑 → ( ( 𝐹 quot 𝐺 ) ∈ ( Poly ‘ 𝑆 ) ∧ ( 𝑅 = 0𝑝 ∨ ( deg ‘ 𝑅 ) < ( deg ‘ 𝐺 ) ) ) )