Editing Parity (mathematics)

{{Other uses|Parity (disambiguation)}}
{{redirect-synonym|Odd number|[[Odd Number (film){{!}}''Odd Number'' (film)]]}}
{{short description|Property of being an even or odd number}}
[[File:Parity of 5 and 6 Cuisenaire rods.svg|275px|thumb|[[Cuisenaire rods]]: 5 (yellow) ''cannot'' be evenly divided in 2 (red) by any 2 rods of the same color/length, while 6 (dark green) ''can'' be evenly divided in 2 by 3 (lime green).<!-- Thus 5 is odd while 6 is even.-->]]
In [[mathematics]], '''parity''' is the [[Property (mathematics)|property]] of an [[integer]] of whether it is '''even''' or '''odd'''. An integer is even if it is [[divisible]] by 2, and odd if it is not.<ref name="rod">{{citation|title=Figuring Out Mathematics| last1=Vijaya| first1=A.V.|last2=Rodriguez|first2=Dora |publisher=Pearson Education India|isbn=9788131703571| pages=20–21| url=https://books.google.com/books?id=9ZN9LuHb0tQC&pg=PA20}}.</ref> For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers.

The above definition of parity applies only to integer numbers, hence it cannot be applied to numbers with decimals or fractions like 1/2 or 4.6978. See the section "Higher mathematics" below for some extensions of the notion of parity to a larger class of "numbers" or in other more general settings.

Even and odd numbers have opposite parities, e.g., 22 (even number) and 13 (odd number) have opposite parities. In particular, the [[parity of zero]] is even.<ref>{{citation|title=A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory|first=Miklós|last=Bóna|publisher=World Scientific|year=2011|isbn=9789814335232|page=178|url=https://books.google.com/books?id=TzJ2L9ZmlQUC&pg=PA178}}.</ref> Any two consecutive integers have opposite parity. A number (i.e., integer) expressed in the [[decimal]] [[numeral system]] is even or odd according to whether its last digit is even or odd. That is, if the last digit is 1, 3, 5, 7, or 9, then it is odd; otherwise it is even—as the last digit of any even number is 0, 2, 4, 6, or 8. The same idea will work using any even base. In particular, a number expressed in the [[binary numeral system]] is odd if its last digit is 1; and it is even if its last digit is 0. In an odd base, the number is even according to the sum of its digits—it is even if and only if the sum of its digits is even.<ref>{{citation|title=Divisibility in bases|first=Ruth L.|last=Owen|url=http://www.pentagon.kappamuepsilon.org/pentagon/Vol_51_Num_2_Spring_1992.pdf|pages=17–20|journal=The Pentagon: A Mathematics Magazine for Students|volume=51|issue=2|year=1992|url-status=dead|archive-url=https://web.archive.org/web/20150317173427/http://www.pentagon.kappamuepsilon.org/pentagon/Vol_51_Num_2_Spring_1992.pdf|archive-date=2015-03-17}}.</ref>

== Definition ==
An even number is an integer of the form
<math display="block">x = 2k</math>
where ''k'' is an integer;<ref>{{citation|last=Bassarear|first=Tom|title=Mathematics for Elementary School Teachers| url=https://books.google.com/books?id=RitXafH4_8EC&pg=PA198|page=198|year=2010|publisher=Cengage Learning|isbn=9780840054630}}.</ref> an odd number is an integer of the form
<math display="block">x = 2k +1.</math>

An equivalent definition is that an even number is [[divisible]] by 2:
<math display="block">2 \ | \ x</math>
and an odd number is not:
<math display="block">2\not| \ x</math>

The [[Set (mathematics)|sets]] of even and odd numbers can be defined as following:<ref>{{citation|last=Sidebotham|first=Thomas H. | title=The A to Z of Mathematics: A Basic Guide|url=https://books.google.com/books?id=VsAZa5PWLz8C&pg=PA181| page=181 | year=2003| publisher=John Wiley & Sons|isbn=9780471461630}}.</ref>
<math display="block">\{ 2k: k \in \mathbb{Z} \}</math>
<math display="block">\{ 2k+1: k \in \mathbb{Z} \}</math>

The set of ''even'' numbers is a [[prime ideal]] of <math>\mathbb{Z}</math> and the [[quotient ring]] <math>\mathbb{Z}/2\mathbb{Z}</math> is the [[field with two elements]]. Parity can then be defined as the unique [[ring homomorphism]] from <math>\mathbb{Z}</math> to <math>\mathbb{Z}/2\mathbb{Z}</math> where odd numbers are 1 and even numbers are 0. The consequences of this homomorphism are covered below.

== Properties ==
The following laws can be verified using the properties of [[divisibility]]. They are a special case of rules in [[modular arithmetic]], and are commonly used to check if an equality is likely to be correct by testing the parity of each side. As with ordinary arithmetic, multiplication and addition are commutative and associative in modulo 2 arithmetic, and multiplication is distributive over addition. However, subtraction in modulo 2 is identical to addition, so subtraction also possesses these properties, which is not true for normal integer arithmetic.

=== Addition and subtraction ===
* even ± even = even;<ref name="rod"/>
* even ± odd = odd;<ref name="rod"/>
* odd ± odd = even;<ref name="rod"/>

===Multiplication===
* even × even = even;<ref name="rod"/>
* even × odd = even;<ref name="rod"/>
* odd × odd = odd;<ref name="rod"/>

By construction in the previous section, the structure ({even, odd}, +, ×) is in fact the [[GF(2)|field with two elements]].

=== Division ===
The division of two whole numbers does not necessarily result in a whole number. For example, 1 divided by 4 equals 1/4, which is neither even ''nor'' odd, since the concepts of even and odd apply only to integers. But when the [[quotient]] is an integer, it will be even [[if and only if]] the [[division (mathematics)|dividend]] has more [[integer factorization|factors of two]] than the divisor.<ref>{{citation|title=Notes on Introductory Combinatorics|first1=George|last1=Pólya|author1-link=George Pólya| first2=Robert E.|last2=Tarjan|author2-link=Robert Tarjan|first3=Donald R.|last3=Woods|publisher=Springer| year=2009| isbn=9780817649524 |pages=21–22|url=https://books.google.com/books?id=y6KmsI0Icp0C&pg=PA21}}.</ref>

==History==
The ancient Greeks considered 1, the [[Monad (philosophy)|monad]], to be neither fully odd nor fully even.<ref>{{citation| title=Ancient Greek Philosophy: Thales to Gorgias|author=Tankha|publisher=Pearson Education India| year=2006| isbn=9788177589399| page=126|url=https://books.google.com/books?id=88PFcpKjupAC&pg=PT126}}.</ref> Some of this sentiment survived into the 19th century: [[Friedrich Fröbel|Friedrich Wilhelm August Fröbel]]'s 1826 ''The Education of Man'' instructs the teacher to drill students with the claim that 1 is neither even nor odd, to which Fröbel attaches the philosophical afterthought,
{{blockquote|It is well to direct the pupil's attention here at once to a great far-reaching law of nature and of thought. It is this, that between two relatively different things or ideas there stands always a third, in a sort of balance, seeming to unite the two. Thus, there is here between odd and even numbers one number (one) which is neither of the two. Similarly, in form, the right angle stands between the acute and obtuse angles; and in language, the semi-vowels or aspirants between the mutes and vowels. A thoughtful teacher and a pupil taught to think for himself can scarcely help noticing this and other important laws.<ref>{{citation|last=Froebel|first=Friedrich|title=The Education of Man|year=1885|publisher=A Lovell & Company|location=New York|pages=[https://archive.org/details/educationofman00froe/page/240 240]|url=https://archive.org/details/educationofman00froe|translator-first=Josephine|translator-last=Jarvis}}</ref>}}

==Higher mathematics==

===Higher dimensions and more general classes of numbers===
{{Chess diagram
| tright
| 
|  |  |xx|  |xx|  |  |  
|  |xx|  |  |  |xx|  |  
|  |  |  |nd|  |  |  |  
|  |xx|  |  |  |xx|  |  
|  |  |xx|  |xx|  |  |  
|  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |  
|  |  |bl|  |  |bl|  |  
| Each of the white [[bishop (chess)|bishops]] is confined to squares of the same parity; the black [[knight (chess)|knight]] can only jump to squares of alternating parity.
}}
Integer coordinates of points in [[Euclidean space]]s of two or more dimensions also have a parity, usually defined as the parity of the sum of the coordinates. For instance, the [[Cubic crystal system|face-centered cubic lattice]] and its higher-dimensional generalizations (the ''D<sub>n</sub>'' [[Lattice (group)|lattices]]) consist of all of the integer points whose coordinates have an even sum.<ref>{{citation
 | last1 = Conway | first1 = J. H.
 | last2 = Sloane | first2 = N. J. A.
 | edition = 3rd
 | isbn = 978-0-387-98585-5
 | location = New York
 | mr = 1662447
 | page = 10
 | publisher = Springer-Verlag
 | series = Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]
 | title = Sphere packings, lattices and groups
 | url = https://books.google.com/books?id=upYwZ6cQumoC&pg=PA10
 | volume = 290
 | year = 1999}}.</ref> This feature also manifests itself in [[chess]], where the parity of a square is indicated by its color: [[Bishop (chess)|bishops]] are constrained to moving between squares of the same parity, whereas [[Knight (chess)|knights]] alternate parity between moves.<ref>{{citation|title=Chess Thinking: The Visual Dictionary of Chess Moves, Rules, Strategies and Concepts|first=Bruce|last=Pandolfini|author-link=Bruce Pandolfini|publisher=Simon and Schuster|year=1995|isbn=9780671795023|pages=273–274|url=https://books.google.com/books?id=S2gI_mExCOoC&pg=PA273}}.</ref> This form of parity was famously used to solve the [[mutilated chessboard problem]]: if two opposite corner squares are removed from a chessboard, then the remaining board cannot be covered by dominoes, because each domino covers one square of each parity and there are two more squares of one parity than of the other.<ref>{{citation|doi=10.2307/4146865|title=Tiling with dominoes| first=N. S.|last=Mendelsohn|journal=The College Mathematics Journal|volume=35|issue=2|year=2004| pages=115–120|jstor=4146865}}.</ref>

The [[Even and odd ordinals|parity of an ordinal number]] may be defined to be even if the number is a limit ordinal, or a limit ordinal plus a finite even number, and odd otherwise.<ref>{{citation|title=Real Analysis |last1=Bruckner|first1= Andrew M.| first2=Judith B.|last2=Bruckner|first3= Brian S.|last3=Thomson |year=1997 |isbn=978-0-13-458886-5 | page=37|publisher=ClassicalRealAnalysis.com | url=https://books.google.com/books?id=1WY6u0C_jEsC&pg=PA37}}.</ref>

Let ''R'' be a [[commutative ring]] and let ''I'' be an [[Ideal (ring theory)|ideal]] of ''R'' whose [[Index of a subgroup|index]] is 2. Elements of the [[coset]] <math>0+I</math> may be called '''even''', while elements of the coset <math>1+I</math> may be called '''odd'''.
As an example, let {{math|1=''R'' = '''Z'''<sub>(2)</sub>}} be the [[Localization of a ring|localization]] of '''Z''' at the [[prime ideal]] (2). Then an element of ''R'' is even or odd if and only if its numerator is so in '''Z'''.

===Number theory===
The even numbers form an [[ring ideal|ideal]] in the [[ring (algebra)|ring]] of integers,<ref>{{citation|title=Elements of Number Theory|first=John|last=Stillwell|author-link=John Stillwell|publisher=Springer|year=2003 |isbn=9780387955872|page=199 |url=https://books.google.com/books?id=LiAlZO2ntKAC&pg=PA199}}.</ref> but the odd numbers do not&mdash;this is clear from the fact that the [[Identity (mathematics)|identity]] element for addition, zero, is an element of the even numbers only. An integer is even if it is congruent to 0 [[modular arithmetic|modulo]] this ideal, in other words if it is congruent to 0 modulo 2, and odd if it is congruent to 1 modulo 2.

All [[prime number]]s are odd, with one exception: the prime number 2.<ref>{{citation |last1=Lial |first1=Margaret L. |title=Basic College Mathematics |url=https://archive.org/details/basiccollegemath00lial/page/128/mode/2up |page=128 |year=2005 |edition=7th |publisher=Addison Wesley |isbn=9780321257802 |last2=Salzman |first2=Stanley A. |last3=Hestwood |first3=Diana}}.</ref> All known [[perfect number]]s are even; it is unknown whether any odd perfect numbers exist.<ref>{{citation|title=Mathematical Cranks|title-link=Mathematical Cranks|series=MAA Spectrum| first=Underwood| last=Dudley|author-link=Underwood Dudley|publisher=Cambridge University Press|year=1992|contribution=Perfect numbers| pages=242–244| contribution-url=https://books.google.com/books?id=HqeoWPsIH6EC&pg=PA242|isbn=9780883855072}}.</ref>

[[Goldbach's conjecture]] states that every even integer greater than 2 can be represented as a sum of two prime numbers. Modern [[computer]] calculations have shown this conjecture to be true for integers up to at least 4 &times; 10<sup>18</sup>, but still no general [[mathematical proof|proof]] has been found.<ref>{{citation|title=Empirical verification of the even Goldbach conjecture, and computation of prime gaps, up to 4&middot;10<sup>18</sup>|url=https://www.ams.org/editflow/editorial/uploads/mcom/accepted/120521-Silva/120521-Silva-v2.pdf|first1=Tomás|last1=Oliveira e Silva|first2=Siegfried|last2=Herzog|first3=Silvio|last3=Pardi|journal=Mathematics of Computation|volume=83|issue=288|pages=2033–2060|year=2013|doi=10.1090/s0025-5718-2013-02787-1|doi-access=free}}. In press.</ref>

===Group theory===
[[File:Rubiks revenge solved.jpg|thumb|left|[[Rubik's Revenge]] in solved state]]
The [[parity of a permutation]] (as defined in [[abstract algebra]]) is the parity of the number of [[Transposition (mathematics)|transposition]]s into which the permutation can be decomposed.<ref>{{citation|title=Permutation Groups|volume=45|series=London Mathematical Society Student Texts|first=Peter J.|last=Cameron|author-link=Peter Cameron (mathematician)|publisher=Cambridge University Press|year=1999|isbn=9780521653787|pages=26–27|url=https://books.google.com/books?id=4bNj8K1omGAC&pg=PA26}}.</ref> For example (ABC) to (BCA) is even because it can be done by swapping A and B then C and A (two transpositions). It can be shown that no permutation can be decomposed both in an even and in an odd number of transpositions. Hence the above is a suitable definition. In [[Rubik's Cube]], [[Megaminx]], and other twisting puzzles, the moves of the puzzle allow only even permutations of the puzzle pieces, so parity is important in understanding the [[Configuration space (mathematics)|configuration space]] of these puzzles.<ref>{{citation|title=Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys|first=David|last=Joyner|publisher=JHU Press|year=2008|isbn=9780801897269|contribution=13.1.2 Parity conditions|pages=252–253|url=https://books.google.com/books?id=iM0fco-_Ri8C&pg=PA252}}.</ref>

The [[Feit&ndash;Thompson theorem]] states that a [[finite group]] is always solvable if its order is an odd number.  This is an example of odd numbers playing a role in an advanced mathematical theorem where the method of application of the simple hypothesis of "odd order" is far from obvious.<ref>{{citation
 | last1 = Bender | first1 = Helmut
 | last2 = Glauberman | first2 = George
 | isbn = 978-0-521-45716-3
 | location = Cambridge
 | mr = 1311244
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Local analysis for the odd order theorem
 | volume = 188
 | year = 1994}}; {{citation
 | last = Peterfalvi | first = Thomas
 | isbn = 978-0-521-64660-4
 | location = Cambridge
 | mr = 1747393
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Character theory for the odd order theorem
 | volume = 272
 | year = 2000}}.</ref>

===Analysis===
The [[Even and odd functions|parity of a function]] describes how its values change when its arguments are exchanged with their negations. An even function, such as an even power of a variable, gives the same result for any argument as for its negation. An odd function, such as an odd power of a variable, gives for any argument the negation of its result when given the negation of that argument. It is possible for a function to be neither odd nor even, and for the case ''f''(''x'')&nbsp;=&nbsp;0, to be both odd and even.<ref>{{citation|title=College Algebra|edition=11th|first1=Roy David|last1=Gustafson|first2=Jeffrey D.|last2=Hughes|publisher=Cengage Learning|year=2012|isbn=9781111990909|page=315|url=https://books.google.com/books?id=sxZpddk1fTIC&pg=PA315}}.</ref> The [[Taylor series]] of an even function contains only terms whose exponent is an even number, and the Taylor series of an odd function contains only terms whose exponent is an odd number.<ref>{{citation|title=Advanced Engineering Mathematics|first1=R. K.|last1=Jain|first2=S. R. K.|last2=Iyengar|publisher=Alpha Science Int'l Ltd.|year=2007|isbn=9781842651858|page=853|url=https://books.google.com/books?id=crOxJNLE5psC&pg=PA853}}.</ref>

===Combinatorial game theory===
In [[combinatorial game theory]], an ''[[evil number]]'' is a number that has an even number of 1's in its [[binary representation]], and an ''odious number'' is a number that has an odd number of 1's in its binary representation; these numbers play an important role in the strategy for the game [[Kayles]].<ref>{{citation
 | last = Guy | first = Richard K. | author-link = Richard K. Guy
 | contribution = Impartial games
 | location = Cambridge
 | mr = 1427957
 | pages = 61–78
 | publisher = Cambridge Univ. Press
 | series = Math. Sci. Res. Inst. Publ.
 | title = Games of no chance (Berkeley, CA, 1994)
 | volume = 29
 | year = 1996}}. See in particular [https://books.google.com/books?id=cYB-ra2T8i4C&pg=PA68 p.&nbsp;68].</ref> The [[parity function]] maps a number to the number of 1's in its binary representation, [[modular arithmetic|modulo 2]], so its value is zero for evil numbers and one for odious numbers.  The [[Thue–Morse sequence]], an infinite sequence of 0's and 1's, has a 0 in position ''i'' when ''i'' is evil, and a 1 in that position when ''i'' is odious.<ref>{{citation|title=Evil twins alternate with odious twins|first=Chris|last=Bernhardt|journal=Mathematics Magazine|volume=82|issue=1|year=2009|pages=57–62|jstor=27643161|doi=10.4169/193009809x469084|url=https://digitalcommons.fairfield.edu/content_policy.pdf}}.</ref>

==Additional applications==
In [[information theory]], a [[parity bit]] appended to a binary number provides the simplest form of [[error detecting code]]. If a single bit in the resulting value is changed, then it will no longer have the correct parity: changing a bit in the original number gives it a different parity than the recorded one, and changing the parity bit while not changing the number it was derived from again produces an incorrect result. In this way, all single-bit transmission errors may be reliably detected.<ref>{{citation|title=A Student's Guide to Coding and Information Theory|first1=Stefan M.|last1=Moser|first2=Po-Ning|last2=Chen|publisher=Cambridge University Press|year=2012|isbn=9781107015838|pages=19–20|url=https://books.google.com/books?id=gFhJXsGXNj8C&pg=PA19}}.</ref> Some more sophisticated error detecting codes are also based on the use of multiple parity bits for subsets of the bits of the original encoded value.<ref>{{citation|title=Codes and turbo codes|first=Claude|last=Berrou|publisher=Springer|year=2011|isbn=9782817800394|page=4|url=https://books.google.com/books?id=ZLPWNq8JN9QC&pg=PA4}}.</ref>

In [[wind instrument]]s with a cylindrical bore and in effect closed at one end, such as the [[clarinet]] at the mouthpiece, the [[harmonic]]s produced are odd multiples of the [[fundamental frequency]]. (With cylindrical pipes open at both ends, used for example in some [[organ stop]]s such as the [[Flue pipe#Diapasons|open diapason]], the harmonics are even multiples of the same frequency for the given bore length, but this has the effect of the fundamental frequency being doubled and all multiples of this fundamental frequency being produced.) See [[harmonic series (music)]].<ref>{{citation|title=An Introduction to Acoustics|first=Robert H.|last=Randall|publisher=Dover|year=2005|isbn=9780486442518|page=181|url=https://books.google.com/books?id=l9pO7vAvLpUC&pg=PA181}}.</ref>

In some countries, [[house numbering]]s are chosen so that the houses on one side of a street have even numbers and the houses on the other side have odd numbers.<ref>{{citation|title=GIS and Public Health|edition=2nd|first1=Ellen K.|last1=Cromley|first2=Sara L.|last2=McLafferty|publisher=Guilford Press|year=2011|isbn=9781462500628|page=100|url=https://books.google.com/books?id=LeaEPg9vCrsC&pg=PA100}}.</ref> Similarly, among [[United States numbered highways]], even numbers primarily indicate east–west highways while odd numbers primarily indicate north–south highways.<ref>{{citation|title=The Big Roads: The Untold Story of the Engineers, Visionaries, and Trailblazers Who Created the American Superhighways|first=Earl|last=Swift|publisher=Houghton Mifflin Harcourt|year=2011|isbn=9780547549132|page=95|url=https://books.google.com/books?id=59dQ_rwoh3UC&pg=PA95}}.</ref> Among airline [[flight number]]s, even numbers typically identify eastbound or northbound flights, and odd numbers typically identify westbound or southbound flights.<ref>{{citation|title=Southwest Airlines|series=Corporations that changed the world|first=Chris|last=Lauer|publisher=ABC-CLIO|year=2010|isbn=9780313378638|page=90|url=https://books.google.com/books?id=NpZbEihL0ZgC&pg=PA90}}.</ref>

== See also ==
* [[Divisor]]
* [[Half-integer]]

==References==
{{reflist|30em}}

[[Category:Parity (mathematics)| ]]
[[Category:Elementary arithmetic]]