Modular arithmetic Modular multiplicative inverse

for given positive integer m, 2 integers, , b, said congruent modulo m if m divides difference. binary relation denoted by,

a
≡
b


(
mod

m
)

.


{\displaystyle a\equiv b{\pmod {m}}.}

this equivalence relation on set of integers, ℤ, , equivalence classes called congruence classes modulo m or residue classes modulo m. let





a
¯




{\displaystyle {\overline {a}}}

denote congruence class containing integer a, then

a
¯


=
{
b
∈

z

∣
a
≡
b


(
mod

m
)

}
.


{\displaystyle {\overline {a}}=\{b\in \mathbb {z} \mid a\equiv b{\pmod {m}}\}.}

a linear congruence modular congruence of form

a
x
≡
b


(
mod

m
)

.


{\displaystyle ax\equiv b{\pmod {m}}.}

unlike linear equations on reals, linear congruences may have zero, 1 or several solutions. if x solution of linear congruence every element in





x
¯




{\displaystyle {\overline {x}}}

solution, so, when speaking of number of solutions of linear congruence referring number of different congruence classes contain solutions.

if d greatest common divisor of , m linear congruence ax ≡ b (mod m) has solutions if , if d divides b. if d divides b, there d solutions.

a modular multiplicative inverse of integer respect modulus m solution of linear congruence

a
x
≡
1


(
mod

m
)

.


{\displaystyle ax\equiv 1{\pmod {m}}.}

the previous result says solution exists if , if gcd(a, m) = 1, is, , m must relatively prime (i.e. coprime). furthermore, when condition holds, there 1 solution, i.e., when exists, modular multiplicative inverse unique.

when ax ≡ 1 (mod m) has solution denoted in way −

x
≡

a

−
1




(
mod

m
)

,


{\displaystyle x\equiv a^{-1}{\pmod {m}},}

but abuse of notation since modular multiplicative inverse integer , not integer when integer other 1 or - 1. notation proper if interpreted token standing congruence class





a
¯




{\displaystyle {\overline {a}}}

, multiplicative inverse of congruence class congruence class multiplication defined in next section.

integers modulo m

the congruence relation, modulo m, partitions set of integers m congruence classes. operations of addition , multiplication can defined on these m objects in following way: either add or multiply 2 congruence classes, first pick representative (in way) each class, perform usual operation integers on 2 representatives , take congruence class result of integer operation lies in result of operation on congruence classes. in symbols,




+

m




{\displaystyle +_{m}}

,




⋅

m




{\displaystyle \cdot _{m}}

representing operations on congruence classes, these definitions are

a
¯



+

m




b
¯


=



a
+
b

¯




{\displaystyle {\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}}

and

a
¯



⋅

m




b
¯


=



a
b

¯


.


{\displaystyle {\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.}

these operations well-defined, meaning end result not depend on choices of representatives made obtain result.

the m congruence classes these 2 defined operations form ring, called ring of integers modulo m. there several notations used these algebraic objects,




z


/

m

z



{\displaystyle \mathbb {z} /m\mathbb {z} }

or




z


/

m


{\displaystyle \mathbb {z} /m}

, several elementary texts , application areas use simplified notation





z


m




{\displaystyle \mathbb {z} _{m}}

when confusion other algebraic objects unlikely.

the congruence classes of integers modulo m traditionally known residue classes modulo m, reflecting fact elements of congruence class have same remainder (i.e., residue ) upon being divided m. set of m integers selected each comes different congruence class modulo m called complete system of residues modulo m. division algorithm shows set of integers, {0, 1, 2, ..., m − 1} form complete system of residues modulo m, known least residue system modulo m. in working arithmetic problems more convenient work complete system of residues , use language of congruences while @ other times point of view of congruence classes of ring




z


/

m

z



{\displaystyle \mathbb {z} /m\mathbb {z} }

more useful.

multiplicative group of integers modulo m

not every element of complete residue system modulo m has modular multiplicative inverse, instance, 0 never does. after removing elements of complete residue system not relatively prime m, left called reduced residue system, of elements have modular multiplicative inverses. number of elements in reduced residue system



ϕ
(
m
)


{\displaystyle \phi (m)}

,



ϕ


{\displaystyle \phi }

euler totient function, i.e., number of positive integers less m relatively prime m.

in general ring unity not every element has multiplicative inverse , called units. product of 2 units unit, units of ring form group, group of units of ring , denoted r if r name of ring. group of units of ring of integers modulo m called multiplicative group of integers modulo m, , isomorphic reduced residue system. in particular, has order (size),



ϕ
(
m
)


{\displaystyle \phi (m)}

.

in case m prime, p,



ϕ
(
p
)
=
p
−
1


{\displaystyle \phi (p)=p-1}

, non-zero elements of




z


/

p

z



{\displaystyle \mathbb {z} /p\mathbb {z} }

have multiplicative inverses,




z


/

p

z



{\displaystyle \mathbb {z} /p\mathbb {z} }

finite field. in case, multiplicative group of integers modulo p form cyclic group of order p − 1.