Theorem lgsqrmod 26834

Description: If the Legendre symbol of an integer for an odd prime is 1, then the number is a quadratic residue mod 𝑃. (Contributed by AV, 20-Aug-2021.)

Assertion

Ref	Expression
lgsqrmod	⊢ ((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → ((𝐴 /L 𝑃) = 1 → ∃𝑥 ∈ ℤ ((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃)))

Distinct variable groups:   𝑥,𝐴   𝑥,𝑃

Proof of Theorem lgsqrmod

Step	Hyp	Ref	Expression
1		lgsqr 26833	. 2 ⊢ ((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → ((𝐴 /L 𝑃) = 1 ↔ (¬ 𝑃 ∥ 𝐴 ∧ ∃𝑥 ∈ ℤ 𝑃 ∥ ((𝑥↑2) − 𝐴))))
2		eldifi 4124	. . . . . . . 8 ⊢ (𝑃 ∈ (ℙ ∖ {2}) → 𝑃 ∈ ℙ)
3		prmnn 16606	. . . . . . . 8 ⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
4	2, 3	syl 17	. . . . . . 7 ⊢ (𝑃 ∈ (ℙ ∖ {2}) → 𝑃 ∈ ℕ)
5	4	ad2antlr 726	. . . . . 6 ⊢ (((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) ∧ 𝑥 ∈ ℤ) → 𝑃 ∈ ℕ)
6		zsqcl 14089	. . . . . . 7 ⊢ (𝑥 ∈ ℤ → (𝑥↑2) ∈ ℤ)
7	6	adantl 483	. . . . . 6 ⊢ (((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) ∧ 𝑥 ∈ ℤ) → (𝑥↑2) ∈ ℤ)
8		simpll 766	. . . . . 6 ⊢ (((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) ∧ 𝑥 ∈ ℤ) → 𝐴 ∈ ℤ)
9		moddvds 16203	. . . . . 6 ⊢ ((𝑃 ∈ ℕ ∧ (𝑥↑2) ∈ ℤ ∧ 𝐴 ∈ ℤ) → (((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃) ↔ 𝑃 ∥ ((𝑥↑2) − 𝐴)))
10	5, 7, 8, 9	syl3anc 1372	. . . . 5 ⊢ (((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) ∧ 𝑥 ∈ ℤ) → (((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃) ↔ 𝑃 ∥ ((𝑥↑2) − 𝐴)))
11	10	biimprd 247	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) ∧ 𝑥 ∈ ℤ) → (𝑃 ∥ ((𝑥↑2) − 𝐴) → ((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃)))
12	11	reximdva 3169	. . 3 ⊢ ((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → (∃𝑥 ∈ ℤ 𝑃 ∥ ((𝑥↑2) − 𝐴) → ∃𝑥 ∈ ℤ ((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃)))
13	12	adantld 492	. 2 ⊢ ((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → ((¬ 𝑃 ∥ 𝐴 ∧ ∃𝑥 ∈ ℤ 𝑃 ∥ ((𝑥↑2) − 𝐴)) → ∃𝑥 ∈ ℤ ((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃)))
14	1, 13	sylbid 239	1 ⊢ ((𝐴 ∈ ℤ ∧ 𝑃 ∈ (ℙ ∖ {2})) → ((𝐴 /L 𝑃) = 1 → ∃𝑥 ∈ ℤ ((𝑥↑2) mod 𝑃) = (𝐴 mod 𝑃)))

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 205   ∧ wa 397   = wceq 1542   ∈ wcel 2107  ∃wrex 3071   ∖ cdif 3943  {csn 4626   class class class wbr 5146  (class class class)co 7403  1c1 11106   − cmin 11439  ℕcn 12207  2c2 12262  ℤcz 12553   mod cmo 13829  ↑cexp 14022   ∥ cdvds 16192  ℙcprime 16603   /_L clgs 26776

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 1914  ax-6 1972  ax-7 2012  ax-8 2109  ax-9 2117  ax-10 2138  ax-11 2155  ax-12 2172  ax-ext 2704  ax-rep 5283  ax-sep 5297  ax-nul 5304  ax-pow 5361  ax-pr 5425  ax-un 7719  ax-cnex 11161  ax-resscn 11162  ax-1cn 11163  ax-icn 11164  ax-addcl 11165  ax-addrcl 11166  ax-mulcl 11167  ax-mulrcl 11168  ax-mulcom 11169  ax-addass 11170  ax-mulass 11171  ax-distr 11172  ax-i2m1 11173  ax-1ne0 11174  ax-1rid 11175  ax-rnegex 11176  ax-rrecex 11177  ax-cnre 11178  ax-pre-lttri 11179  ax-pre-lttrn 11180  ax-pre-ltadd 11181  ax-pre-mulgt0 11182  ax-pre-sup 11183  ax-addf 11184  ax-mulf 11185

This theorem depends on definitions:  df-bi 206  df-an 398  df-or 847  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1783  df-nf 1787  df-sb 2069  df-mo 2535  df-eu 2564  df-clab 2711  df-cleq 2725  df-clel 2811  df-nfc 2886  df-ne 2942  df-nel 3048  df-ral 3063  df-rex 3072  df-rmo 3377  df-reu 3378  df-rab 3434  df-v 3477  df-sbc 3776  df-csb 3892  df-dif 3949  df-un 3951  df-in 3953  df-ss 3963  df-pss 3965  df-nul 4321  df-if 4527  df-pw 4602  df-sn 4627  df-pr 4629  df-tp 4631  df-op 4633  df-uni 4907  df-int 4949  df-iun 4997  df-iin 4998  df-br 5147  df-opab 5209  df-mpt 5230  df-tr 5264  df-id 5572  df-eprel 5578  df-po 5586  df-so 5587  df-fr 5629  df-se 5630  df-we 5631  df-xp 5680  df-rel 5681  df-cnv 5682  df-co 5683  df-dm 5684  df-rn 5685  df-res 5686  df-ima 5687  df-pred 6296  df-ord 6363  df-on 6364  df-lim 6365  df-suc 6366  df-iota 6491  df-fun 6541  df-fn 6542  df-f 6543  df-f1 6544  df-fo 6545  df-f1o 6546  df-fv 6547  df-isom 6548  df-riota 7359  df-ov 7406  df-oprab 7407  df-mpo 7408  df-of 7664  df-ofr 7665  df-om 7850  df-1st 7969  df-2nd 7970  df-supp 8141  df-tpos 8205  df-frecs 8260  df-wrecs 8291  df-recs 8365  df-rdg 8404  df-1o 8460  df-2o 8461  df-oadd 8464  df-er 8698  df-ec 8700  df-qs 8704  df-map 8817  df-pm 8818  df-ixp 8887  df-en 8935  df-dom 8936  df-sdom 8937  df-fin 8938  df-fsupp 9357  df-sup 9432  df-inf 9433  df-oi 9500  df-dju 9891  df-card 9929  df-pnf 11245  df-mnf 11246  df-xr 11247  df-ltxr 11248  df-le 11249  df-sub 11441  df-neg 11442  df-div 11867  df-nn 12208  df-2 12270  df-3 12271  df-4 12272  df-5 12273  df-6 12274  df-7 12275  df-8 12276  df-9 12277  df-n0 12468  df-xnn0 12540  df-z 12554  df-dec 12673  df-uz 12818  df-q 12928  df-rp 12970  df-fz 13480  df-fzo 13623  df-fl 13752  df-mod 13830  df-seq 13962  df-exp 14023  df-hash 14286  df-cj 15041  df-re 15042  df-im 15043  df-sqrt 15177  df-abs 15178  df-dvds 16193  df-gcd 16431  df-prm 16604  df-phi 16694  df-pc 16765  df-struct 17075  df-sets 17092  df-slot 17110  df-ndx 17122  df-base 17140  df-ress 17169  df-plusg 17205  df-mulr 17206  df-starv 17207  df-sca 17208  df-vsca 17209  df-ip 17210  df-tset 17211  df-ple 17212  df-ds 17214  df-unif 17215  df-hom 17216  df-cco 17217  df-0g 17382  df-gsum 17383  df-prds 17388  df-pws 17390  df-imas 17449  df-qus 17450  df-mre 17525  df-mrc 17526  df-acs 17528  df-mgm 18556  df-sgrp 18605  df-mnd 18621  df-mhm 18666  df-submnd 18667  df-grp 18817  df-minusg 18818  df-sbg 18819  df-mulg 18944  df-subg 18996  df-nsg 18997  df-eqg 18998  df-ghm 19083  df-cntz 19174  df-cmn 19642  df-abl 19643  df-mgp 19979  df-ur 19996  df-srg 20000  df-ring 20048  df-cring 20049  df-oppr 20138  df-dvdsr 20159  df-unit 20160  df-invr 20190  df-dvr 20203  df-rnghom 20239  df-nzr 20280  df-drng 20305  df-field 20306  df-subrg 20348  df-lmod 20460  df-lss 20530  df-lsp 20570  df-sra 20772  df-rgmod 20773  df-lidl 20774  df-rsp 20775  df-2idl 20843  df-rlreg 20885  df-domn 20886  df-idom 20887  df-cnfld 20929  df-zring 21002  df-zrh 21036  df-zn 21039  df-assa 21391  df-asp 21392  df-ascl 21393  df-psr 21443  df-mvr 21444  df-mpl 21445  df-opsr 21447  df-evls 21616  df-evl 21617  df-psr1 21685  df-vr1 21686  df-ply1 21687  df-coe1 21688  df-evl1 21816  df-mdeg 25551  df-deg1 25552  df-mon1 25629  df-uc1p 25630  df-q1p 25631  df-r1p 25632  df-lgs 26777

This theorem is referenced by:  lgsqrmodndvds  26835