4sqlem11 - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > 4sqlem11		Structured version Visualization version GIF version

Theorem 4sqlem11 16888

Description: Lemma for 4sq 16897. Use the pigeonhole principle to show that the sets {𝑚↑2 ∣ 𝑚 ∈ (0...𝑁)} and {-1 − 𝑛↑2 ∣ 𝑛 ∈ (0...𝑁)} have a common element, mod 𝑃. (Contributed by Mario Carneiro, 15-Jul-2014.)

**Hypotheses**
Ref	Expression
4sq.1	⊢ 𝑆 = {𝑛 ∣ ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ ∃𝑧 ∈ ℤ ∃𝑤 ∈ ℤ 𝑛 = (((𝑥↑2) + (𝑦↑2)) + ((𝑧↑2) + (𝑤↑2)))}
4sq.2	⊢ (𝜑 → 𝑁 ∈ ℕ)
4sq.3	⊢ (𝜑 → 𝑃 = ((2 · 𝑁) + 1))
4sq.4	⊢ (𝜑 → 𝑃 ∈ ℙ)
4sqlem11.5	⊢ 𝐴 = {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)}
4sqlem11.6	⊢ 𝐹 = (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣))

**Assertion**
Ref	Expression
4sqlem11	⊢ (𝜑 → (𝐴 ∩ ran 𝐹) ≠ ∅)

Distinct variable groups: 𝑤,𝑛,𝑥,𝑦,𝑧 𝑣,𝑛,𝐴 𝑛,𝐹 𝑢,𝑛,𝑚,𝑣,𝑁 𝑃,𝑚,𝑛,𝑢,𝑣 𝜑,𝑚,𝑛,𝑢,𝑣 𝑆,𝑚,𝑛,𝑢,𝑣 Allowed substitution hints: 𝜑(𝑥,𝑦,𝑧,𝑤) 𝐴(𝑥,𝑦,𝑧,𝑤,𝑢,𝑚) 𝑃(𝑥,𝑦,𝑧,𝑤) 𝑆(𝑥,𝑦,𝑧,𝑤) 𝐹(𝑥,𝑦,𝑧,𝑤,𝑣,𝑢,𝑚) 𝑁(𝑥,𝑦,𝑧,𝑤)

Proof of Theorem 4sqlem11 Dummy variable 𝑘 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		fzfid 13938	. . . . . 6 ⊢ (𝜑 → (0...(𝑃 − 1)) ∈ Fin)
2		4sqlem11.5	. . . . . . . 8 ⊢ 𝐴 = {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)}
3		elfzelz 13501	. . . . . . . . . . . . 13 ⊢ (𝑚 ∈ (0...𝑁) → 𝑚 ∈ ℤ)
4		zsqcl 14094	. . . . . . . . . . . . 13 ⊢ (𝑚 ∈ ℤ → (𝑚↑2) ∈ ℤ)
5	3, 4	syl 17	. . . . . . . . . . . 12 ⊢ (𝑚 ∈ (0...𝑁) → (𝑚↑2) ∈ ℤ)
6		4sq.4	. . . . . . . . . . . . 13 ⊢ (𝜑 → 𝑃 ∈ ℙ)
7		prmnn 16611	. . . . . . . . . . . . 13 ⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
8	6, 7	syl 17	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝑃 ∈ ℕ)
9		zmodfz 13858	. . . . . . . . . . . 12 ⊢ (((𝑚↑2) ∈ ℤ ∧ 𝑃 ∈ ℕ) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)))
10	5, 8, 9	syl2anr 598	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑚 ∈ (0...𝑁)) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)))
11		eleq1a 2829	. . . . . . . . . . 11 ⊢ (((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)) → (𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
12	10, 11	syl 17	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑚 ∈ (0...𝑁)) → (𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
13	12	rexlimdva 3156	. . . . . . . . 9 ⊢ (𝜑 → (∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
14	13	abssdv 4066	. . . . . . . 8 ⊢ (𝜑 → {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)} ⊆ (0...(𝑃 − 1)))
15	2, 14	eqsstrid 4031	. . . . . . 7 ⊢ (𝜑 → 𝐴 ⊆ (0...(𝑃 − 1)))
16		prmz 16612	. . . . . . . . . . . . . . . 16 ⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
17	6, 16	syl 17	. . . . . . . . . . . . . . 15 ⊢ (𝜑 → 𝑃 ∈ ℤ)
18		peano2zm 12605	. . . . . . . . . . . . . . 15 ⊢ (𝑃 ∈ ℤ → (𝑃 − 1) ∈ ℤ)
19	17, 18	syl 17	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (𝑃 − 1) ∈ ℤ)
20	19	zcnd 12667	. . . . . . . . . . . . 13 ⊢ (𝜑 → (𝑃 − 1) ∈ ℂ)
21	20	addlidd 11415	. . . . . . . . . . . 12 ⊢ (𝜑 → (0 + (𝑃 − 1)) = (𝑃 − 1))
22	21	oveq1d 7424	. . . . . . . . . . 11 ⊢ (𝜑 → ((0 + (𝑃 − 1)) − 𝑣) = ((𝑃 − 1) − 𝑣))
23	22	adantr 482	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑣 ∈ 𝐴) → ((0 + (𝑃 − 1)) − 𝑣) = ((𝑃 − 1) − 𝑣))
24	15	sselda 3983	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑣 ∈ 𝐴) → 𝑣 ∈ (0...(𝑃 − 1)))
25		fzrev3i 13568	. . . . . . . . . . 11 ⊢ (𝑣 ∈ (0...(𝑃 − 1)) → ((0 + (𝑃 − 1)) − 𝑣) ∈ (0...(𝑃 − 1)))
26	24, 25	syl 17	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑣 ∈ 𝐴) → ((0 + (𝑃 − 1)) − 𝑣) ∈ (0...(𝑃 − 1)))
27	23, 26	eqeltrrd 2835	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑣 ∈ 𝐴) → ((𝑃 − 1) − 𝑣) ∈ (0...(𝑃 − 1)))
28		4sqlem11.6	. . . . . . . . 9 ⊢ 𝐹 = (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣))
29	27, 28	fmptd 7114	. . . . . . . 8 ⊢ (𝜑 → 𝐹:𝐴⟶(0...(𝑃 − 1)))
30	29	frnd 6726	. . . . . . 7 ⊢ (𝜑 → ran 𝐹 ⊆ (0...(𝑃 − 1)))
31	15, 30	unssd 4187	. . . . . 6 ⊢ (𝜑 → (𝐴 ∪ ran 𝐹) ⊆ (0...(𝑃 − 1)))
32	1, 31	ssfid 9267	. . . . 5 ⊢ (𝜑 → (𝐴 ∪ ran 𝐹) ∈ Fin)
33		hashcl 14316	. . . . 5 ⊢ ((𝐴 ∪ ran 𝐹) ∈ Fin → (♯‘(𝐴 ∪ ran 𝐹)) ∈ ℕ₀)
34	32, 33	syl 17	. . . 4 ⊢ (𝜑 → (♯‘(𝐴 ∪ ran 𝐹)) ∈ ℕ₀)
35	34	nn0red 12533	. . 3 ⊢ (𝜑 → (♯‘(𝐴 ∪ ran 𝐹)) ∈ ℝ)
36	17	zred 12666	. . 3 ⊢ (𝜑 → 𝑃 ∈ ℝ)
37		ssdomg 8996	. . . . . 6 ⊢ ((0...(𝑃 − 1)) ∈ Fin → ((𝐴 ∪ ran 𝐹) ⊆ (0...(𝑃 − 1)) → (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
38	1, 31, 37	sylc 65	. . . . 5 ⊢ (𝜑 → (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1)))
39		hashdom 14339	. . . . . 6 ⊢ (((𝐴 ∪ ran 𝐹) ∈ Fin ∧ (0...(𝑃 − 1)) ∈ Fin) → ((♯‘(𝐴 ∪ ran 𝐹)) ≤ (♯‘(0...(𝑃 − 1))) ↔ (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
40	32, 1, 39	syl2anc 585	. . . . 5 ⊢ (𝜑 → ((♯‘(𝐴 ∪ ran 𝐹)) ≤ (♯‘(0...(𝑃 − 1))) ↔ (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
41	38, 40	mpbird 257	. . . 4 ⊢ (𝜑 → (♯‘(𝐴 ∪ ran 𝐹)) ≤ (♯‘(0...(𝑃 − 1))))
42		fz01en 13529	. . . . . . 7 ⊢ (𝑃 ∈ ℤ → (0...(𝑃 − 1)) ≈ (1...𝑃))
43	17, 42	syl 17	. . . . . 6 ⊢ (𝜑 → (0...(𝑃 − 1)) ≈ (1...𝑃))
44		fzfid 13938	. . . . . . 7 ⊢ (𝜑 → (1...𝑃) ∈ Fin)
45		hashen 14307	. . . . . . 7 ⊢ (((0...(𝑃 − 1)) ∈ Fin ∧ (1...𝑃) ∈ Fin) → ((♯‘(0...(𝑃 − 1))) = (♯‘(1...𝑃)) ↔ (0...(𝑃 − 1)) ≈ (1...𝑃)))
46	1, 44, 45	syl2anc 585	. . . . . 6 ⊢ (𝜑 → ((♯‘(0...(𝑃 − 1))) = (♯‘(1...𝑃)) ↔ (0...(𝑃 − 1)) ≈ (1...𝑃)))
47	43, 46	mpbird 257	. . . . 5 ⊢ (𝜑 → (♯‘(0...(𝑃 − 1))) = (♯‘(1...𝑃)))
48	8	nnnn0d 12532	. . . . . 6 ⊢ (𝜑 → 𝑃 ∈ ℕ₀)
49		hashfz1 14306	. . . . . 6 ⊢ (𝑃 ∈ ℕ₀ → (♯‘(1...𝑃)) = 𝑃)
50	48, 49	syl 17	. . . . 5 ⊢ (𝜑 → (♯‘(1...𝑃)) = 𝑃)
51	47, 50	eqtrd 2773	. . . 4 ⊢ (𝜑 → (♯‘(0...(𝑃 − 1))) = 𝑃)
52	41, 51	breqtrd 5175	. . 3 ⊢ (𝜑 → (♯‘(𝐴 ∪ ran 𝐹)) ≤ 𝑃)
53	35, 36, 52	lensymd 11365	. 2 ⊢ (𝜑 → ¬ 𝑃 < (♯‘(𝐴 ∪ ran 𝐹)))
54	36	adantr 482	. . . . . 6 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 ∈ ℝ)
55	54	ltp1d 12144	. . . . 5 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 < (𝑃 + 1))
56		4sq.2	. . . . . . . . . 10 ⊢ (𝜑 → 𝑁 ∈ ℕ)
57	56	nncnd 12228	. . . . . . . . 9 ⊢ (𝜑 → 𝑁 ∈ ℂ)
58		1cnd 11209	. . . . . . . . 9 ⊢ (𝜑 → 1 ∈ ℂ)
59	57, 57, 58, 58	add4d 11442	. . . . . . . 8 ⊢ (𝜑 → ((𝑁 + 𝑁) + (1 + 1)) = ((𝑁 + 1) + (𝑁 + 1)))
60		4sq.3	. . . . . . . . . 10 ⊢ (𝜑 → 𝑃 = ((2 · 𝑁) + 1))
61	60	oveq1d 7424	. . . . . . . . 9 ⊢ (𝜑 → (𝑃 + 1) = (((2 · 𝑁) + 1) + 1))
62		2cn 12287	. . . . . . . . . . 11 ⊢ 2 ∈ ℂ
63		mulcl 11194	. . . . . . . . . . 11 ⊢ ((2 ∈ ℂ ∧ 𝑁 ∈ ℂ) → (2 · 𝑁) ∈ ℂ)
64	62, 57, 63	sylancr 588	. . . . . . . . . 10 ⊢ (𝜑 → (2 · 𝑁) ∈ ℂ)
65	64, 58, 58	addassd 11236	. . . . . . . . 9 ⊢ (𝜑 → (((2 · 𝑁) + 1) + 1) = ((2 · 𝑁) + (1 + 1)))
66	57	2timesd 12455	. . . . . . . . . 10 ⊢ (𝜑 → (2 · 𝑁) = (𝑁 + 𝑁))
67	66	oveq1d 7424	. . . . . . . . 9 ⊢ (𝜑 → ((2 · 𝑁) + (1 + 1)) = ((𝑁 + 𝑁) + (1 + 1)))
68	61, 65, 67	3eqtrd 2777	. . . . . . . 8 ⊢ (𝜑 → (𝑃 + 1) = ((𝑁 + 𝑁) + (1 + 1)))
69	10	ex 414	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → (𝑚 ∈ (0...𝑁) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1))))
70	8	adantr 482	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℕ)
71	3	ad2antrl 727	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℤ)
72	71, 4	syl 17	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚↑2) ∈ ℤ)
73		elfzelz 13501	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (𝑢 ∈ (0...𝑁) → 𝑢 ∈ ℤ)
74	73	ad2antll 728	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℤ)
75		zsqcl 14094	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (𝑢 ∈ ℤ → (𝑢↑2) ∈ ℤ)
76	74, 75	syl 17	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑢↑2) ∈ ℤ)
77		moddvds 16208	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃 ∈ ℕ ∧ (𝑚↑2) ∈ ℤ ∧ (𝑢↑2) ∈ ℤ) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑃 ∥ ((𝑚↑2) − (𝑢↑2))))
78	70, 72, 76, 77	syl3anc 1372	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑃 ∥ ((𝑚↑2) − (𝑢↑2))))
79	71	zcnd 12667	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℂ)
80	74	zcnd 12667	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℂ)
81		subsq 14174	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑚 ∈ ℂ ∧ 𝑢 ∈ ℂ) → ((𝑚↑2) − (𝑢↑2)) = ((𝑚 + 𝑢) · (𝑚 − 𝑢)))
82	79, 80, 81	syl2anc 585	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚↑2) − (𝑢↑2)) = ((𝑚 + 𝑢) · (𝑚 − 𝑢)))
83	82	breq2d 5161	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ ((𝑚↑2) − (𝑢↑2)) ↔ 𝑃 ∥ ((𝑚 + 𝑢) · (𝑚 − 𝑢))))
84	6	adantr 482	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℙ)
85	71, 74	zaddcld 12670	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ∈ ℤ)
86	71, 74	zsubcld 12671	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 − 𝑢) ∈ ℤ)
87		euclemma 16650	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝑃 ∈ ℙ ∧ (𝑚 + 𝑢) ∈ ℤ ∧ (𝑚 − 𝑢) ∈ ℤ) → (𝑃 ∥ ((𝑚 + 𝑢) · (𝑚 − 𝑢)) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚 − 𝑢))))
88	84, 85, 86, 87	syl3anc 1372	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ ((𝑚 + 𝑢) · (𝑚 − 𝑢)) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚 − 𝑢))))
89	78, 83, 88	3bitrd 305	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚 − 𝑢))))
90	85	zred 12666	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ∈ ℝ)
91		2re 12286	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ 2 ∈ ℝ
92	56	nnred 12227	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (𝜑 → 𝑁 ∈ ℝ)
93		remulcl 11195	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((2 ∈ ℝ ∧ 𝑁 ∈ ℝ) → (2 · 𝑁) ∈ ℝ)
94	91, 92, 93	sylancr 588	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ (𝜑 → (2 · 𝑁) ∈ ℝ)
95	94	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) ∈ ℝ)
96	84, 16	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℤ)
97	96	zred 12666	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℝ)
98	71	zred 12666	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℝ)
99	74	zred 12666	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℝ)
100	92	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑁 ∈ ℝ)
101		elfzle2 13505	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ (𝑚 ∈ (0...𝑁) → 𝑚 ≤ 𝑁)
102	101	ad2antrl 727	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ≤ 𝑁)
103		elfzle2 13505	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ (𝑢 ∈ (0...𝑁) → 𝑢 ≤ 𝑁)
104	103	ad2antll 728	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ≤ 𝑁)
105	98, 99, 100, 100, 102, 104	le2addd 11833	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ≤ (𝑁 + 𝑁))
106	57	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑁 ∈ ℂ)
107	106	2timesd 12455	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) = (𝑁 + 𝑁))
108	105, 107	breqtrrd 5177	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ≤ (2 · 𝑁))
109	94	ltp1d 12144	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (𝜑 → (2 · 𝑁) < ((2 · 𝑁) + 1))
110	109, 60	breqtrrd 5177	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ (𝜑 → (2 · 𝑁) < 𝑃)
111	110	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) < 𝑃)
112	90, 95, 97, 108, 111	lelttrd 11372	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) < 𝑃)
113	90, 97	ltnled 11361	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚 + 𝑢) < 𝑃 ↔ ¬ 𝑃 ≤ (𝑚 + 𝑢)))
114	112, 113	mpbid 231	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ¬ 𝑃 ≤ (𝑚 + 𝑢))
115	114	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → ¬ 𝑃 ≤ (𝑚 + 𝑢))
116	17	ad2antrr 725	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 𝑃 ∈ ℤ)
117	85	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑚 + 𝑢) ∈ ℤ)
118		1red 11215	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 1 ∈ ℝ)
119		nn0abscl 15259	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ ((𝑚 − 𝑢) ∈ ℤ → (abs‘(𝑚 − 𝑢)) ∈ ℕ₀)
120	86, 119	syl 17	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 𝑢)) ∈ ℕ₀)
121	120	nn0red 12533	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 𝑢)) ∈ ℝ)
122	121	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ∈ ℝ)
123	117	zred 12666	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑚 + 𝑢) ∈ ℝ)
124	120	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ∈ ℕ₀)
125	124	nn0zd 12584	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ∈ ℤ)
126	86	zcnd 12667	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 − 𝑢) ∈ ℂ)
127	126	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑚 − 𝑢) ∈ ℂ)
128	79, 80	subeq0ad 11581	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚 − 𝑢) = 0 ↔ 𝑚 = 𝑢))
129	128	necon3bid 2986	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚 − 𝑢) ≠ 0 ↔ 𝑚 ≠ 𝑢))
130	129	biimpar 479	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑚 − 𝑢) ≠ 0)
131	127, 130	absrpcld 15395	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ∈ ℝ⁺)
132	131	rpgt0d 13019	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 0 < (abs‘(𝑚 − 𝑢)))
133		elnnz 12568	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((abs‘(𝑚 − 𝑢)) ∈ ℕ ↔ ((abs‘(𝑚 − 𝑢)) ∈ ℤ ∧ 0 < (abs‘(𝑚 − 𝑢))))
134	125, 132, 133	sylanbrc 584	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ∈ ℕ)
135	134	nnge1d 12260	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 1 ≤ (abs‘(𝑚 − 𝑢)))
136		0cnd 11207	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ∈ ℂ)
137	79, 80, 136	abs3difd 15407	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 𝑢)) ≤ ((abs‘(𝑚 − 0)) + (abs‘(0 − 𝑢))))
138	79	subid1d 11560	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 − 0) = 𝑚)
139	138	fveq2d 6896	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 0)) = (abs‘𝑚))
140		elfzle1 13504	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ⊢ (𝑚 ∈ (0...𝑁) → 0 ≤ 𝑚)
141	140	ad2antrl 727	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ≤ 𝑚)
142	98, 141	absidd 15369	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘𝑚) = 𝑚)
143	139, 142	eqtrd 2773	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 0)) = 𝑚)
144		0cn 11206	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ 0 ∈ ℂ
145		abssub 15273	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((0 ∈ ℂ ∧ 𝑢 ∈ ℂ) → (abs‘(0 − 𝑢)) = (abs‘(𝑢 − 0)))
146	144, 80, 145	sylancr 588	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(0 − 𝑢)) = (abs‘(𝑢 − 0)))
147	80	subid1d 11560	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑢 − 0) = 𝑢)
148	147	fveq2d 6896	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑢 − 0)) = (abs‘𝑢))
149		elfzle1 13504	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ⊢ (𝑢 ∈ (0...𝑁) → 0 ≤ 𝑢)
150	149	ad2antll 728	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ≤ 𝑢)
151	99, 150	absidd 15369	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘𝑢) = 𝑢)
152	146, 148, 151	3eqtrd 2777	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(0 − 𝑢)) = 𝑢)
153	143, 152	oveq12d 7427	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((abs‘(𝑚 − 0)) + (abs‘(0 − 𝑢))) = (𝑚 + 𝑢))
154	137, 153	breqtrd 5175	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 𝑢)) ≤ (𝑚 + 𝑢))
155	154	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (abs‘(𝑚 − 𝑢)) ≤ (𝑚 + 𝑢))
156	118, 122, 123, 135, 155	letrd 11371	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 1 ≤ (𝑚 + 𝑢))
157		elnnz1 12588	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((𝑚 + 𝑢) ∈ ℕ ↔ ((𝑚 + 𝑢) ∈ ℤ ∧ 1 ≤ (𝑚 + 𝑢)))
158	117, 156, 157	sylanbrc 584	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑚 + 𝑢) ∈ ℕ)
159		dvdsle 16253	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ ((𝑃 ∈ ℤ ∧ (𝑚 + 𝑢) ∈ ℕ) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑃 ≤ (𝑚 + 𝑢)))
160	116, 158, 159	syl2anc 585	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑃 ≤ (𝑚 + 𝑢)))
161	115, 160	mtod 197	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → ¬ 𝑃 ∥ (𝑚 + 𝑢))
162	161	ex 414	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 ≠ 𝑢 → ¬ 𝑃 ∥ (𝑚 + 𝑢)))
163	162	necon4ad 2960	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑚 = 𝑢))
164		dvdsabsb 16219	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝑃 ∈ ℤ ∧ (𝑚 − 𝑢) ∈ ℤ) → (𝑃 ∥ (𝑚 − 𝑢) ↔ 𝑃 ∥ (abs‘(𝑚 − 𝑢))))
165	96, 86, 164	syl2anc 585	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚 − 𝑢) ↔ 𝑃 ∥ (abs‘(𝑚 − 𝑢))))
166		letr 11308	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((𝑃 ∈ ℝ ∧ (abs‘(𝑚 − 𝑢)) ∈ ℝ ∧ (𝑚 + 𝑢) ∈ ℝ) → ((𝑃 ≤ (abs‘(𝑚 − 𝑢)) ∧ (abs‘(𝑚 − 𝑢)) ≤ (𝑚 + 𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
167	97, 121, 90, 166	syl3anc 1372	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑃 ≤ (abs‘(𝑚 − 𝑢)) ∧ (abs‘(𝑚 − 𝑢)) ≤ (𝑚 + 𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
168	154, 167	mpan2d 693	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ≤ (abs‘(𝑚 − 𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
169	114, 168	mtod 197	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ¬ 𝑃 ≤ (abs‘(𝑚 − 𝑢)))
170	169	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → ¬ 𝑃 ≤ (abs‘(𝑚 − 𝑢)))
171	96	adantr 482	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → 𝑃 ∈ ℤ)
172		dvdsle 16253	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((𝑃 ∈ ℤ ∧ (abs‘(𝑚 − 𝑢)) ∈ ℕ) → (𝑃 ∥ (abs‘(𝑚 − 𝑢)) → 𝑃 ≤ (abs‘(𝑚 − 𝑢))))
173	171, 134, 172	syl2anc 585	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → (𝑃 ∥ (abs‘(𝑚 − 𝑢)) → 𝑃 ≤ (abs‘(𝑚 − 𝑢))))
174	170, 173	mtod 197	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚 ≠ 𝑢) → ¬ 𝑃 ∥ (abs‘(𝑚 − 𝑢)))
175	174	ex 414	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 ≠ 𝑢 → ¬ 𝑃 ∥ (abs‘(𝑚 − 𝑢))))
176	175	necon4ad 2960	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (abs‘(𝑚 − 𝑢)) → 𝑚 = 𝑢))
177	165, 176	sylbid 239	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚 − 𝑢) → 𝑚 = 𝑢))
178	163, 177	jaod 858	. . . . . . . . . . . . . . . . . . . 20 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚 − 𝑢)) → 𝑚 = 𝑢))
179	89, 178	sylbid 239	. . . . . . . . . . . . . . . . . . 19 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) → 𝑚 = 𝑢))
180		oveq1 7416	. . . . . . . . . . . . . . . . . . . 20 ⊢ (𝑚 = 𝑢 → (𝑚↑2) = (𝑢↑2))
181	180	oveq1d 7424	. . . . . . . . . . . . . . . . . . 19 ⊢ (𝑚 = 𝑢 → ((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃))
182	179, 181	impbid1 224	. . . . . . . . . . . . . . . . . 18 ⊢ ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑚 = 𝑢))
183	182	ex 414	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ((𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁)) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑚 = 𝑢)))
184	69, 183	dom2lem 8988	. . . . . . . . . . . . . . . 16 ⊢ (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1→(0...(𝑃 − 1)))
185		f1f1orn 6845	. . . . . . . . . . . . . . . 16 ⊢ ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1→(0...(𝑃 − 1)) → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
186	184, 185	syl 17	. . . . . . . . . . . . . . 15 ⊢ (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
187		eqid 2733	. . . . . . . . . . . . . . . . . 18 ⊢ (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) = (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))
188	187	rnmpt 5955	. . . . . . . . . . . . . . . . 17 ⊢ ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) = {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)}
189	2, 188	eqtr4i 2764	. . . . . . . . . . . . . . . 16 ⊢ 𝐴 = ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))
190		f1oeq3 6824	. . . . . . . . . . . . . . . 16 ⊢ (𝐴 = ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) → ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→𝐴 ↔ (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))))
191	189, 190	ax-mp 5	. . . . . . . . . . . . . . 15 ⊢ ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→𝐴 ↔ (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
192	186, 191	sylibr 233	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→𝐴)
193		ovex 7442	. . . . . . . . . . . . . . 15 ⊢ (0...𝑁) ∈ V
194	193	f1oen 8969	. . . . . . . . . . . . . 14 ⊢ ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→𝐴 → (0...𝑁) ≈ 𝐴)
195	192, 194	syl 17	. . . . . . . . . . . . 13 ⊢ (𝜑 → (0...𝑁) ≈ 𝐴)
196	195	ensymd 9001	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ≈ (0...𝑁))
197		ax-1cn 11168	. . . . . . . . . . . . . . 15 ⊢ 1 ∈ ℂ
198		pncan 11466	. . . . . . . . . . . . . . 15 ⊢ ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 + 1) − 1) = 𝑁)
199	57, 197, 198	sylancl 587	. . . . . . . . . . . . . 14 ⊢ (𝜑 → ((𝑁 + 1) − 1) = 𝑁)
200	199	oveq2d 7425	. . . . . . . . . . . . 13 ⊢ (𝜑 → (0...((𝑁 + 1) − 1)) = (0...𝑁))
201	56	nnnn0d 12532	. . . . . . . . . . . . . . . 16 ⊢ (𝜑 → 𝑁 ∈ ℕ₀)
202		peano2nn0 12512	. . . . . . . . . . . . . . . 16 ⊢ (𝑁 ∈ ℕ₀ → (𝑁 + 1) ∈ ℕ₀)
203	201, 202	syl 17	. . . . . . . . . . . . . . 15 ⊢ (𝜑 → (𝑁 + 1) ∈ ℕ₀)
204	203	nn0zd 12584	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (𝑁 + 1) ∈ ℤ)
205		fz01en 13529	. . . . . . . . . . . . . 14 ⊢ ((𝑁 + 1) ∈ ℤ → (0...((𝑁 + 1) − 1)) ≈ (1...(𝑁 + 1)))
206	204, 205	syl 17	. . . . . . . . . . . . 13 ⊢ (𝜑 → (0...((𝑁 + 1) − 1)) ≈ (1...(𝑁 + 1)))
207	200, 206	eqbrtrrd 5173	. . . . . . . . . . . 12 ⊢ (𝜑 → (0...𝑁) ≈ (1...(𝑁 + 1)))
208		entr 9002	. . . . . . . . . . . 12 ⊢ ((𝐴 ≈ (0...𝑁) ∧ (0...𝑁) ≈ (1...(𝑁 + 1))) → 𝐴 ≈ (1...(𝑁 + 1)))
209	196, 207, 208	syl2anc 585	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐴 ≈ (1...(𝑁 + 1)))
210	1, 15	ssfid 9267	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐴 ∈ Fin)
211		fzfid 13938	. . . . . . . . . . . 12 ⊢ (𝜑 → (1...(𝑁 + 1)) ∈ Fin)
212		hashen 14307	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ (1...(𝑁 + 1)) ∈ Fin) → ((♯‘𝐴) = (♯‘(1...(𝑁 + 1))) ↔ 𝐴 ≈ (1...(𝑁 + 1))))
213	210, 211, 212	syl2anc 585	. . . . . . . . . . 11 ⊢ (𝜑 → ((♯‘𝐴) = (♯‘(1...(𝑁 + 1))) ↔ 𝐴 ≈ (1...(𝑁 + 1))))
214	209, 213	mpbird 257	. . . . . . . . . 10 ⊢ (𝜑 → (♯‘𝐴) = (♯‘(1...(𝑁 + 1))))
215		hashfz1 14306	. . . . . . . . . . 11 ⊢ ((𝑁 + 1) ∈ ℕ₀ → (♯‘(1...(𝑁 + 1))) = (𝑁 + 1))
216	203, 215	syl 17	. . . . . . . . . 10 ⊢ (𝜑 → (♯‘(1...(𝑁 + 1))) = (𝑁 + 1))
217	214, 216	eqtrd 2773	. . . . . . . . 9 ⊢ (𝜑 → (♯‘𝐴) = (𝑁 + 1))
218	27	ex 414	. . . . . . . . . . . . . 14 ⊢ (𝜑 → (𝑣 ∈ 𝐴 → ((𝑃 − 1) − 𝑣) ∈ (0...(𝑃 − 1))))
219	20	adantr 482	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ (𝑣 ∈ 𝐴 ∧ 𝑘 ∈ 𝐴)) → (𝑃 − 1) ∈ ℂ)
220		fzssuz 13542	. . . . . . . . . . . . . . . . . . . 20 ⊢ (0...(𝑃 − 1)) ⊆ (ℤ_≥‘0)
221		uzssz 12843	. . . . . . . . . . . . . . . . . . . . 21 ⊢ (ℤ_≥‘0) ⊆ ℤ
222		zsscn 12566	. . . . . . . . . . . . . . . . . . . . 21 ⊢ ℤ ⊆ ℂ
223	221, 222	sstri 3992	. . . . . . . . . . . . . . . . . . . 20 ⊢ (ℤ_≥‘0) ⊆ ℂ
224	220, 223	sstri 3992	. . . . . . . . . . . . . . . . . . 19 ⊢ (0...(𝑃 − 1)) ⊆ ℂ
225	15, 224	sstrdi 3995	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → 𝐴 ⊆ ℂ)
226	225	sselda 3983	. . . . . . . . . . . . . . . . 17 ⊢ ((𝜑 ∧ 𝑣 ∈ 𝐴) → 𝑣 ∈ ℂ)
227	226	adantrr 716	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ (𝑣 ∈ 𝐴 ∧ 𝑘 ∈ 𝐴)) → 𝑣 ∈ ℂ)
228	225	sselda 3983	. . . . . . . . . . . . . . . . 17 ⊢ ((𝜑 ∧ 𝑘 ∈ 𝐴) → 𝑘 ∈ ℂ)
229	228	adantrl 715	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ (𝑣 ∈ 𝐴 ∧ 𝑘 ∈ 𝐴)) → 𝑘 ∈ ℂ)
230	219, 227, 229	subcanad 11614	. . . . . . . . . . . . . . 15 ⊢ ((𝜑 ∧ (𝑣 ∈ 𝐴 ∧ 𝑘 ∈ 𝐴)) → (((𝑃 − 1) − 𝑣) = ((𝑃 − 1) − 𝑘) ↔ 𝑣 = 𝑘))
231	230	ex 414	. . . . . . . . . . . . . 14 ⊢ (𝜑 → ((𝑣 ∈ 𝐴 ∧ 𝑘 ∈ 𝐴) → (((𝑃 − 1) − 𝑣) = ((𝑃 − 1) − 𝑘) ↔ 𝑣 = 𝑘)))
232	218, 231	dom2lem 8988	. . . . . . . . . . . . 13 ⊢ (𝜑 → (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴–1-1→(0...(𝑃 − 1)))
233		f1eq1 6783	. . . . . . . . . . . . . 14 ⊢ (𝐹 = (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣)) → (𝐹:𝐴–1-1→(0...(𝑃 − 1)) ↔ (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴–1-1→(0...(𝑃 − 1))))
234	28, 233	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (𝐹:𝐴–1-1→(0...(𝑃 − 1)) ↔ (𝑣 ∈ 𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴–1-1→(0...(𝑃 − 1)))
235	232, 234	sylibr 233	. . . . . . . . . . . 12 ⊢ (𝜑 → 𝐹:𝐴–1-1→(0...(𝑃 − 1)))
236		f1f1orn 6845	. . . . . . . . . . . 12 ⊢ (𝐹:𝐴–1-1→(0...(𝑃 − 1)) → 𝐹:𝐴–1-1-onto→ran 𝐹)
237	235, 236	syl 17	. . . . . . . . . . 11 ⊢ (𝜑 → 𝐹:𝐴–1-1-onto→ran 𝐹)
238	210, 237	hasheqf1od 14313	. . . . . . . . . 10 ⊢ (𝜑 → (♯‘𝐴) = (♯‘ran 𝐹))
239	238, 217	eqtr3d 2775	. . . . . . . . 9 ⊢ (𝜑 → (♯‘ran 𝐹) = (𝑁 + 1))
240	217, 239	oveq12d 7427	. . . . . . . 8 ⊢ (𝜑 → ((♯‘𝐴) + (♯‘ran 𝐹)) = ((𝑁 + 1) + (𝑁 + 1)))
241	59, 68, 240	3eqtr4d 2783	. . . . . . 7 ⊢ (𝜑 → (𝑃 + 1) = ((♯‘𝐴) + (♯‘ran 𝐹)))
242	241	adantr 482	. . . . . 6 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝑃 + 1) = ((♯‘𝐴) + (♯‘ran 𝐹)))
243	210	adantr 482	. . . . . . 7 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝐴 ∈ Fin)
244	1, 30	ssfid 9267	. . . . . . . 8 ⊢ (𝜑 → ran 𝐹 ∈ Fin)
245	244	adantr 482	. . . . . . 7 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → ran 𝐹 ∈ Fin)
246		simpr 486	. . . . . . 7 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝐴 ∩ ran 𝐹) = ∅)
247		hashun 14342	. . . . . . 7 ⊢ ((𝐴 ∈ Fin ∧ ran 𝐹 ∈ Fin ∧ (𝐴 ∩ ran 𝐹) = ∅) → (♯‘(𝐴 ∪ ran 𝐹)) = ((♯‘𝐴) + (♯‘ran 𝐹)))
248	243, 245, 246, 247	syl3anc 1372	. . . . . 6 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (♯‘(𝐴 ∪ ran 𝐹)) = ((♯‘𝐴) + (♯‘ran 𝐹)))
249	242, 248	eqtr4d 2776	. . . . 5 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝑃 + 1) = (♯‘(𝐴 ∪ ran 𝐹)))
250	55, 249	breqtrd 5175	. . . 4 ⊢ ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 < (♯‘(𝐴 ∪ ran 𝐹)))
251	250	ex 414	. . 3 ⊢ (𝜑 → ((𝐴 ∩ ran 𝐹) = ∅ → 𝑃 < (♯‘(𝐴 ∪ ran 𝐹))))
252	251	necon3bd 2955	. 2 ⊢ (𝜑 → (¬ 𝑃 < (♯‘(𝐴 ∪ ran 𝐹)) → (𝐴 ∩ ran 𝐹) ≠ ∅))
253	53, 252	mpd 15	1 ⊢ (𝜑 → (𝐴 ∩ ran 𝐹) ≠ ∅)

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ↔ wb 205 ∧ wa 397 ∨ wo 846 = wceq 1542 ∈ wcel 2107 {cab 2710 ≠ wne 2941 ∃wrex 3071 ∪ cun 3947 ∩ cin 3948 ⊆ wss 3949 ∅c0 4323 class class class wbr 5149 ↦ cmpt 5232 ran crn 5678 –1-1→wf1 6541 –1-1-onto→wf1o 6543 ‘cfv 6544 (class class class)co 7409 ≈ cen 8936 ≼ cdom 8937 Fincfn 8939 ℂcc 11108 ℝcr 11109 0cc0 11110 1c1 11111 + caddc 11113 · cmul 11115 < clt 11248 ≤ cle 11249 − cmin 11444 ℕcn 12212 2c2 12267 ℕ₀cn0 12472 ℤcz 12558 ℤ_≥cuz 12822 ...cfz 13484 mod cmo 13834 ↑cexp 14027 ♯chash 14290 abscabs 15181 ∥ cdvds 16197 ℙcprime 16608

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1798 ax-4 1812 ax-5 1914 ax-6 1972 ax-7 2012 ax-8 2109 ax-9 2117 ax-10 2138 ax-11 2155 ax-12 2172 ax-ext 2704 ax-rep 5286 ax-sep 5300 ax-nul 5307 ax-pow 5364 ax-pr 5428 ax-un 7725 ax-cnex 11166 ax-resscn 11167 ax-1cn 11168 ax-icn 11169 ax-addcl 11170 ax-addrcl 11171 ax-mulcl 11172 ax-mulrcl 11173 ax-mulcom 11174 ax-addass 11175 ax-mulass 11176 ax-distr 11177 ax-i2m1 11178 ax-1ne0 11179 ax-1rid 11180 ax-rnegex 11181 ax-rrecex 11182 ax-cnre 11183 ax-pre-lttri 11184 ax-pre-lttrn 11185 ax-pre-ltadd 11186 ax-pre-mulgt0 11187 ax-pre-sup 11188

This theorem depends on definitions: df-bi 206 df-an 398 df-or 847 df-3or 1089 df-3an 1090 df-tru 1545 df-fal 1555 df-ex 1783 df-nf 1787 df-sb 2069 df-mo 2535 df-eu 2564 df-clab 2711 df-cleq 2725 df-clel 2811 df-nfc 2886 df-ne 2942 df-nel 3048 df-ral 3063 df-rex 3072 df-rmo 3377 df-reu 3378 df-rab 3434 df-v 3477 df-sbc 3779 df-csb 3895 df-dif 3952 df-un 3954 df-in 3956 df-ss 3966 df-pss 3968 df-nul 4324 df-if 4530 df-pw 4605 df-sn 4630 df-pr 4632 df-op 4636 df-uni 4910 df-int 4952 df-iun 5000 df-br 5150 df-opab 5212 df-mpt 5233 df-tr 5267 df-id 5575 df-eprel 5581 df-po 5589 df-so 5590 df-fr 5632 df-we 5634 df-xp 5683 df-rel 5684 df-cnv 5685 df-co 5686 df-dm 5687 df-rn 5688 df-res 5689 df-ima 5690 df-pred 6301 df-ord 6368 df-on 6369 df-lim 6370 df-suc 6371 df-iota 6496 df-fun 6546 df-fn 6547 df-f 6548 df-f1 6549 df-fo 6550 df-f1o 6551 df-fv 6552 df-riota 7365 df-ov 7412 df-oprab 7413 df-mpo 7414 df-om 7856 df-1st 7975 df-2nd 7976 df-frecs 8266 df-wrecs 8297 df-recs 8371 df-rdg 8410 df-1o 8466 df-2o 8467 df-oadd 8470 df-er 8703 df-en 8940 df-dom 8941 df-sdom 8942 df-fin 8943 df-sup 9437 df-inf 9438 df-dju 9896 df-card 9934 df-pnf 11250 df-mnf 11251 df-xr 11252 df-ltxr 11253 df-le 11254 df-sub 11446 df-neg 11447 df-div 11872 df-nn 12213 df-2 12275 df-3 12276 df-n0 12473 df-xnn0 12545 df-z 12559 df-uz 12823 df-rp 12975 df-fz 13485 df-fl 13757 df-mod 13835 df-seq 13967 df-exp 14028 df-hash 14291 df-cj 15046 df-re 15047 df-im 15048 df-sqrt 15182 df-abs 15183 df-dvds 16198 df-gcd 16436 df-prm 16609

This theorem is referenced by: 4sqlem12 16889

W3C validator