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	sselid	⊢ ( 𝜑 → 𝐹 ∈ ( Poly ‘ ℂ ) )
25	23 6	sselid	⊢ ( 𝜑 → 𝐺 ∈ ( 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 ‘ 𝐺 ) ) ) )