Theorem 2lgs 27537

Description: The second supplement to the law of quadratic reciprocity (for the Legendre symbol extended to arbitrary primes as second argument). Two is a square modulo a prime 𝑃 iff 𝑃≡±1 (mod 8), see first case of theorem 9.5 in [ApostolNT] p. 181. This theorem justifies our definition of (𝑁 /_L 2) (lgs2 27444) to some degree, by demanding that reciprocity extend to the case 𝑄 = 2. (Proposed by Mario Carneiro, 19-Jun-2015.) (Contributed by AV, 16-Jul-2021.)

Assertion

Ref	Expression
2lgs	⊢ (𝑃 ∈ ℙ → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7}))

Proof of Theorem 2lgs

Dummy variables 𝑖 𝑥 𝑦 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		prm2orodd 16749	. 2 ⊢ (𝑃 ∈ ℙ → (𝑃 = 2 ∨ ¬ 2 ∥ 𝑃))
2		2lgslem4 27536	. . . . . 6 ⊢ ((2 /L 2) = 1 ↔ (2 mod 8) ∈ {1, 7})
3	2	a1i 11	. . . . 5 ⊢ (𝑃 = 2 → ((2 /L 2) = 1 ↔ (2 mod 8) ∈ {1, 7}))
4		oveq2 7419	. . . . . 6 ⊢ (𝑃 = 2 → (2 /L 𝑃) = (2 /L 2))
5	4	eqeq1d 2771	. . . . 5 ⊢ (𝑃 = 2 → ((2 /L 𝑃) = 1 ↔ (2 /L 2) = 1))
6		oveq1 7418	. . . . . 6 ⊢ (𝑃 = 2 → (𝑃 mod 8) = (2 mod 8))
7	6	eleq1d 2854	. . . . 5 ⊢ (𝑃 = 2 → ((𝑃 mod 8) ∈ {1, 7} ↔ (2 mod 8) ∈ {1, 7}))
8	3, 5, 7	3bitr4d 314	. . . 4 ⊢ (𝑃 = 2 → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7}))
9	8	a1d 26	. . 3 ⊢ (𝑃 = 2 → (𝑃 ∈ ℙ → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7})))
10		2prm 16750	. . . . . . . . . 10 ⊢ 2 ∈ ℙ
11		prmnn 16732	. . . . . . . . . 10 ⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
12		dvdsprime 16745	. . . . . . . . . 10 ⊢ ((2 ∈ ℙ ∧ 𝑃 ∈ ℕ) → (𝑃 ∥ 2 ↔ (𝑃 = 2 ∨ 𝑃 = 1)))
13	10, 11, 12	sylancr 598	. . . . . . . . 9 ⊢ (𝑃 ∈ ℙ → (𝑃 ∥ 2 ↔ (𝑃 = 2 ∨ 𝑃 = 1)))
14		z2even 16428	. . . . . . . . . . . . 13 ⊢ 2 ∥ 2
15		breq2 5115	. . . . . . . . . . . . 13 ⊢ (𝑃 = 2 → (2 ∥ 𝑃 ↔ 2 ∥ 2))
16	14, 15	mpbiri 261	. . . . . . . . . . . 12 ⊢ (𝑃 = 2 → 2 ∥ 𝑃)
17	16	a1d 26	. . . . . . . . . . 11 ⊢ (𝑃 = 2 → (𝑃 ∈ ℙ → 2 ∥ 𝑃))
18		eleq1 2857	. . . . . . . . . . . 12 ⊢ (𝑃 = 1 → (𝑃 ∈ ℙ ↔ 1 ∈ ℙ))
19		1nprm 16737	. . . . . . . . . . . . 13 ⊢ ¬ 1 ∈ ℙ
20	19	pm2.21i 120	. . . . . . . . . . . 12 ⊢ (1 ∈ ℙ → 2 ∥ 𝑃)
21	18, 20	biimtrdi 256	. . . . . . . . . . 11 ⊢ (𝑃 = 1 → (𝑃 ∈ ℙ → 2 ∥ 𝑃))
22	17, 21	jaoi 870	. . . . . . . . . 10 ⊢ ((𝑃 = 2 ∨ 𝑃 = 1) → (𝑃 ∈ ℙ → 2 ∥ 𝑃))
23	22	com12 33	. . . . . . . . 9 ⊢ (𝑃 ∈ ℙ → ((𝑃 = 2 ∨ 𝑃 = 1) → 2 ∥ 𝑃))
24	13, 23	sylbid 243	. . . . . . . 8 ⊢ (𝑃 ∈ ℙ → (𝑃 ∥ 2 → 2 ∥ 𝑃))
25	24	con3dimp 413	. . . . . . 7 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ¬ 𝑃 ∥ 2)
26		2z 12626	. . . . . . 7 ⊢ 2 ∈ ℤ
27	25, 26	jctil 528	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (2 ∈ ℤ ∧ ¬ 𝑃 ∥ 2))
28		2lgslem1 27524	. . . . . . 7 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))}) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))))
29	28	eqcomd 2775	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))}))
30		nnoddn2prmb 16873	. . . . . . . . . 10 ⊢ (𝑃 ∈ (ℙ ∖ {2}) ↔ (𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃))
31	30	biimpri 231	. . . . . . . . 9 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → 𝑃 ∈ (ℙ ∖ {2}))
32	31	3ad2ant1 1149	. . . . . . . 8 ⊢ (((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) ∧ (2 ∈ ℤ ∧ ¬ 𝑃 ∥ 2) ∧ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))})) → 𝑃 ∈ (ℙ ∖ {2}))
33		eqid 2769	. . . . . . . 8 ⊢ ((𝑃 − 1) / 2) = ((𝑃 − 1) / 2)
34		eqid 2769	. . . . . . . 8 ⊢ (𝑦 ∈ (1...((𝑃 − 1) / 2)) ↦ if((𝑦 · 2) < (𝑃 / 2), (𝑦 · 2), (𝑃 − (𝑦 · 2)))) = (𝑦 ∈ (1...((𝑃 − 1) / 2)) ↦ if((𝑦 · 2) < (𝑃 / 2), (𝑦 · 2), (𝑃 − (𝑦 · 2))))
35		eqid 2769	. . . . . . . 8 ⊢ (⌊‘(𝑃 / 4)) = (⌊‘(𝑃 / 4))
36		eqid 2769	. . . . . . . 8 ⊢ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) = (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))
37	32, 33, 34, 35, 36	gausslemma2d 27504	. . . . . . 7 ⊢ (((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) ∧ (2 ∈ ℤ ∧ ¬ 𝑃 ∥ 2) ∧ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))})) → (2 /L 𝑃) = (-1↑(((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))))
38	37	eqeq1d 2771	. . . . . 6 ⊢ (((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) ∧ (2 ∈ ℤ ∧ ¬ 𝑃 ∥ 2) ∧ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) = (♯‘{𝑥 ∈ ℤ ∣ ∃𝑖 ∈ (1...((𝑃 − 1) / 2))(𝑥 = (𝑖 · 2) ∧ (𝑃 / 2) < (𝑥 mod 𝑃))})) → ((2 /L 𝑃) = 1 ↔ (-1↑(((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))) = 1))
39	27, 29, 38	mpd3an23 1489	. . . . 5 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((2 /L 𝑃) = 1 ↔ (-1↑(((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))) = 1))
40	36	2lgslem2 27525	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ∈ ℤ)
41		m1exp1 16434	. . . . . 6 ⊢ ((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ∈ ℤ → ((-1↑(((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))) = 1 ↔ 2 ∥ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))))
42	40, 41	syl 18	. . . . 5 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((-1↑(((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))) = 1 ↔ 2 ∥ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4)))))
43		2nn 12314	. . . . . . 7 ⊢ 2 ∈ ℕ
44		dvdsval3 16314	. . . . . . 7 ⊢ ((2 ∈ ℕ ∧ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ∈ ℤ) → (2 ∥ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ↔ ((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) mod 2) = 0))
45	43, 40, 44	sylancr 598	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (2 ∥ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ↔ ((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) mod 2) = 0))
46	36	2lgslem3 27534	. . . . . . . 8 ⊢ ((𝑃 ∈ ℕ ∧ ¬ 2 ∥ 𝑃) → ((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) mod 2) = if((𝑃 mod 8) ∈ {1, 7}, 0, 1))
47	11, 46	sylan 591	. . . . . . 7 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) mod 2) = if((𝑃 mod 8) ∈ {1, 7}, 0, 1))
48	47	eqeq1d 2771	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (((((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) mod 2) = 0 ↔ if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0))
49		ax-1 6	. . . . . . . . 9 ⊢ ((𝑃 mod 8) ∈ {1, 7} → (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 → (𝑃 mod 8) ∈ {1, 7}))
50		iffalse 4499	. . . . . . . . . . 11 ⊢ (¬ (𝑃 mod 8) ∈ {1, 7} → if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 1)
51	50	eqeq1d 2771	. . . . . . . . . 10 ⊢ (¬ (𝑃 mod 8) ∈ {1, 7} → (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 ↔ 1 = 0))
52		ax-1ne0 11169	. . . . . . . . . . 11 ⊢ 1 ≠ 0
53		eqneqall 2975	. . . . . . . . . . 11 ⊢ (1 = 0 → (1 ≠ 0 → (𝑃 mod 8) ∈ {1, 7}))
54	52, 53	mpi 21	. . . . . . . . . 10 ⊢ (1 = 0 → (𝑃 mod 8) ∈ {1, 7})
55	51, 54	biimtrdi 256	. . . . . . . . 9 ⊢ (¬ (𝑃 mod 8) ∈ {1, 7} → (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 → (𝑃 mod 8) ∈ {1, 7}))
56	49, 55	pm2.61i 184	. . . . . . . 8 ⊢ (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 → (𝑃 mod 8) ∈ {1, 7})
57		iftrue 4496	. . . . . . . 8 ⊢ ((𝑃 mod 8) ∈ {1, 7} → if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0)
58	56, 57	impbii 212	. . . . . . 7 ⊢ (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 ↔ (𝑃 mod 8) ∈ {1, 7})
59	58	a1i 11	. . . . . 6 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (if((𝑃 mod 8) ∈ {1, 7}, 0, 1) = 0 ↔ (𝑃 mod 8) ∈ {1, 7}))
60	45, 48, 59	3bitrd 308	. . . . 5 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → (2 ∥ (((𝑃 − 1) / 2) − (⌊‘(𝑃 / 4))) ↔ (𝑃 mod 8) ∈ {1, 7}))
61	39, 42, 60	3bitrd 308	. . . 4 ⊢ ((𝑃 ∈ ℙ ∧ ¬ 2 ∥ 𝑃) → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7}))
62	61	expcom 418	. . 3 ⊢ (¬ 2 ∥ 𝑃 → (𝑃 ∈ ℙ → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7})))
63	9, 62	jaoi 870	. 2 ⊢ ((𝑃 = 2 ∨ ¬ 2 ∥ 𝑃) → (𝑃 ∈ ℙ → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7})))
64	1, 63	mpcom 39	1 ⊢ (𝑃 ∈ ℙ → ((2 /L 𝑃) = 1 ↔ (𝑃 mod 8) ∈ {1, 7}))

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 400   ∨ wo 860   ∧ w3a 1101   = wceq 1567   ∈ wcel 2149   ≠ wne 2964  ∃wrex 3095  {crab 3422   ∖ cdif 3908  ifcif 4490  {csn 4592  {cpr 4594   class class class wbr 5111   ↦ cmpt 5194  ‘cfv 6537  (class class class)co 7411  0cc0 11100  1c1 11101   · cmul 11105   < clt 11243   − cmin 11441  -cneg 11442   / cdiv 11871  ℕcn 12233  2c2 12295  4c4 12297  7c7 12300  8c8 12301  ℤcz 12591  ...cfz 13535  ⌊cfl 13823   mod cmo 13902  ↑cexp 14097  ♯chash 14366   ∥ cdvds 16310  ℙcprime 16729   /_L clgs 27424

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1822  ax-4 1836  ax-5 1937  ax-6 1994  ax-7 2035  ax-8 2151  ax-9 2159  ax-10 2182  ax-11 2198  ax-12 2219  ax-ext 2741  ax-rep 5240  ax-sep 5259  ax-nul 5271  ax-pow 5337  ax-pr 5405  ax-un 7733  ax-inf2 9610  ax-cnex 11156  ax-resscn 11157  ax-1cn 11158  ax-icn 11159  ax-addcl 11160  ax-addrcl 11161  ax-mulcl 11162  ax-mulrcl 11163  ax-mulcom 11164  ax-addass 11165  ax-mulass 11166  ax-distr 11167  ax-i2m1 11168  ax-1ne0 11169  ax-1rid 11170  ax-rnegex 11171  ax-rrecex 11172  ax-cnre 11173  ax-pre-lttri 11174  ax-pre-lttrn 11175  ax-pre-ltadd 11176  ax-pre-mulgt0 11177  ax-pre-sup 11178

This theorem depends on definitions:  df-bi 210  df-an 401  df-or 861  df-3or 1102  df-3an 1103  df-tru 1570  df-fal 1580  df-ex 1807  df-nf 1811  df-sb 2098  df-mo 2573  df-eu 2603  df-clab 2748  df-cleq 2761  df-clel 2844  df-nfc 2918  df-ne 2965  df-nel 3071  df-ral 3086  df-rex 3096  df-rmo 3375  df-reu 3376  df-rab 3423  df-v 3463  df-sbc 3752  df-csb 3860  df-dif 3914  df-un 3916  df-in 3918  df-ss 3928  df-pss 3931  df-nul 4293  df-if 4491  df-pw 4567  df-sn 4593  df-pr 4595  df-tp 4597  df-op 4599  df-uni 4875  df-int 4915  df-iun 4960  df-br 5112  df-opab 5176  df-mpt 5195  df-tr 5221  df-id 5557  df-eprel 5562  df-po 5570  df-so 5571  df-fr 5615  df-se 5616  df-we 5617  df-xp 5668  df-rel 5669  df-cnv 5670  df-co 5671  df-dm 5672  df-rn 5673  df-res 5674  df-ima 5675  df-pred 6303  df-ord 6364  df-on 6365  df-lim 6366  df-suc 6367  df-iota 6493  df-fun 6539  df-fn 6540  df-f 6541  df-f1 6542  df-fo 6543  df-f1o 6544  df-fv 6545  df-isom 6546  df-riota 7368  df-ov 7414  df-oprab 7415  df-mpo 7416  df-om 7863  df-1st 7986  df-2nd 7987  df-frecs 8278  df-wrecs 8309  df-recs 8358  df-rdg 8397  df-1o 8453  df-2o 8454  df-oadd 8457  df-er 8694  df-en 8944  df-dom 8945  df-sdom 8946  df-fin 8947  df-sup 9402  df-inf 9403  df-oi 9472  df-dju 9887  df-card 9925  df-pnf 11245  df-mnf 11246  df-xr 11247  df-ltxr 11248  df-le 11249  df-sub 11443  df-neg 11444  df-div 11872  df-nn 12234  df-2 12303  df-3 12304  df-4 12305  df-5 12306  df-6 12307  df-7 12308  df-8 12309  df-n0 12505  df-xnn0 12578  df-z 12592  df-uz 12863  df-q 12973  df-rp 13017  df-ioo 13376  df-ico 13378  df-fz 13536  df-fzo 13683  df-fl 13825  df-mod 13903  df-seq 14038  df-exp 14098  df-fac 14310  df-hash 14367  df-cj 15150  df-re 15151  df-im 15152  df-sqrt 15286  df-abs 15287  df-clim 15539  df-prod 15958  df-dvds 16311  df-gcd 16553  df-prm 16730  df-phi 16825  df-pc 16897  df-lgs 27425

This theorem is referenced by:  2lgsoddprm  27546  fmtnoprmfac2lem1  48242  sfprmdvdsmersenne  48279