Editing Group (mathematics) (section)

=== Modular arithmetic ===
{{Main|Modular arithmetic}}

[[File:Clock group.svg|thumb|right|The hours on a clock form a group that uses [[Modular arithmetic|addition modulo]]&nbsp;12. Here, {{nowrap|9 + 4 ≡ 1}}.|alt=The clock hand points to 9 o'clock; 4 hours later it is at 1 o'clock.]]
Modular arithmetic for a ''modulus'' <math>n</math> defines any two elements <math>a</math> and <math>b</math> that differ by a multiple of <math>n</math> to be equivalent, denoted by {{tmath|1= a \equiv b\pmod{n} }}. Every integer is equivalent to one of the integers from <math>0</math> to {{tmath|1= n-1 }}, and the operations of modular arithmetic modify normal arithmetic by replacing the result of any operation by its equivalent [[representative (mathematics)|representative]]. Modular addition, defined in this way for the integers from <math>0</math> to {{tmath|1= n-1 }}, forms a group, denoted as <math>\mathrm{Z}_n</math> or {{tmath|1= (\Z/n\Z,+) }}, with <math>0</math> as the identity element and <math>n-a</math> as the inverse element of {{tmath|1= a }}.

A familiar example is addition of hours on the face of a [[12-hour clock|clock]], where 12 rather than 0 is chosen as the representative of the identity. If the hour hand is on <math>9</math> and is advanced <math>4</math> hours, it ends up on {{tmath|1= 1 }}, as shown in the illustration. This is expressed by saying that <math>9+4</math> is congruent to <math>1</math> "modulo {{tmath|1= 12 }}" or, in symbols,
<math display=block>9+4\equiv 1 \pmod{12}.</math>

For any prime number {{tmath|1= p }}, there is also the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{tmath|1= p }}]].{{sfn|Lang|2005|loc=Chapter VII}} Its elements can be represented by <math>1</math> to {{tmath|1= p-1 }}. The group operation, multiplication modulo {{tmath|1= p }}, replaces the usual product by its representative, the [[remainder]] of division by {{tmath|1= p }}. For example, for {{tmath|1= p=5 }}, the four group elements can be represented by {{tmath|1= 1,2,3,4 }}. In this group, {{tmath|1= 4\cdot 4\equiv 1\bmod 5 }}, because the usual product <math>16</math> is equivalent to {{tmath|1= 1 }}: when divided by <math>5</math> it yields a remainder of {{tmath|1= 1 }}. The primality of <math>p</math> ensures that the usual product of two representatives is not divisible by {{tmath|1= p }}, and therefore that the modular product is nonzero.{{efn|The stated property is a possible definition of prime numbers. See ''[[Prime element]]''.}} The identity element is represented by&nbsp;{{tmath|1= 1 }}, and associativity follows from the corresponding property of the integers. Finally, the inverse element axiom requires that given an integer <math>a</math> not divisible by {{tmath|1= p }}, there exists an integer <math>b</math> such that 
<math display=block>a\cdot b\equiv 1\pmod{p},</math>
that is, such that <math>p</math> evenly divides {{tmath|1= a\cdot b-1 }}. The inverse <math>b</math> can be found by using [[Bézout's identity]] and the fact that the [[greatest common divisor]] <math>\gcd(a,p)</math> equals&nbsp;{{tmath|1= 1 }}.{{sfn|Rosen|2000|p=54|loc=&nbsp;(Theorem 2.1)}} In the case <math>p=5</math> above, the inverse of the element represented by <math>4</math> is that represented by {{tmath|1= 4 }}, and the inverse of the element represented by <math>3</math> is represented by&nbsp;{{tmath|1= 2 }}, as {{tmath|1= 3\cdot 2=6\equiv 1\bmod{5} }}. Hence all group axioms are fulfilled. This example is similar to <math>\left(\Q\smallsetminus\left\{0\right\},\cdot\right)</math> above: it consists of exactly those elements in the ring <math>\Z/p\Z</math> that have a multiplicative inverse.{{sfn|Lang|2005|loc=§VIII.1|p=292}} These groups, denoted {{tmath|1= \mathbb F_p^\times }}, are crucial to [[public-key cryptography]].{{efn|For example, the [[Diffie–Hellman]] protocol uses the [[discrete logarithm]]. See {{harvnb|Gollmann|2011|loc=§15.3.2}}.}}