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

Theorem phisum 16105
Description: The divisor sum identity of the totient function. Theorem 2.2 in [ApostolNT] p. 26. (Contributed by Stefan O'Rear, 12-Sep-2015.)
Assertion
Ref Expression
phisum (𝑁 ∈ ℕ → Σ𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘𝑑) = 𝑁)
Distinct variable group:   𝑥,𝑁,𝑑

Proof of Theorem phisum
Dummy variables 𝑧 𝑦 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 breq1 5045 . . . . . 6 (𝑥 = 𝑦 → (𝑥𝑁𝑦𝑁))
21elrab 3660 . . . . 5 (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↔ (𝑦 ∈ ℕ ∧ 𝑦𝑁))
3 hashgcdeq 16104 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑦 ∈ ℕ) → (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = if(𝑦𝑁, (ϕ‘(𝑁 / 𝑦)), 0))
43adantrr 715 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑦 ∈ ℕ ∧ 𝑦𝑁)) → (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = if(𝑦𝑁, (ϕ‘(𝑁 / 𝑦)), 0))
5 iftrue 4449 . . . . . . 7 (𝑦𝑁 → if(𝑦𝑁, (ϕ‘(𝑁 / 𝑦)), 0) = (ϕ‘(𝑁 / 𝑦)))
65ad2antll 727 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑦 ∈ ℕ ∧ 𝑦𝑁)) → if(𝑦𝑁, (ϕ‘(𝑁 / 𝑦)), 0) = (ϕ‘(𝑁 / 𝑦)))
74, 6eqtrd 2855 . . . . 5 ((𝑁 ∈ ℕ ∧ (𝑦 ∈ ℕ ∧ 𝑦𝑁)) → (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = (ϕ‘(𝑁 / 𝑦)))
82, 7sylan2b 595 . . . 4 ((𝑁 ∈ ℕ ∧ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = (ϕ‘(𝑁 / 𝑦)))
98sumeq2dv 15040 . . 3 (𝑁 ∈ ℕ → Σ𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = Σ𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘(𝑁 / 𝑦)))
10 fzfi 13324 . . . . 5 (1...𝑁) ∈ Fin
11 dvdsssfz1 15648 . . . . 5 (𝑁 ∈ ℕ → {𝑥 ∈ ℕ ∣ 𝑥𝑁} ⊆ (1...𝑁))
12 ssfi 8716 . . . . 5 (((1...𝑁) ∈ Fin ∧ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ⊆ (1...𝑁)) → {𝑥 ∈ ℕ ∣ 𝑥𝑁} ∈ Fin)
1310, 11, 12sylancr 589 . . . 4 (𝑁 ∈ ℕ → {𝑥 ∈ ℕ ∣ 𝑥𝑁} ∈ Fin)
14 fzofi 13326 . . . . . 6 (0..^𝑁) ∈ Fin
15 ssrab2 4035 . . . . . 6 {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ⊆ (0..^𝑁)
16 ssfi 8716 . . . . . 6 (((0..^𝑁) ∈ Fin ∧ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ⊆ (0..^𝑁)) → {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ∈ Fin)
1714, 15, 16mp2an 690 . . . . 5 {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ∈ Fin
1817a1i 11 . . . 4 ((𝑁 ∈ ℕ ∧ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ∈ Fin)
19 oveq1 7140 . . . . . . . . . 10 (𝑧 = 𝑤 → (𝑧 gcd 𝑁) = (𝑤 gcd 𝑁))
2019eqeq1d 2822 . . . . . . . . 9 (𝑧 = 𝑤 → ((𝑧 gcd 𝑁) = 𝑦 ↔ (𝑤 gcd 𝑁) = 𝑦))
2120elrab 3660 . . . . . . . 8 (𝑤 ∈ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} ↔ (𝑤 ∈ (0..^𝑁) ∧ (𝑤 gcd 𝑁) = 𝑦))
2221simprbi 499 . . . . . . 7 (𝑤 ∈ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} → (𝑤 gcd 𝑁) = 𝑦)
2322rgen 3135 . . . . . 6 𝑤 ∈ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} (𝑤 gcd 𝑁) = 𝑦
2423rgenw 3137 . . . . 5 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}∀𝑤 ∈ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} (𝑤 gcd 𝑁) = 𝑦
25 invdisj 5026 . . . . 5 (∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}∀𝑤 ∈ {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} (𝑤 gcd 𝑁) = 𝑦Disj 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦})
2624, 25mp1i 13 . . . 4 (𝑁 ∈ ℕ → Disj 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦})
2713, 18, 26hashiun 15157 . . 3 (𝑁 ∈ ℕ → (♯‘ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = Σ𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (♯‘{𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}))
28 fveq2 6646 . . . 4 (𝑑 = (𝑁 / 𝑦) → (ϕ‘𝑑) = (ϕ‘(𝑁 / 𝑦)))
29 eqid 2820 . . . . 5 {𝑥 ∈ ℕ ∣ 𝑥𝑁} = {𝑥 ∈ ℕ ∣ 𝑥𝑁}
30 eqid 2820 . . . . 5 (𝑧 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↦ (𝑁 / 𝑧)) = (𝑧 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↦ (𝑁 / 𝑧))
3129, 30dvdsflip 15647 . . . 4 (𝑁 ∈ ℕ → (𝑧 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↦ (𝑁 / 𝑧)):{𝑥 ∈ ℕ ∣ 𝑥𝑁}–1-1-onto→{𝑥 ∈ ℕ ∣ 𝑥𝑁})
32 oveq2 7141 . . . . . 6 (𝑧 = 𝑦 → (𝑁 / 𝑧) = (𝑁 / 𝑦))
33 ovex 7166 . . . . . 6 (𝑁 / 𝑦) ∈ V
3432, 30, 33fvmpt 6744 . . . . 5 (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} → ((𝑧 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↦ (𝑁 / 𝑧))‘𝑦) = (𝑁 / 𝑦))
3534adantl 484 . . . 4 ((𝑁 ∈ ℕ ∧ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → ((𝑧 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↦ (𝑁 / 𝑧))‘𝑦) = (𝑁 / 𝑦))
36 elrabi 3655 . . . . . . 7 (𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} → 𝑑 ∈ ℕ)
3736adantl 484 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → 𝑑 ∈ ℕ)
3837phicld 16087 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → (ϕ‘𝑑) ∈ ℕ)
3938nncnd 11632 . . . 4 ((𝑁 ∈ ℕ ∧ 𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁}) → (ϕ‘𝑑) ∈ ℂ)
4028, 13, 31, 35, 39fsumf1o 15060 . . 3 (𝑁 ∈ ℕ → Σ𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘𝑑) = Σ𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘(𝑁 / 𝑦)))
419, 27, 403eqtr4rd 2866 . 2 (𝑁 ∈ ℕ → Σ𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘𝑑) = (♯‘ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}))
42 breq1 5045 . . . . . . . . 9 (𝑥 = (𝑧 gcd 𝑁) → (𝑥𝑁 ↔ (𝑧 gcd 𝑁) ∥ 𝑁))
43 elfzoelz 13022 . . . . . . . . . . 11 (𝑧 ∈ (0..^𝑁) → 𝑧 ∈ ℤ)
4443adantl 484 . . . . . . . . . 10 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → 𝑧 ∈ ℤ)
45 nnz 11983 . . . . . . . . . . 11 (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
4645adantr 483 . . . . . . . . . 10 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → 𝑁 ∈ ℤ)
47 nnne0 11650 . . . . . . . . . . . . 13 (𝑁 ∈ ℕ → 𝑁 ≠ 0)
4847neneqd 3011 . . . . . . . . . . . 12 (𝑁 ∈ ℕ → ¬ 𝑁 = 0)
4948intnand 491 . . . . . . . . . . 11 (𝑁 ∈ ℕ → ¬ (𝑧 = 0 ∧ 𝑁 = 0))
5049adantr 483 . . . . . . . . . 10 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → ¬ (𝑧 = 0 ∧ 𝑁 = 0))
51 gcdn0cl 15829 . . . . . . . . . 10 (((𝑧 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑧 = 0 ∧ 𝑁 = 0)) → (𝑧 gcd 𝑁) ∈ ℕ)
5244, 46, 50, 51syl21anc 835 . . . . . . . . 9 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → (𝑧 gcd 𝑁) ∈ ℕ)
53 gcddvds 15830 . . . . . . . . . . 11 ((𝑧 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑧 gcd 𝑁) ∥ 𝑧 ∧ (𝑧 gcd 𝑁) ∥ 𝑁))
5444, 46, 53syl2anc 586 . . . . . . . . . 10 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → ((𝑧 gcd 𝑁) ∥ 𝑧 ∧ (𝑧 gcd 𝑁) ∥ 𝑁))
5554simprd 498 . . . . . . . . 9 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → (𝑧 gcd 𝑁) ∥ 𝑁)
5642, 52, 55elrabd 3662 . . . . . . . 8 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → (𝑧 gcd 𝑁) ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁})
57 clel5 3636 . . . . . . . 8 ((𝑧 gcd 𝑁) ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} ↔ ∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦)
5856, 57sylib 220 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑧 ∈ (0..^𝑁)) → ∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦)
5958ralrimiva 3169 . . . . . 6 (𝑁 ∈ ℕ → ∀𝑧 ∈ (0..^𝑁)∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦)
60 rabid2 3368 . . . . . 6 ((0..^𝑁) = {𝑧 ∈ (0..^𝑁) ∣ ∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦} ↔ ∀𝑧 ∈ (0..^𝑁)∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦)
6159, 60sylibr 236 . . . . 5 (𝑁 ∈ ℕ → (0..^𝑁) = {𝑧 ∈ (0..^𝑁) ∣ ∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦})
62 iunrab 4952 . . . . 5 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} = {𝑧 ∈ (0..^𝑁) ∣ ∃𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (𝑧 gcd 𝑁) = 𝑦}
6361, 62syl6reqr 2874 . . . 4 (𝑁 ∈ ℕ → 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦} = (0..^𝑁))
6463fveq2d 6650 . . 3 (𝑁 ∈ ℕ → (♯‘ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = (♯‘(0..^𝑁)))
65 nnnn0 11883 . . . 4 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
66 hashfzo0 13776 . . . 4 (𝑁 ∈ ℕ0 → (♯‘(0..^𝑁)) = 𝑁)
6765, 66syl 17 . . 3 (𝑁 ∈ ℕ → (♯‘(0..^𝑁)) = 𝑁)
6864, 67eqtrd 2855 . 2 (𝑁 ∈ ℕ → (♯‘ 𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} {𝑧 ∈ (0..^𝑁) ∣ (𝑧 gcd 𝑁) = 𝑦}) = 𝑁)
6941, 68eqtrd 2855 1 (𝑁 ∈ ℕ → Σ𝑑 ∈ {𝑥 ∈ ℕ ∣ 𝑥𝑁} (ϕ‘𝑑) = 𝑁)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wa 398   = wceq 1537  wcel 2114  wral 3125  wrex 3126  {crab 3129  wss 3913  ifcif 4443   ciun 4895  Disj wdisj 5007   class class class wbr 5042  cmpt 5122  cfv 6331  (class class class)co 7133  Fincfn 8487  0cc0 10515  1c1 10516   / cdiv 11275  cn 11616  0cn0 11876  cz 11960  ...cfz 12876  ..^cfzo 13017  chash 13675  Σcsu 15022  cdvds 15587   gcd cgcd 15821  ϕcphi 16079
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2792  ax-rep 5166  ax-sep 5179  ax-nul 5186  ax-pow 5242  ax-pr 5306  ax-un 7439  ax-inf2 9082  ax-cnex 10571  ax-resscn 10572  ax-1cn 10573  ax-icn 10574  ax-addcl 10575  ax-addrcl 10576  ax-mulcl 10577  ax-mulrcl 10578  ax-mulcom 10579  ax-addass 10580  ax-mulass 10581  ax-distr 10582  ax-i2m1 10583  ax-1ne0 10584  ax-1rid 10585  ax-rnegex 10586  ax-rrecex 10587  ax-cnre 10588  ax-pre-lttri 10589  ax-pre-lttrn 10590  ax-pre-ltadd 10591  ax-pre-mulgt0 10592  ax-pre-sup 10593
This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1540  df-fal 1550  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2653  df-clab 2799  df-cleq 2813  df-clel 2891  df-nfc 2959  df-ne 3007  df-nel 3111  df-ral 3130  df-rex 3131  df-reu 3132  df-rmo 3133  df-rab 3134  df-v 3475  df-sbc 3753  df-csb 3861  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-pss 3932  df-nul 4270  df-if 4444  df-pw 4517  df-sn 4544  df-pr 4546  df-tp 4548  df-op 4550  df-uni 4815  df-int 4853  df-iun 4897  df-disj 5008  df-br 5043  df-opab 5105  df-mpt 5123  df-tr 5149  df-id 5436  df-eprel 5441  df-po 5450  df-so 5451  df-fr 5490  df-se 5491  df-we 5492  df-xp 5537  df-rel 5538  df-cnv 5539  df-co 5540  df-dm 5541  df-rn 5542  df-res 5543  df-ima 5544  df-pred 6124  df-ord 6170  df-on 6171  df-lim 6172  df-suc 6173  df-iota 6290  df-fun 6333  df-fn 6334  df-f 6335  df-f1 6336  df-fo 6337  df-f1o 6338  df-fv 6339  df-isom 6340  df-riota 7091  df-ov 7136  df-oprab 7137  df-mpo 7138  df-om 7559  df-1st 7667  df-2nd 7668  df-wrecs 7925  df-recs 7986  df-rdg 8024  df-1o 8080  df-oadd 8084  df-er 8267  df-en 8488  df-dom 8489  df-sdom 8490  df-fin 8491  df-sup 8884  df-inf 8885  df-oi 8952  df-card 9346  df-pnf 10655  df-mnf 10656  df-xr 10657  df-ltxr 10658  df-le 10659  df-sub 10850  df-neg 10851  df-div 11276  df-nn 11617  df-2 11679  df-3 11680  df-n0 11877  df-xnn0 11947  df-z 11961  df-uz 12223  df-rp 12369  df-fz 12877  df-fzo 13018  df-fl 13146  df-mod 13222  df-seq 13354  df-exp 13415  df-hash 13676  df-cj 14438  df-re 14439  df-im 14440  df-sqrt 14574  df-abs 14575  df-clim 14825  df-sum 15023  df-dvds 15588  df-gcd 15822  df-phi 16081
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator