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

Theorem 4sqlem11 15594
Description: Lemma for 4sq 15603. 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.
StepHypRef Expression
1 fzfid 12720 . . . . . 6 (𝜑 → (0...(𝑃 − 1)) ∈ Fin)
2 4sqlem11.5 . . . . . . . 8 𝐴 = {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)}
3 elfzelz 12292 . . . . . . . . . . . . 13 (𝑚 ∈ (0...𝑁) → 𝑚 ∈ ℤ)
4 zsqcl 12882 . . . . . . . . . . . . 13 (𝑚 ∈ ℤ → (𝑚↑2) ∈ ℤ)
53, 4syl 17 . . . . . . . . . . . 12 (𝑚 ∈ (0...𝑁) → (𝑚↑2) ∈ ℤ)
6 4sq.4 . . . . . . . . . . . . 13 (𝜑𝑃 ∈ ℙ)
7 prmnn 15323 . . . . . . . . . . . . 13 (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
86, 7syl 17 . . . . . . . . . . . 12 (𝜑𝑃 ∈ ℕ)
9 zmodfz 12640 . . . . . . . . . . . 12 (((𝑚↑2) ∈ ℤ ∧ 𝑃 ∈ ℕ) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)))
105, 8, 9syl2anr 495 . . . . . . . . . . 11 ((𝜑𝑚 ∈ (0...𝑁)) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)))
11 eleq1a 2693 . . . . . . . . . . 11 (((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1)) → (𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
1210, 11syl 17 . . . . . . . . . 10 ((𝜑𝑚 ∈ (0...𝑁)) → (𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
1312rexlimdva 3025 . . . . . . . . 9 (𝜑 → (∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃) → 𝑢 ∈ (0...(𝑃 − 1))))
1413abssdv 3660 . . . . . . . 8 (𝜑 → {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)} ⊆ (0...(𝑃 − 1)))
152, 14syl5eqss 3633 . . . . . . 7 (𝜑𝐴 ⊆ (0...(𝑃 − 1)))
16 prmz 15324 . . . . . . . . . . . . . . . 16 (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
176, 16syl 17 . . . . . . . . . . . . . . 15 (𝜑𝑃 ∈ ℤ)
18 peano2zm 11372 . . . . . . . . . . . . . . 15 (𝑃 ∈ ℤ → (𝑃 − 1) ∈ ℤ)
1917, 18syl 17 . . . . . . . . . . . . . 14 (𝜑 → (𝑃 − 1) ∈ ℤ)
2019zcnd 11435 . . . . . . . . . . . . 13 (𝜑 → (𝑃 − 1) ∈ ℂ)
2120addid2d 10189 . . . . . . . . . . . 12 (𝜑 → (0 + (𝑃 − 1)) = (𝑃 − 1))
2221oveq1d 6625 . . . . . . . . . . 11 (𝜑 → ((0 + (𝑃 − 1)) − 𝑣) = ((𝑃 − 1) − 𝑣))
2322adantr 481 . . . . . . . . . 10 ((𝜑𝑣𝐴) → ((0 + (𝑃 − 1)) − 𝑣) = ((𝑃 − 1) − 𝑣))
2415sselda 3587 . . . . . . . . . . 11 ((𝜑𝑣𝐴) → 𝑣 ∈ (0...(𝑃 − 1)))
25 fzrev3i 12357 . . . . . . . . . . 11 (𝑣 ∈ (0...(𝑃 − 1)) → ((0 + (𝑃 − 1)) − 𝑣) ∈ (0...(𝑃 − 1)))
2624, 25syl 17 . . . . . . . . . 10 ((𝜑𝑣𝐴) → ((0 + (𝑃 − 1)) − 𝑣) ∈ (0...(𝑃 − 1)))
2723, 26eqeltrrd 2699 . . . . . . . . 9 ((𝜑𝑣𝐴) → ((𝑃 − 1) − 𝑣) ∈ (0...(𝑃 − 1)))
28 4sqlem11.6 . . . . . . . . 9 𝐹 = (𝑣𝐴 ↦ ((𝑃 − 1) − 𝑣))
2927, 28fmptd 6346 . . . . . . . 8 (𝜑𝐹:𝐴⟶(0...(𝑃 − 1)))
30 frn 6015 . . . . . . . 8 (𝐹:𝐴⟶(0...(𝑃 − 1)) → ran 𝐹 ⊆ (0...(𝑃 − 1)))
3129, 30syl 17 . . . . . . 7 (𝜑 → ran 𝐹 ⊆ (0...(𝑃 − 1)))
3215, 31unssd 3772 . . . . . 6 (𝜑 → (𝐴 ∪ ran 𝐹) ⊆ (0...(𝑃 − 1)))
33 ssdomg 7953 . . . . . 6 ((0...(𝑃 − 1)) ∈ Fin → ((𝐴 ∪ ran 𝐹) ⊆ (0...(𝑃 − 1)) → (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
341, 32, 33sylc 65 . . . . 5 (𝜑 → (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1)))
35 ssfi 8132 . . . . . . 7 (((0...(𝑃 − 1)) ∈ Fin ∧ (𝐴 ∪ ran 𝐹) ⊆ (0...(𝑃 − 1))) → (𝐴 ∪ ran 𝐹) ∈ Fin)
361, 32, 35syl2anc 692 . . . . . 6 (𝜑 → (𝐴 ∪ ran 𝐹) ∈ Fin)
37 hashdom 13116 . . . . . 6 (((𝐴 ∪ ran 𝐹) ∈ Fin ∧ (0...(𝑃 − 1)) ∈ Fin) → ((#‘(𝐴 ∪ ran 𝐹)) ≤ (#‘(0...(𝑃 − 1))) ↔ (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
3836, 1, 37syl2anc 692 . . . . 5 (𝜑 → ((#‘(𝐴 ∪ ran 𝐹)) ≤ (#‘(0...(𝑃 − 1))) ↔ (𝐴 ∪ ran 𝐹) ≼ (0...(𝑃 − 1))))
3934, 38mpbird 247 . . . 4 (𝜑 → (#‘(𝐴 ∪ ran 𝐹)) ≤ (#‘(0...(𝑃 − 1))))
40 fz01en 12319 . . . . . . 7 (𝑃 ∈ ℤ → (0...(𝑃 − 1)) ≈ (1...𝑃))
4117, 40syl 17 . . . . . 6 (𝜑 → (0...(𝑃 − 1)) ≈ (1...𝑃))
42 fzfid 12720 . . . . . . 7 (𝜑 → (1...𝑃) ∈ Fin)
43 hashen 13083 . . . . . . 7 (((0...(𝑃 − 1)) ∈ Fin ∧ (1...𝑃) ∈ Fin) → ((#‘(0...(𝑃 − 1))) = (#‘(1...𝑃)) ↔ (0...(𝑃 − 1)) ≈ (1...𝑃)))
441, 42, 43syl2anc 692 . . . . . 6 (𝜑 → ((#‘(0...(𝑃 − 1))) = (#‘(1...𝑃)) ↔ (0...(𝑃 − 1)) ≈ (1...𝑃)))
4541, 44mpbird 247 . . . . 5 (𝜑 → (#‘(0...(𝑃 − 1))) = (#‘(1...𝑃)))
468nnnn0d 11303 . . . . . 6 (𝜑𝑃 ∈ ℕ0)
47 hashfz1 13082 . . . . . 6 (𝑃 ∈ ℕ0 → (#‘(1...𝑃)) = 𝑃)
4846, 47syl 17 . . . . 5 (𝜑 → (#‘(1...𝑃)) = 𝑃)
4945, 48eqtrd 2655 . . . 4 (𝜑 → (#‘(0...(𝑃 − 1))) = 𝑃)
5039, 49breqtrd 4644 . . 3 (𝜑 → (#‘(𝐴 ∪ ran 𝐹)) ≤ 𝑃)
51 hashcl 13095 . . . . . 6 ((𝐴 ∪ ran 𝐹) ∈ Fin → (#‘(𝐴 ∪ ran 𝐹)) ∈ ℕ0)
5236, 51syl 17 . . . . 5 (𝜑 → (#‘(𝐴 ∪ ran 𝐹)) ∈ ℕ0)
5352nn0red 11304 . . . 4 (𝜑 → (#‘(𝐴 ∪ ran 𝐹)) ∈ ℝ)
5417zred 11434 . . . 4 (𝜑𝑃 ∈ ℝ)
5553, 54lenltd 10135 . . 3 (𝜑 → ((#‘(𝐴 ∪ ran 𝐹)) ≤ 𝑃 ↔ ¬ 𝑃 < (#‘(𝐴 ∪ ran 𝐹))))
5650, 55mpbid 222 . 2 (𝜑 → ¬ 𝑃 < (#‘(𝐴 ∪ ran 𝐹)))
5754adantr 481 . . . . . 6 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 ∈ ℝ)
5857ltp1d 10906 . . . . 5 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 < (𝑃 + 1))
59 4sq.2 . . . . . . . . . 10 (𝜑𝑁 ∈ ℕ)
6059nncnd 10988 . . . . . . . . 9 (𝜑𝑁 ∈ ℂ)
61 1cnd 10008 . . . . . . . . 9 (𝜑 → 1 ∈ ℂ)
6260, 60, 61, 61add4d 10216 . . . . . . . 8 (𝜑 → ((𝑁 + 𝑁) + (1 + 1)) = ((𝑁 + 1) + (𝑁 + 1)))
63 4sq.3 . . . . . . . . . 10 (𝜑𝑃 = ((2 · 𝑁) + 1))
6463oveq1d 6625 . . . . . . . . 9 (𝜑 → (𝑃 + 1) = (((2 · 𝑁) + 1) + 1))
65 2cn 11043 . . . . . . . . . . 11 2 ∈ ℂ
66 mulcl 9972 . . . . . . . . . . 11 ((2 ∈ ℂ ∧ 𝑁 ∈ ℂ) → (2 · 𝑁) ∈ ℂ)
6765, 60, 66sylancr 694 . . . . . . . . . 10 (𝜑 → (2 · 𝑁) ∈ ℂ)
6867, 61, 61addassd 10014 . . . . . . . . 9 (𝜑 → (((2 · 𝑁) + 1) + 1) = ((2 · 𝑁) + (1 + 1)))
69602timesd 11227 . . . . . . . . . 10 (𝜑 → (2 · 𝑁) = (𝑁 + 𝑁))
7069oveq1d 6625 . . . . . . . . 9 (𝜑 → ((2 · 𝑁) + (1 + 1)) = ((𝑁 + 𝑁) + (1 + 1)))
7164, 68, 703eqtrd 2659 . . . . . . . 8 (𝜑 → (𝑃 + 1) = ((𝑁 + 𝑁) + (1 + 1)))
7210ex 450 . . . . . . . . . . . . . . . . 17 (𝜑 → (𝑚 ∈ (0...𝑁) → ((𝑚↑2) mod 𝑃) ∈ (0...(𝑃 − 1))))
738adantr 481 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℕ)
743ad2antrl 763 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℤ)
7574, 4syl 17 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚↑2) ∈ ℤ)
76 elfzelz 12292 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑢 ∈ (0...𝑁) → 𝑢 ∈ ℤ)
7776ad2antll 764 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℤ)
78 zsqcl 12882 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑢 ∈ ℤ → (𝑢↑2) ∈ ℤ)
7977, 78syl 17 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑢↑2) ∈ ℤ)
80 moddvds 14926 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑃 ∈ ℕ ∧ (𝑚↑2) ∈ ℤ ∧ (𝑢↑2) ∈ ℤ) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑃 ∥ ((𝑚↑2) − (𝑢↑2))))
8173, 75, 79, 80syl3anc 1323 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑃 ∥ ((𝑚↑2) − (𝑢↑2))))
8274zcnd 11435 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℂ)
8377zcnd 11435 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℂ)
84 subsq 12920 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝑚 ∈ ℂ ∧ 𝑢 ∈ ℂ) → ((𝑚↑2) − (𝑢↑2)) = ((𝑚 + 𝑢) · (𝑚𝑢)))
8582, 83, 84syl2anc 692 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚↑2) − (𝑢↑2)) = ((𝑚 + 𝑢) · (𝑚𝑢)))
8685breq2d 4630 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ ((𝑚↑2) − (𝑢↑2)) ↔ 𝑃 ∥ ((𝑚 + 𝑢) · (𝑚𝑢))))
876adantr 481 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℙ)
8874, 77zaddcld 11438 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ∈ ℤ)
8974, 77zsubcld 11439 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚𝑢) ∈ ℤ)
90 euclemma 15360 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑃 ∈ ℙ ∧ (𝑚 + 𝑢) ∈ ℤ ∧ (𝑚𝑢) ∈ ℤ) → (𝑃 ∥ ((𝑚 + 𝑢) · (𝑚𝑢)) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚𝑢))))
9187, 88, 89, 90syl3anc 1323 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ ((𝑚 + 𝑢) · (𝑚𝑢)) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚𝑢))))
9281, 86, 913bitrd 294 . . . . . . . . . . . . . . . . . . . 20 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ (𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚𝑢))))
9388zred 11434 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ∈ ℝ)
94 2re 11042 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2 ∈ ℝ
9559nnred 10987 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (𝜑𝑁 ∈ ℝ)
96 remulcl 9973 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((2 ∈ ℝ ∧ 𝑁 ∈ ℝ) → (2 · 𝑁) ∈ ℝ)
9794, 95, 96sylancr 694 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (𝜑 → (2 · 𝑁) ∈ ℝ)
9897adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) ∈ ℝ)
9987, 16syl 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℤ)
10099zred 11434 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑃 ∈ ℝ)
10174zred 11434 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚 ∈ ℝ)
10277zred 11434 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢 ∈ ℝ)
10395adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑁 ∈ ℝ)
104 elfzle2 12295 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 (𝑚 ∈ (0...𝑁) → 𝑚𝑁)
105104ad2antrl 763 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑚𝑁)
106 elfzle2 12295 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 (𝑢 ∈ (0...𝑁) → 𝑢𝑁)
107106ad2antll 764 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑢𝑁)
108101, 102, 103, 103, 105, 107le2addd 10598 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ≤ (𝑁 + 𝑁))
10960adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 𝑁 ∈ ℂ)
1101092timesd 11227 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) = (𝑁 + 𝑁))
111108, 110breqtrrd 4646 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) ≤ (2 · 𝑁))
11297ltp1d 10906 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (𝜑 → (2 · 𝑁) < ((2 · 𝑁) + 1))
113112, 63breqtrrd 4646 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (𝜑 → (2 · 𝑁) < 𝑃)
114113adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (2 · 𝑁) < 𝑃)
11593, 98, 100, 111, 114lelttrd 10147 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 + 𝑢) < 𝑃)
11693, 100ltnled 10136 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚 + 𝑢) < 𝑃 ↔ ¬ 𝑃 ≤ (𝑚 + 𝑢)))
117115, 116mpbid 222 . . . . . . . . . . . . . . . . . . . . . . . . 25 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ¬ 𝑃 ≤ (𝑚 + 𝑢))
118117adantr 481 . . . . . . . . . . . . . . . . . . . . . . . 24 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → ¬ 𝑃 ≤ (𝑚 + 𝑢))
11917ad2antrr 761 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 𝑃 ∈ ℤ)
12088adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . 26 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑚 + 𝑢) ∈ ℤ)
121 1red 10007 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 1 ∈ ℝ)
122 nn0abscl 13994 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ((𝑚𝑢) ∈ ℤ → (abs‘(𝑚𝑢)) ∈ ℕ0)
12389, 122syl 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚𝑢)) ∈ ℕ0)
124123nn0red 11304 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚𝑢)) ∈ ℝ)
125124adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ∈ ℝ)
126120zred 11434 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑚 + 𝑢) ∈ ℝ)
127123adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ∈ ℕ0)
128127nn0zd 11432 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ∈ ℤ)
12989zcnd 11435 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚𝑢) ∈ ℂ)
130129adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑚𝑢) ∈ ℂ)
13182, 83subeq0ad 10354 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚𝑢) = 0 ↔ 𝑚 = 𝑢))
132131necon3bid 2834 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑚𝑢) ≠ 0 ↔ 𝑚𝑢))
133132biimpar 502 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑚𝑢) ≠ 0)
134130, 133absrpcld 14129 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ∈ ℝ+)
135134rpgt0d 11827 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 0 < (abs‘(𝑚𝑢)))
136 elnnz 11339 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((abs‘(𝑚𝑢)) ∈ ℕ ↔ ((abs‘(𝑚𝑢)) ∈ ℤ ∧ 0 < (abs‘(𝑚𝑢))))
137128, 135, 136sylanbrc 697 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ∈ ℕ)
138137nnge1d 11015 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 1 ≤ (abs‘(𝑚𝑢)))
139 0cnd 9985 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ∈ ℂ)
14082, 83, 139abs3difd 14141 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚𝑢)) ≤ ((abs‘(𝑚 − 0)) + (abs‘(0 − 𝑢))))
14182subid1d 10333 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚 − 0) = 𝑚)
142141fveq2d 6157 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 0)) = (abs‘𝑚))
143 elfzle1 12294 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 (𝑚 ∈ (0...𝑁) → 0 ≤ 𝑚)
144143ad2antrl 763 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ≤ 𝑚)
145101, 144absidd 14103 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘𝑚) = 𝑚)
146142, 145eqtrd 2655 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚 − 0)) = 𝑚)
147 0cn 9984 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 0 ∈ ℂ
148 abssub 14008 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((0 ∈ ℂ ∧ 𝑢 ∈ ℂ) → (abs‘(0 − 𝑢)) = (abs‘(𝑢 − 0)))
149147, 83, 148sylancr 694 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(0 − 𝑢)) = (abs‘(𝑢 − 0)))
15083subid1d 10333 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑢 − 0) = 𝑢)
151150fveq2d 6157 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑢 − 0)) = (abs‘𝑢))
152 elfzle1 12294 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 (𝑢 ∈ (0...𝑁) → 0 ≤ 𝑢)
153152ad2antll 764 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → 0 ≤ 𝑢)
154102, 153absidd 14103 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘𝑢) = 𝑢)
155149, 151, 1543eqtrd 2659 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(0 − 𝑢)) = 𝑢)
156146, 155oveq12d 6628 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((abs‘(𝑚 − 0)) + (abs‘(0 − 𝑢))) = (𝑚 + 𝑢))
157140, 156breqtrd 4644 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (abs‘(𝑚𝑢)) ≤ (𝑚 + 𝑢))
158157adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (abs‘(𝑚𝑢)) ≤ (𝑚 + 𝑢))
159121, 125, 126, 138, 158letrd 10146 . . . . . . . . . . . . . . . . . . . . . . . . . 26 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 1 ≤ (𝑚 + 𝑢))
160 elnnz1 11355 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑚 + 𝑢) ∈ ℕ ↔ ((𝑚 + 𝑢) ∈ ℤ ∧ 1 ≤ (𝑚 + 𝑢)))
161120, 159, 160sylanbrc 697 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑚 + 𝑢) ∈ ℕ)
162 dvdsle 14967 . . . . . . . . . . . . . . . . . . . . . . . . 25 ((𝑃 ∈ ℤ ∧ (𝑚 + 𝑢) ∈ ℕ) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑃 ≤ (𝑚 + 𝑢)))
163119, 161, 162syl2anc 692 . . . . . . . . . . . . . . . . . . . . . . . 24 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑃 ≤ (𝑚 + 𝑢)))
164118, 163mtod 189 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → ¬ 𝑃 ∥ (𝑚 + 𝑢))
165164ex 450 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚𝑢 → ¬ 𝑃 ∥ (𝑚 + 𝑢)))
166165necon4ad 2809 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚 + 𝑢) → 𝑚 = 𝑢))
167 dvdsabsb 14936 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝑃 ∈ ℤ ∧ (𝑚𝑢) ∈ ℤ) → (𝑃 ∥ (𝑚𝑢) ↔ 𝑃 ∥ (abs‘(𝑚𝑢))))
16899, 89, 167syl2anc 692 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚𝑢) ↔ 𝑃 ∥ (abs‘(𝑚𝑢))))
169 letr 10083 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((𝑃 ∈ ℝ ∧ (abs‘(𝑚𝑢)) ∈ ℝ ∧ (𝑚 + 𝑢) ∈ ℝ) → ((𝑃 ≤ (abs‘(𝑚𝑢)) ∧ (abs‘(𝑚𝑢)) ≤ (𝑚 + 𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
170100, 124, 93, 169syl3anc 1323 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑃 ≤ (abs‘(𝑚𝑢)) ∧ (abs‘(𝑚𝑢)) ≤ (𝑚 + 𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
171157, 170mpan2d 709 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ≤ (abs‘(𝑚𝑢)) → 𝑃 ≤ (𝑚 + 𝑢)))
172117, 171mtod 189 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ¬ 𝑃 ≤ (abs‘(𝑚𝑢)))
173172adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → ¬ 𝑃 ≤ (abs‘(𝑚𝑢)))
17499adantr 481 . . . . . . . . . . . . . . . . . . . . . . . . . 26 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → 𝑃 ∈ ℤ)
175 dvdsle 14967 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑃 ∈ ℤ ∧ (abs‘(𝑚𝑢)) ∈ ℕ) → (𝑃 ∥ (abs‘(𝑚𝑢)) → 𝑃 ≤ (abs‘(𝑚𝑢))))
176174, 137, 175syl2anc 692 . . . . . . . . . . . . . . . . . . . . . . . . 25 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → (𝑃 ∥ (abs‘(𝑚𝑢)) → 𝑃 ≤ (abs‘(𝑚𝑢))))
177173, 176mtod 189 . . . . . . . . . . . . . . . . . . . . . . . 24 (((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) ∧ 𝑚𝑢) → ¬ 𝑃 ∥ (abs‘(𝑚𝑢)))
178177ex 450 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑚𝑢 → ¬ 𝑃 ∥ (abs‘(𝑚𝑢))))
179178necon4ad 2809 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (abs‘(𝑚𝑢)) → 𝑚 = 𝑢))
180168, 179sylbid 230 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (𝑃 ∥ (𝑚𝑢) → 𝑚 = 𝑢))
181166, 180jaod 395 . . . . . . . . . . . . . . . . . . . 20 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → ((𝑃 ∥ (𝑚 + 𝑢) ∨ 𝑃 ∥ (𝑚𝑢)) → 𝑚 = 𝑢))
18292, 181sylbid 230 . . . . . . . . . . . . . . . . . . 19 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) → 𝑚 = 𝑢))
183 oveq1 6617 . . . . . . . . . . . . . . . . . . . 20 (𝑚 = 𝑢 → (𝑚↑2) = (𝑢↑2))
184183oveq1d 6625 . . . . . . . . . . . . . . . . . . 19 (𝑚 = 𝑢 → ((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃))
185182, 184impbid1 215 . . . . . . . . . . . . . . . . . 18 ((𝜑 ∧ (𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁))) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑚 = 𝑢))
186185ex 450 . . . . . . . . . . . . . . . . 17 (𝜑 → ((𝑚 ∈ (0...𝑁) ∧ 𝑢 ∈ (0...𝑁)) → (((𝑚↑2) mod 𝑃) = ((𝑢↑2) mod 𝑃) ↔ 𝑚 = 𝑢)))
18772, 186dom2lem 7947 . . . . . . . . . . . . . . . 16 (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1→(0...(𝑃 − 1)))
188 f1f1orn 6110 . . . . . . . . . . . . . . . 16 ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1→(0...(𝑃 − 1)) → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
189187, 188syl 17 . . . . . . . . . . . . . . 15 (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
190 eqid 2621 . . . . . . . . . . . . . . . . . 18 (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) = (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))
191190rnmpt 5336 . . . . . . . . . . . . . . . . 17 ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) = {𝑢 ∣ ∃𝑚 ∈ (0...𝑁)𝑢 = ((𝑚↑2) mod 𝑃)}
1922, 191eqtr4i 2646 . . . . . . . . . . . . . . . 16 𝐴 = ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))
193 f1oeq3 6091 . . . . . . . . . . . . . . . 16 (𝐴 = ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)) → ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto𝐴 ↔ (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃))))
194192, 193ax-mp 5 . . . . . . . . . . . . . . 15 ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto𝐴 ↔ (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto→ran (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)))
195189, 194sylibr 224 . . . . . . . . . . . . . 14 (𝜑 → (𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto𝐴)
196 ovex 6638 . . . . . . . . . . . . . . 15 (0...𝑁) ∈ V
197196f1oen 7928 . . . . . . . . . . . . . 14 ((𝑚 ∈ (0...𝑁) ↦ ((𝑚↑2) mod 𝑃)):(0...𝑁)–1-1-onto𝐴 → (0...𝑁) ≈ 𝐴)
198195, 197syl 17 . . . . . . . . . . . . 13 (𝜑 → (0...𝑁) ≈ 𝐴)
199198ensymd 7959 . . . . . . . . . . . 12 (𝜑𝐴 ≈ (0...𝑁))
200 ax-1cn 9946 . . . . . . . . . . . . . . 15 1 ∈ ℂ
201 pncan 10239 . . . . . . . . . . . . . . 15 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 + 1) − 1) = 𝑁)
20260, 200, 201sylancl 693 . . . . . . . . . . . . . 14 (𝜑 → ((𝑁 + 1) − 1) = 𝑁)
203202oveq2d 6626 . . . . . . . . . . . . 13 (𝜑 → (0...((𝑁 + 1) − 1)) = (0...𝑁))
20459nnnn0d 11303 . . . . . . . . . . . . . . . 16 (𝜑𝑁 ∈ ℕ0)
205 peano2nn0 11285 . . . . . . . . . . . . . . . 16 (𝑁 ∈ ℕ0 → (𝑁 + 1) ∈ ℕ0)
206204, 205syl 17 . . . . . . . . . . . . . . 15 (𝜑 → (𝑁 + 1) ∈ ℕ0)
207206nn0zd 11432 . . . . . . . . . . . . . 14 (𝜑 → (𝑁 + 1) ∈ ℤ)
208 fz01en 12319 . . . . . . . . . . . . . 14 ((𝑁 + 1) ∈ ℤ → (0...((𝑁 + 1) − 1)) ≈ (1...(𝑁 + 1)))
209207, 208syl 17 . . . . . . . . . . . . 13 (𝜑 → (0...((𝑁 + 1) − 1)) ≈ (1...(𝑁 + 1)))
210203, 209eqbrtrrd 4642 . . . . . . . . . . . 12 (𝜑 → (0...𝑁) ≈ (1...(𝑁 + 1)))
211 entr 7960 . . . . . . . . . . . 12 ((𝐴 ≈ (0...𝑁) ∧ (0...𝑁) ≈ (1...(𝑁 + 1))) → 𝐴 ≈ (1...(𝑁 + 1)))
212199, 210, 211syl2anc 692 . . . . . . . . . . 11 (𝜑𝐴 ≈ (1...(𝑁 + 1)))
213 ssfi 8132 . . . . . . . . . . . . 13 (((0...(𝑃 − 1)) ∈ Fin ∧ 𝐴 ⊆ (0...(𝑃 − 1))) → 𝐴 ∈ Fin)
2141, 15, 213syl2anc 692 . . . . . . . . . . . 12 (𝜑𝐴 ∈ Fin)
215 fzfid 12720 . . . . . . . . . . . 12 (𝜑 → (1...(𝑁 + 1)) ∈ Fin)
216 hashen 13083 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ (1...(𝑁 + 1)) ∈ Fin) → ((#‘𝐴) = (#‘(1...(𝑁 + 1))) ↔ 𝐴 ≈ (1...(𝑁 + 1))))
217214, 215, 216syl2anc 692 . . . . . . . . . . 11 (𝜑 → ((#‘𝐴) = (#‘(1...(𝑁 + 1))) ↔ 𝐴 ≈ (1...(𝑁 + 1))))
218212, 217mpbird 247 . . . . . . . . . 10 (𝜑 → (#‘𝐴) = (#‘(1...(𝑁 + 1))))
219 hashfz1 13082 . . . . . . . . . . 11 ((𝑁 + 1) ∈ ℕ0 → (#‘(1...(𝑁 + 1))) = (𝑁 + 1))
220206, 219syl 17 . . . . . . . . . 10 (𝜑 → (#‘(1...(𝑁 + 1))) = (𝑁 + 1))
221218, 220eqtrd 2655 . . . . . . . . 9 (𝜑 → (#‘𝐴) = (𝑁 + 1))
22227ex 450 . . . . . . . . . . . . . . 15 (𝜑 → (𝑣𝐴 → ((𝑃 − 1) − 𝑣) ∈ (0...(𝑃 − 1))))
22320adantr 481 . . . . . . . . . . . . . . . . 17 ((𝜑 ∧ (𝑣𝐴𝑘𝐴)) → (𝑃 − 1) ∈ ℂ)
224 fzssuz 12332 . . . . . . . . . . . . . . . . . . . . 21 (0...(𝑃 − 1)) ⊆ (ℤ‘0)
225 uzssz 11659 . . . . . . . . . . . . . . . . . . . . . 22 (ℤ‘0) ⊆ ℤ
226 zsscn 11337 . . . . . . . . . . . . . . . . . . . . . 22 ℤ ⊆ ℂ
227225, 226sstri 3596 . . . . . . . . . . . . . . . . . . . . 21 (ℤ‘0) ⊆ ℂ
228224, 227sstri 3596 . . . . . . . . . . . . . . . . . . . 20 (0...(𝑃 − 1)) ⊆ ℂ
22915, 228syl6ss 3599 . . . . . . . . . . . . . . . . . . 19 (𝜑𝐴 ⊆ ℂ)
230229sselda 3587 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑣𝐴) → 𝑣 ∈ ℂ)
231230adantrr 752 . . . . . . . . . . . . . . . . 17 ((𝜑 ∧ (𝑣𝐴𝑘𝐴)) → 𝑣 ∈ ℂ)
232229sselda 3587 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑘𝐴) → 𝑘 ∈ ℂ)
233232adantrl 751 . . . . . . . . . . . . . . . . 17 ((𝜑 ∧ (𝑣𝐴𝑘𝐴)) → 𝑘 ∈ ℂ)
234223, 231, 233subcanad 10387 . . . . . . . . . . . . . . . 16 ((𝜑 ∧ (𝑣𝐴𝑘𝐴)) → (((𝑃 − 1) − 𝑣) = ((𝑃 − 1) − 𝑘) ↔ 𝑣 = 𝑘))
235234ex 450 . . . . . . . . . . . . . . 15 (𝜑 → ((𝑣𝐴𝑘𝐴) → (((𝑃 − 1) − 𝑣) = ((𝑃 − 1) − 𝑘) ↔ 𝑣 = 𝑘)))
236222, 235dom2lem 7947 . . . . . . . . . . . . . 14 (𝜑 → (𝑣𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴1-1→(0...(𝑃 − 1)))
237 f1eq1 6058 . . . . . . . . . . . . . . 15 (𝐹 = (𝑣𝐴 ↦ ((𝑃 − 1) − 𝑣)) → (𝐹:𝐴1-1→(0...(𝑃 − 1)) ↔ (𝑣𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴1-1→(0...(𝑃 − 1))))
23828, 237ax-mp 5 . . . . . . . . . . . . . 14 (𝐹:𝐴1-1→(0...(𝑃 − 1)) ↔ (𝑣𝐴 ↦ ((𝑃 − 1) − 𝑣)):𝐴1-1→(0...(𝑃 − 1)))
239236, 238sylibr 224 . . . . . . . . . . . . 13 (𝜑𝐹:𝐴1-1→(0...(𝑃 − 1)))
240 f1f1orn 6110 . . . . . . . . . . . . 13 (𝐹:𝐴1-1→(0...(𝑃 − 1)) → 𝐹:𝐴1-1-onto→ran 𝐹)
241239, 240syl 17 . . . . . . . . . . . 12 (𝜑𝐹:𝐴1-1-onto→ran 𝐹)
242 f1oeng 7926 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝐹:𝐴1-1-onto→ran 𝐹) → 𝐴 ≈ ran 𝐹)
243214, 241, 242syl2anc 692 . . . . . . . . . . 11 (𝜑𝐴 ≈ ran 𝐹)
244 ssfi 8132 . . . . . . . . . . . . 13 (((0...(𝑃 − 1)) ∈ Fin ∧ ran 𝐹 ⊆ (0...(𝑃 − 1))) → ran 𝐹 ∈ Fin)
2451, 31, 244syl2anc 692 . . . . . . . . . . . 12 (𝜑 → ran 𝐹 ∈ Fin)
246 hashen 13083 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ ran 𝐹 ∈ Fin) → ((#‘𝐴) = (#‘ran 𝐹) ↔ 𝐴 ≈ ran 𝐹))
247214, 245, 246syl2anc 692 . . . . . . . . . . 11 (𝜑 → ((#‘𝐴) = (#‘ran 𝐹) ↔ 𝐴 ≈ ran 𝐹))
248243, 247mpbird 247 . . . . . . . . . 10 (𝜑 → (#‘𝐴) = (#‘ran 𝐹))
249248, 221eqtr3d 2657 . . . . . . . . 9 (𝜑 → (#‘ran 𝐹) = (𝑁 + 1))
250221, 249oveq12d 6628 . . . . . . . 8 (𝜑 → ((#‘𝐴) + (#‘ran 𝐹)) = ((𝑁 + 1) + (𝑁 + 1)))
25162, 71, 2503eqtr4d 2665 . . . . . . 7 (𝜑 → (𝑃 + 1) = ((#‘𝐴) + (#‘ran 𝐹)))
252251adantr 481 . . . . . 6 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝑃 + 1) = ((#‘𝐴) + (#‘ran 𝐹)))
253214adantr 481 . . . . . . 7 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝐴 ∈ Fin)
254245adantr 481 . . . . . . 7 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → ran 𝐹 ∈ Fin)
255 simpr 477 . . . . . . 7 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝐴 ∩ ran 𝐹) = ∅)
256 hashun 13119 . . . . . . 7 ((𝐴 ∈ Fin ∧ ran 𝐹 ∈ Fin ∧ (𝐴 ∩ ran 𝐹) = ∅) → (#‘(𝐴 ∪ ran 𝐹)) = ((#‘𝐴) + (#‘ran 𝐹)))
257253, 254, 255, 256syl3anc 1323 . . . . . 6 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (#‘(𝐴 ∪ ran 𝐹)) = ((#‘𝐴) + (#‘ran 𝐹)))
258252, 257eqtr4d 2658 . . . . 5 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → (𝑃 + 1) = (#‘(𝐴 ∪ ran 𝐹)))
25958, 258breqtrd 4644 . . . 4 ((𝜑 ∧ (𝐴 ∩ ran 𝐹) = ∅) → 𝑃 < (#‘(𝐴 ∪ ran 𝐹)))
260259ex 450 . . 3 (𝜑 → ((𝐴 ∩ ran 𝐹) = ∅ → 𝑃 < (#‘(𝐴 ∪ ran 𝐹))))
261260necon3bd 2804 . 2 (𝜑 → (¬ 𝑃 < (#‘(𝐴 ∪ ran 𝐹)) → (𝐴 ∩ ran 𝐹) ≠ ∅))
26256, 261mpd 15 1 (𝜑 → (𝐴 ∩ ran 𝐹) ≠ ∅)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wo 383  wa 384   = wceq 1480  wcel 1987  {cab 2607  wne 2790  wrex 2908  cun 3557  cin 3558  wss 3559  c0 3896   class class class wbr 4618  cmpt 4678  ran crn 5080  wf 5848  1-1wf1 5849  1-1-ontowf1o 5851  cfv 5852  (class class class)co 6610  cen 7904  cdom 7905  Fincfn 7907  cc 9886  cr 9887  0cc0 9888  1c1 9889   + caddc 9891   · cmul 9893   < clt 10026  cle 10027  cmin 10218  cn 10972  2c2 11022  0cn0 11244  cz 11329  cuz 11639  ...cfz 12276   mod cmo 12616  cexp 12808  #chash 13065  abscabs 13916  cdvds 14918  cprime 15320
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1719  ax-4 1734  ax-5 1836  ax-6 1885  ax-7 1932  ax-8 1989  ax-9 1996  ax-10 2016  ax-11 2031  ax-12 2044  ax-13 2245  ax-ext 2601  ax-rep 4736  ax-sep 4746  ax-nul 4754  ax-pow 4808  ax-pr 4872  ax-un 6909  ax-cnex 9944  ax-resscn 9945  ax-1cn 9946  ax-icn 9947  ax-addcl 9948  ax-addrcl 9949  ax-mulcl 9950  ax-mulrcl 9951  ax-mulcom 9952  ax-addass 9953  ax-mulass 9954  ax-distr 9955  ax-i2m1 9956  ax-1ne0 9957  ax-1rid 9958  ax-rnegex 9959  ax-rrecex 9960  ax-cnre 9961  ax-pre-lttri 9962  ax-pre-lttrn 9963  ax-pre-ltadd 9964  ax-pre-mulgt0 9965  ax-pre-sup 9966
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1037  df-3an 1038  df-tru 1483  df-ex 1702  df-nf 1707  df-sb 1878  df-eu 2473  df-mo 2474  df-clab 2608  df-cleq 2614  df-clel 2617  df-nfc 2750  df-ne 2791  df-nel 2894  df-ral 2912  df-rex 2913  df-reu 2914  df-rmo 2915  df-rab 2916  df-v 3191  df-sbc 3422  df-csb 3519  df-dif 3562  df-un 3564  df-in 3566  df-ss 3573  df-pss 3575  df-nul 3897  df-if 4064  df-pw 4137  df-sn 4154  df-pr 4156  df-tp 4158  df-op 4160  df-uni 4408  df-int 4446  df-iun 4492  df-br 4619  df-opab 4679  df-mpt 4680  df-tr 4718  df-eprel 4990  df-id 4994  df-po 5000  df-so 5001  df-fr 5038  df-we 5040  df-xp 5085  df-rel 5086  df-cnv 5087  df-co 5088  df-dm 5089  df-rn 5090  df-res 5091  df-ima 5092  df-pred 5644  df-ord 5690  df-on 5691  df-lim 5692  df-suc 5693  df-iota 5815  df-fun 5854  df-fn 5855  df-f 5856  df-f1 5857  df-fo 5858  df-f1o 5859  df-fv 5860  df-riota 6571  df-ov 6613  df-oprab 6614  df-mpt2 6615  df-om 7020  df-1st 7120  df-2nd 7121  df-wrecs 7359  df-recs 7420  df-rdg 7458  df-1o 7512  df-2o 7513  df-oadd 7516  df-er 7694  df-en 7908  df-dom 7909  df-sdom 7910  df-fin 7911  df-sup 8300  df-inf 8301  df-card 8717  df-cda 8942  df-pnf 10028  df-mnf 10029  df-xr 10030  df-ltxr 10031  df-le 10032  df-sub 10220  df-neg 10221  df-div 10637  df-nn 10973  df-2 11031  df-3 11032  df-n0 11245  df-xnn0 11316  df-z 11330  df-uz 11640  df-rp 11785  df-fz 12277  df-fl 12541  df-mod 12617  df-seq 12750  df-exp 12809  df-hash 13066  df-cj 13781  df-re 13782  df-im 13783  df-sqrt 13917  df-abs 13918  df-dvds 14919  df-gcd 15152  df-prm 15321
This theorem is referenced by:  4sqlem12  15595
  Copyright terms: Public domain W3C validator