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

Theorem phiprmpw 15763
Description: Value of the Euler ϕ function at a prime power. Theorem 2.5(a) in [ApostolNT] p. 28. (Contributed by Mario Carneiro, 24-Feb-2014.)
Assertion
Ref Expression
phiprmpw ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (ϕ‘(𝑃𝐾)) = ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)))

Proof of Theorem phiprmpw
Dummy variable 𝑥 is distinct from all other variables.
StepHypRef Expression
1 prmnn 15671 . . . 4 (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
2 nnnn0 11548 . . . 4 (𝐾 ∈ ℕ → 𝐾 ∈ ℕ0)
3 nnexpcl 13083 . . . 4 ((𝑃 ∈ ℕ ∧ 𝐾 ∈ ℕ0) → (𝑃𝐾) ∈ ℕ)
41, 2, 3syl2an 589 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℕ)
5 phival 15754 . . 3 ((𝑃𝐾) ∈ ℕ → (ϕ‘(𝑃𝐾)) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
64, 5syl 17 . 2 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (ϕ‘(𝑃𝐾)) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
7 nnm1nn0 11583 . . . . . 6 (𝐾 ∈ ℕ → (𝐾 − 1) ∈ ℕ0)
8 nnexpcl 13083 . . . . . 6 ((𝑃 ∈ ℕ ∧ (𝐾 − 1) ∈ ℕ0) → (𝑃↑(𝐾 − 1)) ∈ ℕ)
91, 7, 8syl2an 589 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℕ)
109nncnd 11294 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℂ)
111nncnd 11294 . . . . 5 (𝑃 ∈ ℙ → 𝑃 ∈ ℂ)
1211adantr 472 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 ∈ ℂ)
13 ax-1cn 10249 . . . . 5 1 ∈ ℂ
14 subdi 10719 . . . . 5 (((𝑃↑(𝐾 − 1)) ∈ ℂ ∧ 𝑃 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1513, 14mp3an3 1574 . . . 4 (((𝑃↑(𝐾 − 1)) ∈ ℂ ∧ 𝑃 ∈ ℂ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1610, 12, 15syl2anc 579 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1710mulid1d 10313 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · 1) = (𝑃↑(𝐾 − 1)))
1817oveq2d 6860 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))))
19 inrab 4065 . . . . . . 7 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))}
20 elfzelz 12552 . . . . . . . . . . . 12 (𝑥 ∈ (1...(𝑃𝐾)) → 𝑥 ∈ ℤ)
21 prmz 15672 . . . . . . . . . . . . . . . . 17 (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
22 rpexp 15714 . . . . . . . . . . . . . . . . 17 ((𝑃 ∈ ℤ ∧ 𝑥 ∈ ℤ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
2321, 22syl3an1 1202 . . . . . . . . . . . . . . . 16 ((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
24233expa 1147 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ) ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
2524an32s 642 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
26 simpr 477 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → 𝑥 ∈ ℤ)
27 zexpcl 13085 . . . . . . . . . . . . . . . . . 18 ((𝑃 ∈ ℤ ∧ 𝐾 ∈ ℕ0) → (𝑃𝐾) ∈ ℤ)
2821, 2, 27syl2an 589 . . . . . . . . . . . . . . . . 17 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℤ)
2928adantr 472 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑃𝐾) ∈ ℤ)
30 gcdcom 15519 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ ℤ ∧ (𝑃𝐾) ∈ ℤ) → (𝑥 gcd (𝑃𝐾)) = ((𝑃𝐾) gcd 𝑥))
3126, 29, 30syl2anc 579 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑥 gcd (𝑃𝐾)) = ((𝑃𝐾) gcd 𝑥))
3231eqeq1d 2767 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ((𝑃𝐾) gcd 𝑥) = 1))
33 coprm 15705 . . . . . . . . . . . . . . 15 ((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ) → (¬ 𝑃𝑥 ↔ (𝑃 gcd 𝑥) = 1))
3433adantlr 706 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (¬ 𝑃𝑥 ↔ (𝑃 gcd 𝑥) = 1))
3525, 32, 343bitr4d 302 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃𝑥))
36 zcn 11631 . . . . . . . . . . . . . . . . 17 (𝑥 ∈ ℤ → 𝑥 ∈ ℂ)
3736adantl 473 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → 𝑥 ∈ ℂ)
3837subid1d 10637 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑥 − 0) = 𝑥)
3938breq2d 4823 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑃 ∥ (𝑥 − 0) ↔ 𝑃𝑥))
4039notbid 309 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (¬ 𝑃 ∥ (𝑥 − 0) ↔ ¬ 𝑃𝑥))
4135, 40bitr4d 273 . . . . . . . . . . . 12 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃 ∥ (𝑥 − 0)))
4220, 41sylan2 586 . . . . . . . . . . 11 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃 ∥ (𝑥 − 0)))
4342biimpd 220 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 → ¬ 𝑃 ∥ (𝑥 − 0)))
44 imnan 388 . . . . . . . . . 10 (((𝑥 gcd (𝑃𝐾)) = 1 → ¬ 𝑃 ∥ (𝑥 − 0)) ↔ ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
4543, 44sylib 209 . . . . . . . . 9 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
4645ralrimiva 3113 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ∀𝑥 ∈ (1...(𝑃𝐾)) ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
47 rabeq0 4123 . . . . . . . 8 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))} = ∅ ↔ ∀𝑥 ∈ (1...(𝑃𝐾)) ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
4846, 47sylibr 225 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))} = ∅)
4919, 48syl5eq 2811 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ∅)
50 fzfi 12982 . . . . . . . 8 (1...(𝑃𝐾)) ∈ Fin
51 ssrab2 3849 . . . . . . . 8 {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ⊆ (1...(𝑃𝐾))
52 ssfi 8389 . . . . . . . 8 (((1...(𝑃𝐾)) ∈ Fin ∧ {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ⊆ (1...(𝑃𝐾))) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin)
5350, 51, 52mp2an 683 . . . . . . 7 {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin
54 ssrab2 3849 . . . . . . . 8 {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ⊆ (1...(𝑃𝐾))
55 ssfi 8389 . . . . . . . 8 (((1...(𝑃𝐾)) ∈ Fin ∧ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ⊆ (1...(𝑃𝐾))) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ∈ Fin)
5650, 54, 55mp2an 683 . . . . . . 7 {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ∈ Fin
57 hashun 13376 . . . . . . 7 (({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin ∧ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ∈ Fin ∧ ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ∅) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})))
5853, 56, 57mp3an12 1575 . . . . . 6 (({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ∅ → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})))
5949, 58syl 17 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})))
6042biimprd 239 . . . . . . . . . . . 12 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (¬ 𝑃 ∥ (𝑥 − 0) → (𝑥 gcd (𝑃𝐾)) = 1))
6160con1d 141 . . . . . . . . . . 11 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (¬ (𝑥 gcd (𝑃𝐾)) = 1 → 𝑃 ∥ (𝑥 − 0)))
6261orrd 889 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
6362ralrimiva 3113 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ∀𝑥 ∈ (1...(𝑃𝐾))((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
64 rabid2 3266 . . . . . . . . 9 ((1...(𝑃𝐾)) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))} ↔ ∀𝑥 ∈ (1...(𝑃𝐾))((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
6563, 64sylibr 225 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (1...(𝑃𝐾)) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))})
66 unrab 4064 . . . . . . . 8 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))}
6765, 66syl6reqr 2818 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = (1...(𝑃𝐾)))
6867fveq2d 6381 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = (♯‘(1...(𝑃𝐾))))
694nnnn0d 11600 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℕ0)
70 hashfz1 13341 . . . . . . 7 ((𝑃𝐾) ∈ ℕ0 → (♯‘(1...(𝑃𝐾))) = (𝑃𝐾))
7169, 70syl 17 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘(1...(𝑃𝐾))) = (𝑃𝐾))
72 expm1t 13098 . . . . . . 7 ((𝑃 ∈ ℂ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) = ((𝑃↑(𝐾 − 1)) · 𝑃))
7311, 72sylan 575 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) = ((𝑃↑(𝐾 − 1)) · 𝑃))
7468, 71, 733eqtrd 2803 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((𝑃↑(𝐾 − 1)) · 𝑃))
751adantr 472 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 ∈ ℕ)
76 1zzd 11658 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 1 ∈ ℤ)
77 nn0uz 11925 . . . . . . . . . . 11 0 = (ℤ‘0)
78 1m1e0 11346 . . . . . . . . . . . 12 (1 − 1) = 0
7978fveq2i 6380 . . . . . . . . . . 11 (ℤ‘(1 − 1)) = (ℤ‘0)
8077, 79eqtr4i 2790 . . . . . . . . . 10 0 = (ℤ‘(1 − 1))
8169, 80syl6eleq 2854 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ (ℤ‘(1 − 1)))
82 0zd 11638 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 0 ∈ ℤ)
8375, 76, 81, 82hashdvds 15762 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ((⌊‘(((𝑃𝐾) − 0) / 𝑃)) − (⌊‘(((1 − 1) − 0) / 𝑃))))
844nncnd 11294 . . . . . . . . . . . . . 14 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℂ)
8584subid1d 10637 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃𝐾) − 0) = (𝑃𝐾))
8685oveq1d 6859 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) − 0) / 𝑃) = ((𝑃𝐾) / 𝑃))
8775nnne0d 11324 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 ≠ 0)
88 nnz 11649 . . . . . . . . . . . . . 14 (𝐾 ∈ ℕ → 𝐾 ∈ ℤ)
8988adantl 473 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝐾 ∈ ℤ)
9012, 87, 89expm1d 13228 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) = ((𝑃𝐾) / 𝑃))
9186, 90eqtr4d 2802 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) − 0) / 𝑃) = (𝑃↑(𝐾 − 1)))
9291fveq2d 6381 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((𝑃𝐾) − 0) / 𝑃)) = (⌊‘(𝑃↑(𝐾 − 1))))
939nnzd 11731 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℤ)
94 flid 12820 . . . . . . . . . . 11 ((𝑃↑(𝐾 − 1)) ∈ ℤ → (⌊‘(𝑃↑(𝐾 − 1))) = (𝑃↑(𝐾 − 1)))
9593, 94syl 17 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(𝑃↑(𝐾 − 1))) = (𝑃↑(𝐾 − 1)))
9692, 95eqtrd 2799 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((𝑃𝐾) − 0) / 𝑃)) = (𝑃↑(𝐾 − 1)))
9778oveq1i 6854 . . . . . . . . . . . . . 14 ((1 − 1) − 0) = (0 − 0)
98 0m0e0 11401 . . . . . . . . . . . . . 14 (0 − 0) = 0
9997, 98eqtri 2787 . . . . . . . . . . . . 13 ((1 − 1) − 0) = 0
10099oveq1i 6854 . . . . . . . . . . . 12 (((1 − 1) − 0) / 𝑃) = (0 / 𝑃)
10112, 87div0d 11056 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (0 / 𝑃) = 0)
102100, 101syl5eq 2811 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((1 − 1) − 0) / 𝑃) = 0)
103102fveq2d 6381 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((1 − 1) − 0) / 𝑃)) = (⌊‘0))
104 0z 11637 . . . . . . . . . . 11 0 ∈ ℤ
105 flid 12820 . . . . . . . . . . 11 (0 ∈ ℤ → (⌊‘0) = 0)
106104, 105ax-mp 5 . . . . . . . . . 10 (⌊‘0) = 0
107103, 106syl6eq 2815 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((1 − 1) − 0) / 𝑃)) = 0)
10896, 107oveq12d 6862 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((⌊‘(((𝑃𝐾) − 0) / 𝑃)) − (⌊‘(((1 − 1) − 0) / 𝑃))) = ((𝑃↑(𝐾 − 1)) − 0))
10910subid1d 10637 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) − 0) = (𝑃↑(𝐾 − 1)))
11083, 108, 1093eqtrd 2803 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = (𝑃↑(𝐾 − 1)))
111110oveq2d 6860 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (𝑃↑(𝐾 − 1))))
112 hashcl 13352 . . . . . . . . 9 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℕ0)
11353, 112ax-mp 5 . . . . . . . 8 (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℕ0
114113nn0cni 11553 . . . . . . 7 (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℂ
115 addcom 10478 . . . . . . 7 (((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℂ ∧ (𝑃↑(𝐾 − 1)) ∈ ℂ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (𝑃↑(𝐾 − 1))) = ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})))
116114, 10, 115sylancr 581 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (𝑃↑(𝐾 − 1))) = ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})))
117111, 116eqtrd 2799 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})))
11859, 74, 1173eqtr3rd 2808 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})) = ((𝑃↑(𝐾 − 1)) · 𝑃))
11910, 12mulcld 10316 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · 𝑃) ∈ ℂ)
120114a1i 11 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℂ)
121119, 10, 120subaddd 10666 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ↔ ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})) = ((𝑃↑(𝐾 − 1)) · 𝑃)))
122118, 121mpbird 248 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
12316, 18, 1223eqtrrd 2804 . 2 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) = ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)))
1246, 123eqtrd 2799 1 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (ϕ‘(𝑃𝐾)) = ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  wo 873   = wceq 1652  wcel 2155  wral 3055  {crab 3059  cun 3732  cin 3733  wss 3734  c0 4081   class class class wbr 4811  cfv 6070  (class class class)co 6844  Fincfn 8162  cc 10189  0cc0 10191  1c1 10192   + caddc 10194   · cmul 10196  cmin 10522   / cdiv 10940  cn 11276  0cn0 11540  cz 11626  cuz 11889  ...cfz 12536  cfl 12802  cexp 13070  chash 13324  cdvds 15268   gcd cgcd 15500  cprime 15668  ϕcphi 15751
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1890  ax-4 1904  ax-5 2005  ax-6 2070  ax-7 2105  ax-8 2157  ax-9 2164  ax-10 2183  ax-11 2198  ax-12 2211  ax-13 2352  ax-ext 2743  ax-rep 4932  ax-sep 4943  ax-nul 4951  ax-pow 5003  ax-pr 5064  ax-un 7149  ax-cnex 10247  ax-resscn 10248  ax-1cn 10249  ax-icn 10250  ax-addcl 10251  ax-addrcl 10252  ax-mulcl 10253  ax-mulrcl 10254  ax-mulcom 10255  ax-addass 10256  ax-mulass 10257  ax-distr 10258  ax-i2m1 10259  ax-1ne0 10260  ax-1rid 10261  ax-rnegex 10262  ax-rrecex 10263  ax-cnre 10264  ax-pre-lttri 10265  ax-pre-lttrn 10266  ax-pre-ltadd 10267  ax-pre-mulgt0 10268  ax-pre-sup 10269
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 874  df-3or 1108  df-3an 1109  df-tru 1656  df-ex 1875  df-nf 1879  df-sb 2063  df-mo 2565  df-eu 2582  df-clab 2752  df-cleq 2758  df-clel 2761  df-nfc 2896  df-ne 2938  df-nel 3041  df-ral 3060  df-rex 3061  df-reu 3062  df-rmo 3063  df-rab 3064  df-v 3352  df-sbc 3599  df-csb 3694  df-dif 3737  df-un 3739  df-in 3741  df-ss 3748  df-pss 3750  df-nul 4082  df-if 4246  df-pw 4319  df-sn 4337  df-pr 4339  df-tp 4341  df-op 4343  df-uni 4597  df-int 4636  df-iun 4680  df-br 4812  df-opab 4874  df-mpt 4891  df-tr 4914  df-id 5187  df-eprel 5192  df-po 5200  df-so 5201  df-fr 5238  df-we 5240  df-xp 5285  df-rel 5286  df-cnv 5287  df-co 5288  df-dm 5289  df-rn 5290  df-res 5291  df-ima 5292  df-pred 5867  df-ord 5913  df-on 5914  df-lim 5915  df-suc 5916  df-iota 6033  df-fun 6072  df-fn 6073  df-f 6074  df-f1 6075  df-fo 6076  df-f1o 6077  df-fv 6078  df-riota 6805  df-ov 6847  df-oprab 6848  df-mpt2 6849  df-om 7266  df-1st 7368  df-2nd 7369  df-wrecs 7612  df-recs 7674  df-rdg 7712  df-1o 7766  df-2o 7767  df-oadd 7770  df-er 7949  df-en 8163  df-dom 8164  df-sdom 8165  df-fin 8166  df-sup 8557  df-inf 8558  df-card 9018  df-cda 9245  df-pnf 10332  df-mnf 10333  df-xr 10334  df-ltxr 10335  df-le 10336  df-sub 10524  df-neg 10525  df-div 10941  df-nn 11277  df-2 11337  df-3 11338  df-n0 11541  df-z 11627  df-uz 11890  df-rp 12032  df-fz 12537  df-fl 12804  df-mod 12880  df-seq 13012  df-exp 13071  df-hash 13325  df-cj 14127  df-re 14128  df-im 14129  df-sqrt 14263  df-abs 14264  df-dvds 15269  df-gcd 15501  df-prm 15669  df-phi 15753
This theorem is referenced by:  phiprm  15764
  Copyright terms: Public domain W3C validator