Premium
Abelian groups and quadratic residues in weak arithmetic
Author(s) -
Jeřábek Emil
Publication year - 2010
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200910009
Subject(s) - mathematics , legendre symbol , fermat's last theorem , abelian group , quadratic residue , modulo , quadratic equation , bounded function , discrete mathematics , quadratic field , pure mathematics , arithmetic , quadratic function , mathematical analysis , geometry
We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S 2 2 + iWPHP(Σ 1 b ), and use it to derive Fermat's little theorem and Euler's criterion for the Legendre symbol in S 2 2 + iWPHP(PV) extended by the pigeonhole principle PHP(PV). We prove the quadratic reciprocity theorem (including the supplementary laws) in the arithmetic theories T 2 0 + Count 2 (PV) and I Δ 0 + Count 2 (Δ 0 ) with modulo‐2 counting principles (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)