ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  phiprmpw GIF version

Theorem phiprmpw 11737
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 11631 . . . 4 (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
2 nnnn0 8882 . . . 4 (𝐾 ∈ ℕ → 𝐾 ∈ ℕ0)
3 nnexpcl 10193 . . . 4 ((𝑃 ∈ ℕ ∧ 𝐾 ∈ ℕ0) → (𝑃𝐾) ∈ ℕ)
41, 2, 3syl2an 285 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℕ)
5 phival 11728 . . 3 ((𝑃𝐾) ∈ ℕ → (ϕ‘(𝑃𝐾)) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
64, 5syl 14 . 2 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (ϕ‘(𝑃𝐾)) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
7 nnm1nn0 8916 . . . . . 6 (𝐾 ∈ ℕ → (𝐾 − 1) ∈ ℕ0)
8 nnexpcl 10193 . . . . . 6 ((𝑃 ∈ ℕ ∧ (𝐾 − 1) ∈ ℕ0) → (𝑃↑(𝐾 − 1)) ∈ ℕ)
91, 7, 8syl2an 285 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℕ)
109nncnd 8638 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℂ)
111nncnd 8638 . . . . 5 (𝑃 ∈ ℙ → 𝑃 ∈ ℂ)
1211adantr 272 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 ∈ ℂ)
13 ax-1cn 7632 . . . . 5 1 ∈ ℂ
14 subdi 8060 . . . . 5 (((𝑃↑(𝐾 − 1)) ∈ ℂ ∧ 𝑃 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1513, 14mp3an3 1285 . . . 4 (((𝑃↑(𝐾 − 1)) ∈ ℂ ∧ 𝑃 ∈ ℂ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1610, 12, 15syl2anc 406 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)))
1710mulid1d 7701 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · 1) = (𝑃↑(𝐾 − 1)))
1817oveq2d 5742 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃↑(𝐾 − 1)) · 𝑃) − ((𝑃↑(𝐾 − 1)) · 1)) = (((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))))
19 phivalfi 11727 . . . . . . 7 ((𝑃𝐾) ∈ ℕ → {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin)
204, 19syl 14 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin)
21 1zzd 8979 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 1 ∈ ℤ)
22 prmz 11632 . . . . . . . . 9 (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
23 zexpcl 10195 . . . . . . . . 9 ((𝑃 ∈ ℤ ∧ 𝐾 ∈ ℕ0) → (𝑃𝐾) ∈ ℤ)
2422, 2, 23syl2an 285 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℤ)
2521, 24fzfigd 10091 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (1...(𝑃𝐾)) ∈ Fin)
2622ad2antrr 477 . . . . . . . . 9 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → 𝑃 ∈ ℤ)
27 elfzelz 9693 . . . . . . . . . . 11 (𝑥 ∈ (1...(𝑃𝐾)) → 𝑥 ∈ ℤ)
2827adantl 273 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → 𝑥 ∈ ℤ)
29 0zd 8964 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → 0 ∈ ℤ)
3028, 29zsubcld 9076 . . . . . . . . 9 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (𝑥 − 0) ∈ ℤ)
31 zdvdsdc 11356 . . . . . . . . 9 ((𝑃 ∈ ℤ ∧ (𝑥 − 0) ∈ ℤ) → DECID 𝑃 ∥ (𝑥 − 0))
3226, 30, 31syl2anc 406 . . . . . . . 8 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → DECID 𝑃 ∥ (𝑥 − 0))
3332ralrimiva 2477 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ∀𝑥 ∈ (1...(𝑃𝐾))DECID 𝑃 ∥ (𝑥 − 0))
3425, 33ssfirab 6772 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ∈ Fin)
35 inrab 3312 . . . . . . 7 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))}
36 rpexp 11671 . . . . . . . . . . . . . . . . 17 ((𝑃 ∈ ℤ ∧ 𝑥 ∈ ℤ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
3722, 36syl3an1 1230 . . . . . . . . . . . . . . . 16 ((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
38373expa 1162 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ) ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
3938an32s 540 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (((𝑃𝐾) gcd 𝑥) = 1 ↔ (𝑃 gcd 𝑥) = 1))
40 simpr 109 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → 𝑥 ∈ ℤ)
4124adantr 272 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑃𝐾) ∈ ℤ)
42 gcdcom 11504 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ ℤ ∧ (𝑃𝐾) ∈ ℤ) → (𝑥 gcd (𝑃𝐾)) = ((𝑃𝐾) gcd 𝑥))
4340, 41, 42syl2anc 406 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑥 gcd (𝑃𝐾)) = ((𝑃𝐾) gcd 𝑥))
4443eqeq1d 2121 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ((𝑃𝐾) gcd 𝑥) = 1))
45 coprm 11662 . . . . . . . . . . . . . . 15 ((𝑃 ∈ ℙ ∧ 𝑥 ∈ ℤ) → (¬ 𝑃𝑥 ↔ (𝑃 gcd 𝑥) = 1))
4645adantlr 466 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (¬ 𝑃𝑥 ↔ (𝑃 gcd 𝑥) = 1))
4739, 44, 463bitr4d 219 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃𝑥))
48 zcn 8957 . . . . . . . . . . . . . . . . 17 (𝑥 ∈ ℤ → 𝑥 ∈ ℂ)
4948adantl 273 . . . . . . . . . . . . . . . 16 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → 𝑥 ∈ ℂ)
5049subid1d 7979 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑥 − 0) = 𝑥)
5150breq2d 3905 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (𝑃 ∥ (𝑥 − 0) ↔ 𝑃𝑥))
5251notbid 639 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → (¬ 𝑃 ∥ (𝑥 − 0) ↔ ¬ 𝑃𝑥))
5347, 52bitr4d 190 . . . . . . . . . . . 12 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ ℤ) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃 ∥ (𝑥 − 0)))
5427, 53sylan2 282 . . . . . . . . . . 11 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 ↔ ¬ 𝑃 ∥ (𝑥 − 0)))
5554biimpd 143 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 → ¬ 𝑃 ∥ (𝑥 − 0)))
56 imnan 662 . . . . . . . . . 10 (((𝑥 gcd (𝑃𝐾)) = 1 → ¬ 𝑃 ∥ (𝑥 − 0)) ↔ ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
5755, 56sylib 121 . . . . . . . . 9 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
5857ralrimiva 2477 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ∀𝑥 ∈ (1...(𝑃𝐾)) ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
59 rabeq0 3356 . . . . . . . 8 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))} = ∅ ↔ ∀𝑥 ∈ (1...(𝑃𝐾)) ¬ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0)))
6058, 59sylibr 133 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∧ 𝑃 ∥ (𝑥 − 0))} = ∅)
6135, 60syl5eq 2157 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ∅)
62 hashun 10438 . . . . . 6 (({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin ∧ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)} ∈ Fin ∧ ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∩ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ∅) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})))
6320, 34, 61, 62syl3anc 1197 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})))
6454biimprd 157 . . . . . . . . . . . 12 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (¬ 𝑃 ∥ (𝑥 − 0) → (𝑥 gcd (𝑃𝐾)) = 1))
65 con1dc 822 . . . . . . . . . . . 12 (DECID 𝑃 ∥ (𝑥 − 0) → ((¬ 𝑃 ∥ (𝑥 − 0) → (𝑥 gcd (𝑃𝐾)) = 1) → (¬ (𝑥 gcd (𝑃𝐾)) = 1 → 𝑃 ∥ (𝑥 − 0))))
6632, 64, 65sylc 62 . . . . . . . . . . 11 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (¬ (𝑥 gcd (𝑃𝐾)) = 1 → 𝑃 ∥ (𝑥 − 0)))
6724adantr 272 . . . . . . . . . . . . . . 15 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (𝑃𝐾) ∈ ℤ)
6828, 67gcdcld 11499 . . . . . . . . . . . . . 14 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (𝑥 gcd (𝑃𝐾)) ∈ ℕ0)
6968nn0zd 9069 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (𝑥 gcd (𝑃𝐾)) ∈ ℤ)
70 1zzd 8979 . . . . . . . . . . . . 13 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → 1 ∈ ℤ)
71 zdceq 9024 . . . . . . . . . . . . 13 (((𝑥 gcd (𝑃𝐾)) ∈ ℤ ∧ 1 ∈ ℤ) → DECID (𝑥 gcd (𝑃𝐾)) = 1)
7269, 70, 71syl2anc 406 . . . . . . . . . . . 12 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → DECID (𝑥 gcd (𝑃𝐾)) = 1)
73 dfordc 858 . . . . . . . . . . . 12 (DECID (𝑥 gcd (𝑃𝐾)) = 1 → (((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)) ↔ (¬ (𝑥 gcd (𝑃𝐾)) = 1 → 𝑃 ∥ (𝑥 − 0))))
7472, 73syl 14 . . . . . . . . . . 11 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → (((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)) ↔ (¬ (𝑥 gcd (𝑃𝐾)) = 1 → 𝑃 ∥ (𝑥 − 0))))
7566, 74mpbird 166 . . . . . . . . . 10 (((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) ∧ 𝑥 ∈ (1...(𝑃𝐾))) → ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
7675ralrimiva 2477 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ∀𝑥 ∈ (1...(𝑃𝐾))((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
77 rabid2 2579 . . . . . . . . 9 ((1...(𝑃𝐾)) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))} ↔ ∀𝑥 ∈ (1...(𝑃𝐾))((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0)))
7876, 77sylibr 133 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (1...(𝑃𝐾)) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))})
79 unrab 3311 . . . . . . . 8 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = {𝑥 ∈ (1...(𝑃𝐾)) ∣ ((𝑥 gcd (𝑃𝐾)) = 1 ∨ 𝑃 ∥ (𝑥 − 0))}
8078, 79syl6reqr 2164 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = (1...(𝑃𝐾)))
8180fveq2d 5377 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = (♯‘(1...(𝑃𝐾))))
824nnnn0d 8928 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℕ0)
83 hashfz1 10416 . . . . . . 7 ((𝑃𝐾) ∈ ℕ0 → (♯‘(1...(𝑃𝐾))) = (𝑃𝐾))
8482, 83syl 14 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘(1...(𝑃𝐾))) = (𝑃𝐾))
85 expm1t 10208 . . . . . . 7 ((𝑃 ∈ ℂ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) = ((𝑃↑(𝐾 − 1)) · 𝑃))
8611, 85sylan 279 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) = ((𝑃↑(𝐾 − 1)) · 𝑃))
8781, 84, 863eqtrd 2149 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∪ {𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((𝑃↑(𝐾 − 1)) · 𝑃))
88 hashcl 10414 . . . . . . . 8 ({𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1} ∈ Fin → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℕ0)
8920, 88syl 14 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℕ0)
9089nn0cnd 8930 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ∈ ℂ)
911adantr 272 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 ∈ ℕ)
92 nn0uz 9256 . . . . . . . . . . 11 0 = (ℤ‘0)
93 1m1e0 8693 . . . . . . . . . . . 12 (1 − 1) = 0
9493fveq2i 5376 . . . . . . . . . . 11 (ℤ‘(1 − 1)) = (ℤ‘0)
9592, 94eqtr4i 2136 . . . . . . . . . 10 0 = (ℤ‘(1 − 1))
9682, 95syl6eleq 2205 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ (ℤ‘(1 − 1)))
97 0zd 8964 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 0 ∈ ℤ)
9891, 21, 96, 97hashdvds 11736 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = ((⌊‘(((𝑃𝐾) − 0) / 𝑃)) − (⌊‘(((1 − 1) − 0) / 𝑃))))
994nncnd 8638 . . . . . . . . . . . . . 14 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃𝐾) ∈ ℂ)
10099subid1d 7979 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃𝐾) − 0) = (𝑃𝐾))
101100oveq1d 5741 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) − 0) / 𝑃) = ((𝑃𝐾) / 𝑃))
10291nnap0d 8670 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝑃 # 0)
103 nnz 8971 . . . . . . . . . . . . . 14 (𝐾 ∈ ℕ → 𝐾 ∈ ℤ)
104103adantl 273 . . . . . . . . . . . . 13 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → 𝐾 ∈ ℤ)
10512, 102, 104expm1apd 10321 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) = ((𝑃𝐾) / 𝑃))
106101, 105eqtr4d 2148 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃𝐾) − 0) / 𝑃) = (𝑃↑(𝐾 − 1)))
107106fveq2d 5377 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((𝑃𝐾) − 0) / 𝑃)) = (⌊‘(𝑃↑(𝐾 − 1))))
1089nnzd 9070 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (𝑃↑(𝐾 − 1)) ∈ ℤ)
109 flid 9944 . . . . . . . . . . 11 ((𝑃↑(𝐾 − 1)) ∈ ℤ → (⌊‘(𝑃↑(𝐾 − 1))) = (𝑃↑(𝐾 − 1)))
110108, 109syl 14 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(𝑃↑(𝐾 − 1))) = (𝑃↑(𝐾 − 1)))
111107, 110eqtrd 2145 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((𝑃𝐾) − 0) / 𝑃)) = (𝑃↑(𝐾 − 1)))
11293oveq1i 5736 . . . . . . . . . . . . . 14 ((1 − 1) − 0) = (0 − 0)
113 0m0e0 8736 . . . . . . . . . . . . . 14 (0 − 0) = 0
114112, 113eqtri 2133 . . . . . . . . . . . . 13 ((1 − 1) − 0) = 0
115114oveq1i 5736 . . . . . . . . . . . 12 (((1 − 1) − 0) / 𝑃) = (0 / 𝑃)
11612, 102div0apd 8454 . . . . . . . . . . . 12 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (0 / 𝑃) = 0)
117115, 116syl5eq 2157 . . . . . . . . . . 11 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((1 − 1) − 0) / 𝑃) = 0)
118117fveq2d 5377 . . . . . . . . . 10 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((1 − 1) − 0) / 𝑃)) = (⌊‘0))
119 0z 8963 . . . . . . . . . . 11 0 ∈ ℤ
120 flid 9944 . . . . . . . . . . 11 (0 ∈ ℤ → (⌊‘0) = 0)
121119, 120ax-mp 7 . . . . . . . . . 10 (⌊‘0) = 0
122118, 121syl6eq 2161 . . . . . . . . 9 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (⌊‘(((1 − 1) − 0) / 𝑃)) = 0)
123111, 122oveq12d 5744 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((⌊‘(((𝑃𝐾) − 0) / 𝑃)) − (⌊‘(((1 − 1) − 0) / 𝑃))) = ((𝑃↑(𝐾 − 1)) − 0))
12410subid1d 7979 . . . . . . . 8 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) − 0) = (𝑃↑(𝐾 − 1)))
12598, 123, 1243eqtrd 2149 . . . . . . 7 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)}) = (𝑃↑(𝐾 − 1)))
126125oveq2d 5742 . . . . . 6 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (𝑃↑(𝐾 − 1))))
12790, 10, 126comraddd 7836 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ 𝑃 ∥ (𝑥 − 0)})) = ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})))
12863, 87, 1273eqtr3rd 2154 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})) = ((𝑃↑(𝐾 − 1)) · 𝑃))
12910, 12mulcld 7704 . . . . 5 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((𝑃↑(𝐾 − 1)) · 𝑃) ∈ ℂ)
130129, 10, 90subaddd 8008 . . . 4 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → ((((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) ↔ ((𝑃↑(𝐾 − 1)) + (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1})) = ((𝑃↑(𝐾 − 1)) · 𝑃)))
131128, 130mpbird 166 . . 3 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (((𝑃↑(𝐾 − 1)) · 𝑃) − (𝑃↑(𝐾 − 1))) = (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}))
13216, 18, 1313eqtrrd 2150 . 2 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (♯‘{𝑥 ∈ (1...(𝑃𝐾)) ∣ (𝑥 gcd (𝑃𝐾)) = 1}) = ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)))
1336, 132eqtrd 2145 1 ((𝑃 ∈ ℙ ∧ 𝐾 ∈ ℕ) → (ϕ‘(𝑃𝐾)) = ((𝑃↑(𝐾 − 1)) · (𝑃 − 1)))
Colors of variables: wff set class
Syntax hints:  ¬ wn 3  wi 4  wa 103  wb 104  wo 680  DECID wdc 802   = wceq 1312  wcel 1461  wral 2388  {crab 2392  cun 3033  cin 3034  c0 3327   class class class wbr 3893  cfv 5079  (class class class)co 5726  Fincfn 6586  cc 7539  0cc0 7541  1c1 7542   + caddc 7544   · cmul 7546  cmin 7850   / cdiv 8339  cn 8624  0cn0 8875  cz 8952  cuz 9222  ...cfz 9677  cfl 9928  cexp 10179  chash 10408  cdvds 11335   gcd cgcd 11477  cprime 11628  ϕcphi 11725
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 586  ax-in2 587  ax-io 681  ax-5 1404  ax-7 1405  ax-gen 1406  ax-ie1 1450  ax-ie2 1451  ax-8 1463  ax-10 1464  ax-11 1465  ax-i12 1466  ax-bndl 1467  ax-4 1468  ax-13 1472  ax-14 1473  ax-17 1487  ax-i9 1491  ax-ial 1495  ax-i5r 1496  ax-ext 2095  ax-coll 4001  ax-sep 4004  ax-nul 4012  ax-pow 4056  ax-pr 4089  ax-un 4313  ax-setind 4410  ax-iinf 4460  ax-cnex 7630  ax-resscn 7631  ax-1cn 7632  ax-1re 7633  ax-icn 7634  ax-addcl 7635  ax-addrcl 7636  ax-mulcl 7637  ax-mulrcl 7638  ax-addcom 7639  ax-mulcom 7640  ax-addass 7641  ax-mulass 7642  ax-distr 7643  ax-i2m1 7644  ax-0lt1 7645  ax-1rid 7646  ax-0id 7647  ax-rnegex 7648  ax-precex 7649  ax-cnre 7650  ax-pre-ltirr 7651  ax-pre-ltwlin 7652  ax-pre-lttrn 7653  ax-pre-apti 7654  ax-pre-ltadd 7655  ax-pre-mulgt0 7656  ax-pre-mulext 7657  ax-arch 7658  ax-caucvg 7659
This theorem depends on definitions:  df-bi 116  df-stab 799  df-dc 803  df-3or 944  df-3an 945  df-tru 1315  df-fal 1318  df-nf 1418  df-sb 1717  df-eu 1976  df-mo 1977  df-clab 2100  df-cleq 2106  df-clel 2109  df-nfc 2242  df-ne 2281  df-nel 2376  df-ral 2393  df-rex 2394  df-reu 2395  df-rmo 2396  df-rab 2397  df-v 2657  df-sbc 2877  df-csb 2970  df-dif 3037  df-un 3039  df-in 3041  df-ss 3048  df-nul 3328  df-if 3439  df-pw 3476  df-sn 3497  df-pr 3498  df-op 3500  df-uni 3701  df-int 3736  df-iun 3779  df-br 3894  df-opab 3948  df-mpt 3949  df-tr 3985  df-id 4173  df-po 4176  df-iso 4177  df-iord 4246  df-on 4248  df-ilim 4249  df-suc 4251  df-iom 4463  df-xp 4503  df-rel 4504  df-cnv 4505  df-co 4506  df-dm 4507  df-rn 4508  df-res 4509  df-ima 4510  df-iota 5044  df-fun 5081  df-fn 5082  df-f 5083  df-f1 5084  df-fo 5085  df-f1o 5086  df-fv 5087  df-riota 5682  df-ov 5729  df-oprab 5730  df-mpo 5731  df-1st 5990  df-2nd 5991  df-recs 6154  df-irdg 6219  df-frec 6240  df-1o 6265  df-2o 6266  df-oadd 6269  df-er 6381  df-en 6587  df-dom 6588  df-fin 6589  df-sup 6821  df-pnf 7720  df-mnf 7721  df-xr 7722  df-ltxr 7723  df-le 7724  df-sub 7852  df-neg 7853  df-reap 8249  df-ap 8256  df-div 8340  df-inn 8625  df-2 8683  df-3 8684  df-4 8685  df-n0 8876  df-z 8953  df-uz 9223  df-q 9308  df-rp 9338  df-fz 9678  df-fzo 9807  df-fl 9930  df-mod 9983  df-seqfrec 10106  df-exp 10180  df-ihash 10409  df-cj 10501  df-re 10502  df-im 10503  df-rsqrt 10656  df-abs 10657  df-dvds 11336  df-gcd 11478  df-prm 11629  df-phi 11726
This theorem is referenced by:  phiprm  11738
  Copyright terms: Public domain W3C validator