Users' Mathboxes Mathbox for Alexander van der Vekens < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  fpprmod Structured version   Visualization version   GIF version

Theorem fpprmod 45136
Description: The set of Fermat pseudoprimes to the base 𝑁, expressed by a modulo operation instead of the divisibility relation. (Contributed by AV, 30-May-2023.)
Assertion
Ref Expression
fpprmod (𝑁 ∈ ℕ → ( FPPr ‘𝑁) = {𝑥 ∈ (ℤ‘4) ∣ (𝑥 ∉ ℙ ∧ ((𝑁↑(𝑥 − 1)) mod 𝑥) = 1)})
Distinct variable group:   𝑥,𝑁

Proof of Theorem fpprmod
StepHypRef Expression
1 fppr 45135 . 2 (𝑁 ∈ ℕ → ( FPPr ‘𝑁) = {𝑥 ∈ (ℤ‘4) ∣ (𝑥 ∉ ℙ ∧ 𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1))})
2 eluz4eluz2 12614 . . . . . 6 (𝑥 ∈ (ℤ‘4) → 𝑥 ∈ (ℤ‘2))
3 nnz 12331 . . . . . . 7 (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
4 eluz4nn 12615 . . . . . . . 8 (𝑥 ∈ (ℤ‘4) → 𝑥 ∈ ℕ)
5 nnm1nn0 12263 . . . . . . . 8 (𝑥 ∈ ℕ → (𝑥 − 1) ∈ ℕ0)
64, 5syl 17 . . . . . . 7 (𝑥 ∈ (ℤ‘4) → (𝑥 − 1) ∈ ℕ0)
7 zexpcl 13786 . . . . . . 7 ((𝑁 ∈ ℤ ∧ (𝑥 − 1) ∈ ℕ0) → (𝑁↑(𝑥 − 1)) ∈ ℤ)
83, 6, 7syl2an 596 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (ℤ‘4)) → (𝑁↑(𝑥 − 1)) ∈ ℤ)
9 modm1div 15964 . . . . . 6 ((𝑥 ∈ (ℤ‘2) ∧ (𝑁↑(𝑥 − 1)) ∈ ℤ) → (((𝑁↑(𝑥 − 1)) mod 𝑥) = 1 ↔ 𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1)))
102, 8, 9syl2an2 683 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (ℤ‘4)) → (((𝑁↑(𝑥 − 1)) mod 𝑥) = 1 ↔ 𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1)))
1110bicomd 222 . . . 4 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (ℤ‘4)) → (𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1) ↔ ((𝑁↑(𝑥 − 1)) mod 𝑥) = 1))
1211anbi2d 629 . . 3 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (ℤ‘4)) → ((𝑥 ∉ ℙ ∧ 𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1)) ↔ (𝑥 ∉ ℙ ∧ ((𝑁↑(𝑥 − 1)) mod 𝑥) = 1)))
1312rabbidva 3412 . 2 (𝑁 ∈ ℕ → {𝑥 ∈ (ℤ‘4) ∣ (𝑥 ∉ ℙ ∧ 𝑥 ∥ ((𝑁↑(𝑥 − 1)) − 1))} = {𝑥 ∈ (ℤ‘4) ∣ (𝑥 ∉ ℙ ∧ ((𝑁↑(𝑥 − 1)) mod 𝑥) = 1)})
141, 13eqtrd 2778 1 (𝑁 ∈ ℕ → ( FPPr ‘𝑁) = {𝑥 ∈ (ℤ‘4) ∣ (𝑥 ∉ ℙ ∧ ((𝑁↑(𝑥 − 1)) mod 𝑥) = 1)})
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 396   = wceq 1539  wcel 2106  wnel 3049  {crab 3068   class class class wbr 5075  cfv 6428  (class class class)co 7269  1c1 10861  cmin 11194  cn 11962  2c2 12017  4c4 12019  0cn0 12222  cz 12308  cuz 12571   mod cmo 13578  cexp 13771  cdvds 15952  cprime 16365   FPPr cfppr 45133
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 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2709  ax-sep 5223  ax-nul 5230  ax-pow 5288  ax-pr 5352  ax-un 7580  ax-cnex 10916  ax-resscn 10917  ax-1cn 10918  ax-icn 10919  ax-addcl 10920  ax-addrcl 10921  ax-mulcl 10922  ax-mulrcl 10923  ax-mulcom 10924  ax-addass 10925  ax-mulass 10926  ax-distr 10927  ax-i2m1 10928  ax-1ne0 10929  ax-1rid 10930  ax-rnegex 10931  ax-rrecex 10932  ax-cnre 10933  ax-pre-lttri 10934  ax-pre-lttrn 10935  ax-pre-ltadd 10936  ax-pre-mulgt0 10937  ax-pre-sup 10938
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1783  df-nf 1787  df-sb 2068  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2816  df-nfc 2889  df-ne 2944  df-nel 3050  df-ral 3069  df-rex 3070  df-rmo 3071  df-reu 3072  df-rab 3073  df-v 3433  df-sbc 3718  df-csb 3834  df-dif 3891  df-un 3893  df-in 3895  df-ss 3905  df-pss 3907  df-nul 4259  df-if 4462  df-pw 4537  df-sn 4564  df-pr 4566  df-op 4570  df-uni 4842  df-iun 4928  df-br 5076  df-opab 5138  df-mpt 5159  df-tr 5193  df-id 5486  df-eprel 5492  df-po 5500  df-so 5501  df-fr 5541  df-we 5543  df-xp 5592  df-rel 5593  df-cnv 5594  df-co 5595  df-dm 5596  df-rn 5597  df-res 5598  df-ima 5599  df-pred 6197  df-ord 6264  df-on 6265  df-lim 6266  df-suc 6267  df-iota 6386  df-fun 6430  df-fn 6431  df-f 6432  df-f1 6433  df-fo 6434  df-f1o 6435  df-fv 6436  df-riota 7226  df-ov 7272  df-oprab 7273  df-mpo 7274  df-om 7705  df-2nd 7823  df-frecs 8086  df-wrecs 8117  df-recs 8191  df-rdg 8230  df-er 8487  df-en 8723  df-dom 8724  df-sdom 8725  df-sup 9190  df-inf 9191  df-pnf 11000  df-mnf 11001  df-xr 11002  df-ltxr 11003  df-le 11004  df-sub 11196  df-neg 11197  df-div 11622  df-nn 11963  df-2 12025  df-3 12026  df-4 12027  df-n0 12223  df-z 12309  df-uz 12572  df-rp 12720  df-fl 13501  df-mod 13579  df-seq 13711  df-exp 13772  df-dvds 15953  df-fppr 45134
This theorem is referenced by:  fpprel  45137
  Copyright terms: Public domain W3C validator