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

Theorem lgsdchrval 27285
Description: The Legendre symbol function 𝑋(𝑚) = (𝑚 /L 𝑁), where 𝑁 is an odd positive number, is a Dirichlet character modulo 𝑁. (Contributed by Mario Carneiro, 28-Apr-2016.)
Hypotheses
Ref Expression
lgsdchr.g 𝐺 = (DChr‘𝑁)
lgsdchr.z 𝑍 = (ℤ/nℤ‘𝑁)
lgsdchr.d 𝐷 = (Base‘𝐺)
lgsdchr.b 𝐵 = (Base‘𝑍)
lgsdchr.l 𝐿 = (ℤRHom‘𝑍)
lgsdchr.x 𝑋 = (𝑦𝐵 ↦ (℩𝑚 ∈ ℤ (𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
Assertion
Ref Expression
lgsdchrval (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (𝑋‘(𝐿𝐴)) = (𝐴 /L 𝑁))
Distinct variable groups:   𝑦,𝐵   ,𝑚,𝑦,𝐿   ,𝑁,𝑚,𝑦   𝑦,𝑋   𝐴,,𝑚,𝑦   𝑦,𝑍
Allowed substitution hints:   𝐵(,𝑚)   𝐷(𝑦,,𝑚)   𝐺(𝑦,,𝑚)   𝑋(,𝑚)   𝑍(,𝑚)

Proof of Theorem lgsdchrval
StepHypRef Expression
1 nnnn0 12380 . . . . . 6 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
21adantr 480 . . . . 5 ((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) → 𝑁 ∈ ℕ0)
3 lgsdchr.z . . . . . 6 𝑍 = (ℤ/nℤ‘𝑁)
4 lgsdchr.b . . . . . 6 𝐵 = (Base‘𝑍)
5 lgsdchr.l . . . . . 6 𝐿 = (ℤRHom‘𝑍)
63, 4, 5znzrhfo 21477 . . . . 5 (𝑁 ∈ ℕ0𝐿:ℤ–onto𝐵)
7 fof 6731 . . . . 5 (𝐿:ℤ–onto𝐵𝐿:ℤ⟶𝐵)
82, 6, 73syl 18 . . . 4 ((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) → 𝐿:ℤ⟶𝐵)
98ffvelcdmda 7012 . . 3 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (𝐿𝐴) ∈ 𝐵)
10 eqeq1 2734 . . . . . . 7 (𝑦 = (𝐿𝐴) → (𝑦 = (𝐿𝑚) ↔ (𝐿𝐴) = (𝐿𝑚)))
1110anbi1d 631 . . . . . 6 (𝑦 = (𝐿𝐴) → ((𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) ↔ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
1211rexbidv 3154 . . . . 5 (𝑦 = (𝐿𝐴) → (∃𝑚 ∈ ℤ (𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) ↔ ∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
1312iotabidv 6461 . . . 4 (𝑦 = (𝐿𝐴) → (℩𝑚 ∈ ℤ (𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))) = (℩𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
14 lgsdchr.x . . . 4 𝑋 = (𝑦𝐵 ↦ (℩𝑚 ∈ ℤ (𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
15 iotaex 6453 . . . 4 (℩𝑚 ∈ ℤ (𝑦 = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))) ∈ V
1613, 14, 15fvmpt3i 6929 . . 3 ((𝐿𝐴) ∈ 𝐵 → (𝑋‘(𝐿𝐴)) = (℩𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
179, 16syl 17 . 2 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (𝑋‘(𝐿𝐴)) = (℩𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
18 ovex 7374 . . 3 (𝐴 /L 𝑁) ∈ V
19 simprr 772 . . . . . . . . . . . . . . 15 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → (𝐿𝐴) = (𝐿𝑚))
20 simplll 774 . . . . . . . . . . . . . . . . 17 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → 𝑁 ∈ ℕ)
2120, 1syl 17 . . . . . . . . . . . . . . . 16 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → 𝑁 ∈ ℕ0)
22 simplr 768 . . . . . . . . . . . . . . . 16 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → 𝐴 ∈ ℤ)
23 simprl 770 . . . . . . . . . . . . . . . 16 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → 𝑚 ∈ ℤ)
243, 5zndvds 21479 . . . . . . . . . . . . . . . 16 ((𝑁 ∈ ℕ0𝐴 ∈ ℤ ∧ 𝑚 ∈ ℤ) → ((𝐿𝐴) = (𝐿𝑚) ↔ 𝑁 ∥ (𝐴𝑚)))
2521, 22, 23, 24syl3anc 1373 . . . . . . . . . . . . . . 15 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ((𝐿𝐴) = (𝐿𝑚) ↔ 𝑁 ∥ (𝐴𝑚)))
2619, 25mpbid 232 . . . . . . . . . . . . . 14 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → 𝑁 ∥ (𝐴𝑚))
27 moddvds 16166 . . . . . . . . . . . . . . 15 ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ 𝑚 ∈ ℤ) → ((𝐴 mod 𝑁) = (𝑚 mod 𝑁) ↔ 𝑁 ∥ (𝐴𝑚)))
2820, 22, 23, 27syl3anc 1373 . . . . . . . . . . . . . 14 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ((𝐴 mod 𝑁) = (𝑚 mod 𝑁) ↔ 𝑁 ∥ (𝐴𝑚)))
2926, 28mpbird 257 . . . . . . . . . . . . 13 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → (𝐴 mod 𝑁) = (𝑚 mod 𝑁))
3029oveq1d 7356 . . . . . . . . . . . 12 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ((𝐴 mod 𝑁) /L 𝑁) = ((𝑚 mod 𝑁) /L 𝑁))
31 simpllr 775 . . . . . . . . . . . . 13 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ¬ 2 ∥ 𝑁)
32 lgsmod 27254 . . . . . . . . . . . . 13 ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) → ((𝐴 mod 𝑁) /L 𝑁) = (𝐴 /L 𝑁))
3322, 20, 31, 32syl3anc 1373 . . . . . . . . . . . 12 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ((𝐴 mod 𝑁) /L 𝑁) = (𝐴 /L 𝑁))
34 lgsmod 27254 . . . . . . . . . . . . 13 ((𝑚 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) → ((𝑚 mod 𝑁) /L 𝑁) = (𝑚 /L 𝑁))
3523, 20, 31, 34syl3anc 1373 . . . . . . . . . . . 12 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ((𝑚 mod 𝑁) /L 𝑁) = (𝑚 /L 𝑁))
3630, 33, 353eqtr3d 2773 . . . . . . . . . . 11 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → (𝐴 /L 𝑁) = (𝑚 /L 𝑁))
3736eqeq2d 2741 . . . . . . . . . 10 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ( = (𝐴 /L 𝑁) ↔ = (𝑚 /L 𝑁)))
3837biimprd 248 . . . . . . . . 9 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝑚 ∈ ℤ ∧ (𝐿𝐴) = (𝐿𝑚))) → ( = (𝑚 /L 𝑁) → = (𝐴 /L 𝑁)))
3938anassrs 467 . . . . . . . 8 (((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ 𝑚 ∈ ℤ) ∧ (𝐿𝐴) = (𝐿𝑚)) → ( = (𝑚 /L 𝑁) → = (𝐴 /L 𝑁)))
4039expimpd 453 . . . . . . 7 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ 𝑚 ∈ ℤ) → (((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) → = (𝐴 /L 𝑁)))
4140rexlimdva 3131 . . . . . 6 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) → = (𝐴 /L 𝑁)))
42 fveq2 6817 . . . . . . . . . . . 12 (𝑚 = 𝐴 → (𝐿𝑚) = (𝐿𝐴))
4342eqcomd 2736 . . . . . . . . . . 11 (𝑚 = 𝐴 → (𝐿𝐴) = (𝐿𝑚))
4443biantrurd 532 . . . . . . . . . 10 (𝑚 = 𝐴 → ( = (𝑚 /L 𝑁) ↔ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
45 oveq1 7348 . . . . . . . . . . 11 (𝑚 = 𝐴 → (𝑚 /L 𝑁) = (𝐴 /L 𝑁))
4645eqeq2d 2741 . . . . . . . . . 10 (𝑚 = 𝐴 → ( = (𝑚 /L 𝑁) ↔ = (𝐴 /L 𝑁)))
4744, 46bitr3d 281 . . . . . . . . 9 (𝑚 = 𝐴 → (((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) ↔ = (𝐴 /L 𝑁)))
4847rspcev 3575 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ = (𝐴 /L 𝑁)) → ∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)))
4948ex 412 . . . . . . 7 (𝐴 ∈ ℤ → ( = (𝐴 /L 𝑁) → ∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
5049adantl 481 . . . . . 6 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → ( = (𝐴 /L 𝑁) → ∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))))
5141, 50impbid 212 . . . . 5 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) ↔ = (𝐴 /L 𝑁)))
5251adantr 480 . . . 4 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝐴 /L 𝑁) ∈ V) → (∃𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁)) ↔ = (𝐴 /L 𝑁)))
5352iota5 6460 . . 3 ((((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) ∧ (𝐴 /L 𝑁) ∈ V) → (℩𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))) = (𝐴 /L 𝑁))
5418, 53mpan2 691 . 2 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (℩𝑚 ∈ ℤ ((𝐿𝐴) = (𝐿𝑚) ∧ = (𝑚 /L 𝑁))) = (𝐴 /L 𝑁))
5517, 54eqtrd 2765 1 (((𝑁 ∈ ℕ ∧ ¬ 2 ∥ 𝑁) ∧ 𝐴 ∈ ℤ) → (𝑋‘(𝐿𝐴)) = (𝐴 /L 𝑁))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 206  wa 395   = wceq 1541  wcel 2110  wrex 3054  Vcvv 3434   class class class wbr 5089  cmpt 5170  cio 6431  wf 6473  ontowfo 6475  cfv 6477  (class class class)co 7341  cmin 11336  cn 12117  2c2 12172  0cn0 12373  cz 12460   mod cmo 13765  cdvds 16155  Basecbs 17112  ℤRHomczrh 21429  ℤ/nczn 21432  DChrcdchr 27163   /L clgs 27225
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 1968  ax-7 2009  ax-8 2112  ax-9 2120  ax-10 2143  ax-11 2159  ax-12 2179  ax-ext 2702  ax-rep 5215  ax-sep 5232  ax-nul 5242  ax-pow 5301  ax-pr 5368  ax-un 7663  ax-cnex 11054  ax-resscn 11055  ax-1cn 11056  ax-icn 11057  ax-addcl 11058  ax-addrcl 11059  ax-mulcl 11060  ax-mulrcl 11061  ax-mulcom 11062  ax-addass 11063  ax-mulass 11064  ax-distr 11065  ax-i2m1 11066  ax-1ne0 11067  ax-1rid 11068  ax-rnegex 11069  ax-rrecex 11070  ax-cnre 11071  ax-pre-lttri 11072  ax-pre-lttrn 11073  ax-pre-ltadd 11074  ax-pre-mulgt0 11075  ax-pre-sup 11076  ax-addf 11077  ax-mulf 11078
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2067  df-mo 2534  df-eu 2563  df-clab 2709  df-cleq 2722  df-clel 2804  df-nfc 2879  df-ne 2927  df-nel 3031  df-ral 3046  df-rex 3055  df-rmo 3344  df-reu 3345  df-rab 3394  df-v 3436  df-sbc 3740  df-csb 3849  df-dif 3903  df-un 3905  df-in 3907  df-ss 3917  df-pss 3920  df-nul 4282  df-if 4474  df-pw 4550  df-sn 4575  df-pr 4577  df-tp 4579  df-op 4581  df-uni 4858  df-int 4896  df-iun 4941  df-br 5090  df-opab 5152  df-mpt 5171  df-tr 5197  df-id 5509  df-eprel 5514  df-po 5522  df-so 5523  df-fr 5567  df-we 5569  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-pred 6244  df-ord 6305  df-on 6306  df-lim 6307  df-suc 6308  df-iota 6433  df-fun 6479  df-fn 6480  df-f 6481  df-f1 6482  df-fo 6483  df-f1o 6484  df-fv 6485  df-riota 7298  df-ov 7344  df-oprab 7345  df-mpo 7346  df-om 7792  df-1st 7916  df-2nd 7917  df-tpos 8151  df-frecs 8206  df-wrecs 8237  df-recs 8286  df-rdg 8324  df-1o 8380  df-2o 8381  df-oadd 8384  df-er 8617  df-ec 8619  df-qs 8623  df-map 8747  df-en 8865  df-dom 8866  df-sdom 8867  df-fin 8868  df-sup 9321  df-inf 9322  df-dju 9786  df-card 9824  df-pnf 11140  df-mnf 11141  df-xr 11142  df-ltxr 11143  df-le 11144  df-sub 11338  df-neg 11339  df-div 11767  df-nn 12118  df-2 12180  df-3 12181  df-4 12182  df-5 12183  df-6 12184  df-7 12185  df-8 12186  df-9 12187  df-n0 12374  df-xnn0 12447  df-z 12461  df-dec 12581  df-uz 12725  df-q 12839  df-rp 12883  df-fz 13400  df-fzo 13547  df-fl 13688  df-mod 13766  df-seq 13901  df-exp 13961  df-hash 14230  df-cj 14998  df-re 14999  df-im 15000  df-sqrt 15134  df-abs 15135  df-dvds 16156  df-gcd 16398  df-prm 16575  df-phi 16669  df-pc 16741  df-struct 17050  df-sets 17067  df-slot 17085  df-ndx 17097  df-base 17113  df-ress 17134  df-plusg 17166  df-mulr 17167  df-starv 17168  df-sca 17169  df-vsca 17170  df-ip 17171  df-tset 17172  df-ple 17173  df-ds 17175  df-unif 17176  df-0g 17337  df-imas 17404  df-qus 17405  df-mgm 18540  df-sgrp 18619  df-mnd 18635  df-mhm 18683  df-grp 18841  df-minusg 18842  df-sbg 18843  df-mulg 18973  df-subg 19028  df-nsg 19029  df-eqg 19030  df-ghm 19118  df-cmn 19687  df-abl 19688  df-mgp 20052  df-rng 20064  df-ur 20093  df-ring 20146  df-cring 20147  df-oppr 20248  df-dvdsr 20268  df-rhm 20383  df-subrng 20454  df-subrg 20478  df-lmod 20788  df-lss 20858  df-lsp 20898  df-sra 21100  df-rgmod 21101  df-lidl 21138  df-rsp 21139  df-2idl 21180  df-cnfld 21285  df-zring 21377  df-zrh 21433  df-zn 21436  df-lgs 27226
This theorem is referenced by:  lgsdchr  27286
  Copyright terms: Public domain W3C validator