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

Theorem gausslemma2d 15113
Description: Gauss' Lemma (see also theorem 9.6 in [ApostolNT] p. 182) for integer 2: Let p be an odd prime. Let S = {2, 4, 6, ..., p - 1}. Let n denote the number of elements of S whose least positive residue modulo p is greater than p/2. Then ( 2 | p ) = (-1)^n. (Contributed by AV, 14-Jul-2021.)
Hypotheses
Ref Expression
gausslemma2d.p (𝜑𝑃 ∈ (ℙ ∖ {2}))
gausslemma2d.h 𝐻 = ((𝑃 − 1) / 2)
gausslemma2d.r 𝑅 = (𝑥 ∈ (1...𝐻) ↦ if((𝑥 · 2) < (𝑃 / 2), (𝑥 · 2), (𝑃 − (𝑥 · 2))))
gausslemma2d.m 𝑀 = (⌊‘(𝑃 / 4))
gausslemma2d.n 𝑁 = (𝐻𝑀)
Assertion
Ref Expression
gausslemma2d (𝜑 → (2 /L 𝑃) = (-1↑𝑁))
Distinct variable groups:   𝑥,𝐻   𝑥,𝑃   𝜑,𝑥   𝑥,𝑀
Allowed substitution hints:   𝑅(𝑥)   𝑁(𝑥)

Proof of Theorem gausslemma2d
StepHypRef Expression
1 gausslemma2d.p . . 3 (𝜑𝑃 ∈ (ℙ ∖ {2}))
2 gausslemma2d.h . . 3 𝐻 = ((𝑃 − 1) / 2)
3 gausslemma2d.r . . 3 𝑅 = (𝑥 ∈ (1...𝐻) ↦ if((𝑥 · 2) < (𝑃 / 2), (𝑥 · 2), (𝑃 − (𝑥 · 2))))
4 gausslemma2d.m . . 3 𝑀 = (⌊‘(𝑃 / 4))
5 gausslemma2d.n . . 3 𝑁 = (𝐻𝑀)
61, 2, 3, 4, 5gausslemma2dlem7 15112 . 2 (𝜑 → (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = 1)
71gausslemma2dlem0a 15093 . . . . . . 7 (𝜑𝑃 ∈ ℕ)
8 nnq 9684 . . . . . . 7 (𝑃 ∈ ℕ → 𝑃 ∈ ℚ)
97, 8syl 14 . . . . . 6 (𝜑𝑃 ∈ ℚ)
10 eldifi 3277 . . . . . . 7 (𝑃 ∈ (ℙ ∖ {2}) → 𝑃 ∈ ℙ)
11 prmgt1 12244 . . . . . . 7 (𝑃 ∈ ℙ → 1 < 𝑃)
121, 10, 113syl 17 . . . . . 6 (𝜑 → 1 < 𝑃)
13 q1mod 10413 . . . . . 6 ((𝑃 ∈ ℚ ∧ 1 < 𝑃) → (1 mod 𝑃) = 1)
149, 12, 13syl2anc 411 . . . . 5 (𝜑 → (1 mod 𝑃) = 1)
1514eqcomd 2195 . . . 4 (𝜑 → 1 = (1 mod 𝑃))
1615eqeq2d 2201 . . 3 (𝜑 → ((((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = 1 ↔ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)))
17 neg1z 9335 . . . . . . . . . 10 -1 ∈ ℤ
181, 4, 2, 5gausslemma2dlem0h 15100 . . . . . . . . . 10 (𝜑𝑁 ∈ ℕ0)
19 zexpcl 10599 . . . . . . . . . 10 ((-1 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → (-1↑𝑁) ∈ ℤ)
2017, 18, 19sylancr 414 . . . . . . . . 9 (𝜑 → (-1↑𝑁) ∈ ℤ)
21 2nn 9129 . . . . . . . . . . . 12 2 ∈ ℕ
2221a1i 9 . . . . . . . . . . 11 (𝜑 → 2 ∈ ℕ)
231, 2gausslemma2dlem0b 15094 . . . . . . . . . . . 12 (𝜑𝐻 ∈ ℕ)
2423nnnn0d 9279 . . . . . . . . . . 11 (𝜑𝐻 ∈ ℕ0)
2522, 24nnexpcld 10740 . . . . . . . . . 10 (𝜑 → (2↑𝐻) ∈ ℕ)
2625nnzd 9424 . . . . . . . . 9 (𝜑 → (2↑𝐻) ∈ ℤ)
2720, 26zmulcld 9431 . . . . . . . 8 (𝜑 → ((-1↑𝑁) · (2↑𝐻)) ∈ ℤ)
28 zq 9677 . . . . . . . 8 (((-1↑𝑁) · (2↑𝐻)) ∈ ℤ → ((-1↑𝑁) · (2↑𝐻)) ∈ ℚ)
2927, 28syl 14 . . . . . . 7 (𝜑 → ((-1↑𝑁) · (2↑𝐻)) ∈ ℚ)
3029adantr 276 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → ((-1↑𝑁) · (2↑𝐻)) ∈ ℚ)
31 1z 9329 . . . . . . 7 1 ∈ ℤ
32 zq 9677 . . . . . . 7 (1 ∈ ℤ → 1 ∈ ℚ)
3331, 32mp1i 10 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → 1 ∈ ℚ)
3420adantr 276 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → (-1↑𝑁) ∈ ℤ)
359adantr 276 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → 𝑃 ∈ ℚ)
367nngt0d 9012 . . . . . . 7 (𝜑 → 0 < 𝑃)
3736adantr 276 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → 0 < 𝑃)
38 simpr 110 . . . . . 6 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃))
3930, 33, 34, 35, 37, 38modqmul1 10434 . . . . 5 ((𝜑 ∧ (((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃)) → ((((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) mod 𝑃) = ((1 · (-1↑𝑁)) mod 𝑃))
4039ex 115 . . . 4 (𝜑 → ((((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃) → ((((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) mod 𝑃) = ((1 · (-1↑𝑁)) mod 𝑃)))
4120zcnd 9426 . . . . . . . . 9 (𝜑 → (-1↑𝑁) ∈ ℂ)
4225nncnd 8982 . . . . . . . . 9 (𝜑 → (2↑𝐻) ∈ ℂ)
4341, 42, 41mul32d 8158 . . . . . . . 8 (𝜑 → (((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) = (((-1↑𝑁) · (-1↑𝑁)) · (2↑𝐻)))
4418nn0cnd 9281 . . . . . . . . . . . . 13 (𝜑𝑁 ∈ ℂ)
45442timesd 9211 . . . . . . . . . . . 12 (𝜑 → (2 · 𝑁) = (𝑁 + 𝑁))
4645eqcomd 2195 . . . . . . . . . . 11 (𝜑 → (𝑁 + 𝑁) = (2 · 𝑁))
4746oveq2d 5922 . . . . . . . . . 10 (𝜑 → (-1↑(𝑁 + 𝑁)) = (-1↑(2 · 𝑁)))
48 neg1cn 9073 . . . . . . . . . . . 12 -1 ∈ ℂ
4948a1i 9 . . . . . . . . . . 11 (𝜑 → -1 ∈ ℂ)
5049, 18, 18expaddd 10720 . . . . . . . . . 10 (𝜑 → (-1↑(𝑁 + 𝑁)) = ((-1↑𝑁) · (-1↑𝑁)))
5118nn0zd 9423 . . . . . . . . . . 11 (𝜑𝑁 ∈ ℤ)
52 m1expeven 10631 . . . . . . . . . . 11 (𝑁 ∈ ℤ → (-1↑(2 · 𝑁)) = 1)
5351, 52syl 14 . . . . . . . . . 10 (𝜑 → (-1↑(2 · 𝑁)) = 1)
5447, 50, 533eqtr3d 2230 . . . . . . . . 9 (𝜑 → ((-1↑𝑁) · (-1↑𝑁)) = 1)
5554oveq1d 5921 . . . . . . . 8 (𝜑 → (((-1↑𝑁) · (-1↑𝑁)) · (2↑𝐻)) = (1 · (2↑𝐻)))
5642mullidd 8023 . . . . . . . 8 (𝜑 → (1 · (2↑𝐻)) = (2↑𝐻))
5743, 55, 563eqtrd 2226 . . . . . . 7 (𝜑 → (((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) = (2↑𝐻))
5857oveq1d 5921 . . . . . 6 (𝜑 → ((((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) mod 𝑃) = ((2↑𝐻) mod 𝑃))
5941mullidd 8023 . . . . . . 7 (𝜑 → (1 · (-1↑𝑁)) = (-1↑𝑁))
6059oveq1d 5921 . . . . . 6 (𝜑 → ((1 · (-1↑𝑁)) mod 𝑃) = ((-1↑𝑁) mod 𝑃))
6158, 60eqeq12d 2204 . . . . 5 (𝜑 → (((((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) mod 𝑃) = ((1 · (-1↑𝑁)) mod 𝑃) ↔ ((2↑𝐻) mod 𝑃) = ((-1↑𝑁) mod 𝑃)))
622oveq2i 5917 . . . . . . . 8 (2↑𝐻) = (2↑((𝑃 − 1) / 2))
6362oveq1i 5916 . . . . . . 7 ((2↑𝐻) mod 𝑃) = ((2↑((𝑃 − 1) / 2)) mod 𝑃)
6463eqeq1i 2197 . . . . . 6 (((2↑𝐻) mod 𝑃) = ((-1↑𝑁) mod 𝑃) ↔ ((2↑((𝑃 − 1) / 2)) mod 𝑃) = ((-1↑𝑁) mod 𝑃))
65 2z 9331 . . . . . . . . . 10 2 ∈ ℤ
66 lgsvalmod 15063 . . . . . . . . . 10 ((2 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → ((2 /L 𝑃) mod 𝑃) = ((2↑((𝑃 − 1) / 2)) mod 𝑃))
6765, 1, 66sylancr 414 . . . . . . . . 9 (𝜑 → ((2 /L 𝑃) mod 𝑃) = ((2↑((𝑃 − 1) / 2)) mod 𝑃))
6867eqcomd 2195 . . . . . . . 8 (𝜑 → ((2↑((𝑃 − 1) / 2)) mod 𝑃) = ((2 /L 𝑃) mod 𝑃))
6968eqeq1d 2198 . . . . . . 7 (𝜑 → (((2↑((𝑃 − 1) / 2)) mod 𝑃) = ((-1↑𝑁) mod 𝑃) ↔ ((2 /L 𝑃) mod 𝑃) = ((-1↑𝑁) mod 𝑃)))
701, 4, 2, 5gausslemma2dlem0i 15101 . . . . . . 7 (𝜑 → (((2 /L 𝑃) mod 𝑃) = ((-1↑𝑁) mod 𝑃) → (2 /L 𝑃) = (-1↑𝑁)))
7169, 70sylbid 150 . . . . . 6 (𝜑 → (((2↑((𝑃 − 1) / 2)) mod 𝑃) = ((-1↑𝑁) mod 𝑃) → (2 /L 𝑃) = (-1↑𝑁)))
7264, 71biimtrid 152 . . . . 5 (𝜑 → (((2↑𝐻) mod 𝑃) = ((-1↑𝑁) mod 𝑃) → (2 /L 𝑃) = (-1↑𝑁)))
7361, 72sylbid 150 . . . 4 (𝜑 → (((((-1↑𝑁) · (2↑𝐻)) · (-1↑𝑁)) mod 𝑃) = ((1 · (-1↑𝑁)) mod 𝑃) → (2 /L 𝑃) = (-1↑𝑁)))
7440, 73syld 45 . . 3 (𝜑 → ((((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = (1 mod 𝑃) → (2 /L 𝑃) = (-1↑𝑁)))
7516, 74sylbid 150 . 2 (𝜑 → ((((-1↑𝑁) · (2↑𝐻)) mod 𝑃) = 1 → (2 /L 𝑃) = (-1↑𝑁)))
766, 75mpd 13 1 (𝜑 → (2 /L 𝑃) = (-1↑𝑁))
Colors of variables: wff set class
Syntax hints:  wi 4  wa 104   = wceq 1364  wcel 2160  cdif 3146  ifcif 3553  {csn 3614   class class class wbr 4025  cmpt 4086  cfv 5242  (class class class)co 5906  cc 7856  0cc0 7858  1c1 7859   + caddc 7861   · cmul 7863   < clt 8040  cmin 8176  -cneg 8177   / cdiv 8677  cn 8968  2c2 9019  4c4 9021  0cn0 9226  cz 9303  cq 9670  ...cfz 10060  cfl 10323   mod cmo 10379  cexp 10583  cprime 12219   /L clgs 15041
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 615  ax-in2 616  ax-io 710  ax-5 1458  ax-7 1459  ax-gen 1460  ax-ie1 1504  ax-ie2 1505  ax-8 1515  ax-10 1516  ax-11 1517  ax-i12 1518  ax-bndl 1520  ax-4 1521  ax-17 1537  ax-i9 1541  ax-ial 1545  ax-i5r 1546  ax-13 2162  ax-14 2163  ax-ext 2171  ax-coll 4140  ax-sep 4143  ax-nul 4151  ax-pow 4199  ax-pr 4234  ax-un 4458  ax-setind 4561  ax-iinf 4612  ax-cnex 7949  ax-resscn 7950  ax-1cn 7951  ax-1re 7952  ax-icn 7953  ax-addcl 7954  ax-addrcl 7955  ax-mulcl 7956  ax-mulrcl 7957  ax-addcom 7958  ax-mulcom 7959  ax-addass 7960  ax-mulass 7961  ax-distr 7962  ax-i2m1 7963  ax-0lt1 7964  ax-1rid 7965  ax-0id 7966  ax-rnegex 7967  ax-precex 7968  ax-cnre 7969  ax-pre-ltirr 7970  ax-pre-ltwlin 7971  ax-pre-lttrn 7972  ax-pre-apti 7973  ax-pre-ltadd 7974  ax-pre-mulgt0 7975  ax-pre-mulext 7976  ax-arch 7977  ax-caucvg 7978
This theorem depends on definitions:  df-bi 117  df-stab 832  df-dc 836  df-3or 981  df-3an 982  df-tru 1367  df-fal 1370  df-xor 1387  df-nf 1472  df-sb 1774  df-eu 2041  df-mo 2042  df-clab 2176  df-cleq 2182  df-clel 2185  df-nfc 2321  df-ne 2361  df-nel 2456  df-ral 2473  df-rex 2474  df-reu 2475  df-rmo 2476  df-rab 2477  df-v 2758  df-sbc 2982  df-csb 3077  df-dif 3151  df-un 3153  df-in 3155  df-ss 3162  df-nul 3443  df-if 3554  df-pw 3599  df-sn 3620  df-pr 3621  df-tp 3622  df-op 3623  df-uni 3832  df-int 3867  df-iun 3910  df-br 4026  df-opab 4087  df-mpt 4088  df-tr 4124  df-id 4318  df-po 4321  df-iso 4322  df-iord 4391  df-on 4393  df-ilim 4394  df-suc 4396  df-iom 4615  df-xp 4657  df-rel 4658  df-cnv 4659  df-co 4660  df-dm 4661  df-rn 4662  df-res 4663  df-ima 4664  df-iota 5203  df-fun 5244  df-fn 5245  df-f 5246  df-f1 5247  df-fo 5248  df-f1o 5249  df-fv 5250  df-isom 5251  df-riota 5861  df-ov 5909  df-oprab 5910  df-mpo 5911  df-1st 6180  df-2nd 6181  df-recs 6345  df-irdg 6410  df-frec 6431  df-1o 6456  df-2o 6457  df-oadd 6460  df-er 6574  df-en 6782  df-dom 6783  df-fin 6784  df-sup 7029  df-inf 7030  df-pnf 8042  df-mnf 8043  df-xr 8044  df-ltxr 8045  df-le 8046  df-sub 8178  df-neg 8179  df-reap 8580  df-ap 8587  df-div 8678  df-inn 8969  df-2 9027  df-3 9028  df-4 9029  df-5 9030  df-6 9031  df-7 9032  df-8 9033  df-n0 9227  df-z 9304  df-uz 9579  df-q 9671  df-rp 9706  df-ioo 9944  df-fz 10061  df-fzo 10195  df-fl 10325  df-mod 10380  df-seqfrec 10505  df-exp 10584  df-fac 10771  df-ihash 10821  df-cj 10960  df-re 10961  df-im 10962  df-rsqrt 11116  df-abs 11117  df-clim 11396  df-proddc 11668  df-dvds 11905  df-gcd 12054  df-prm 12220  df-phi 12323  df-pc 12397  df-lgs 15042
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator