Wolfram Alpha:
Search by keyword:
Astronomy
Chemistry
Classical Mechanics
Classical Physics
Climate Change
Cosmology
Finance and Accounting
Game Theory
General Relativity
Group Theory
Lagrangian and Hamiltonian Mechanics
Macroeconomics
Mathematics
Microeconomics
Nuclear Physics
Particle Physics
Probability and Statistics
Programming and Computer Science
Quantum Computing
Quantum Field Theory
Quantum Mechanics
Semiconductor Reliability
Solid State Electronics
Special Relativity
Statistical Mechanics
String Theory
Superconductivity
Supersymmetry (SUSY) and Grand Unified Theory (GUT)
The Standard Model
Topology
Units, Constants and Useful Formulas
The Integers Modulo n Under + and x
-----------------------------------
The integers modulo n under addition are written
as ℤ/nℤ (or simply ℤ_{n}) and the integers modulo
n under multiplication are written as (ℤ_{n}/nℤ)^{x}
(or (ℤ_{n})^{x}).
Every ℤ/nℤ forms a finite cyclic group. However,
not every (ℤ/nℤ)^{x} does. Gauss showed that (ℤ/nℤ)^{x}
forms a cyclic group if and only if n is 1, 2, 4,
a power of an odd prime, or twice a power of an
odd prime.
p = 2, 3, 5, 7, 11, 13, 17, ...
2p = 4, 6, 10, 14, 22, 26, 34, ...
Therefore, for example, the group (ℤ_{8})^{x} is not
cyclic. This is the KLEIN GROUP.
All cyclic groups are abelian.
Cyclic Groups
-------------
A group G is cyclic if there exists an element
g ∈ G such that:
Multiplicative: G = {g^{n}|n ∈ Z}
= {1,g,g^{2},g^{3},...,g^{n-1}}
Additive: G = {ng|n ∈ Z}
= {0,g,2g,3g,...,(n - 1)g}
In the literature {g^{n}|n ∈ Z} is normally used
to describe both situations where g^{n} implies
ng in the additive case.
g is referred to as the GROUP GENERATOR. It
is denoted by <g>.
Cyclic Subgroups
----------------
If G is a group and g ∈ G then <g> is a subgroup
of G. Furthermore, the subgroup is also cyclic.
This should be obvious given the definition of a
cyclic group. Because cyclic groups are abelian,
their subgroups are normal subgroups.
Example
-------
Consider the group ℤ/6ℤ under +.
ℤ_{6} = {0,1,2,3,4,5}
The Cayley table for mod 6 is:
+ | 0 1 2 3 4 5
--+----------------
0 | 0 1 2 3 4 5
1 | 1 2 3 4 5 0
2 | 2 3 4 5 0 1
3 | 3 4 5 0 1 2
4 | 4 5 0 1 2 3
5 | 5 0 1 2 3 4
Therefore, under addition the generators are:
<1> = {1,2,3,4,5,0}
<2> = {2,4,0}
<3> = {0}
<4> = {4,2,0}
<5> = {5,4,3,2,1,0}
<0> = {0}
Therefore, <1> and <5> are both generators
of ℤ_{6}.
{ ...,-3x,-2x,-x,0,x,2x,3x,...} additive
x = 1: { ...,-3,-2,-1,0,1,2,3,...}
x = 5: { ...,-15,-10,-5,0,5,10,15,...} (mod 6)
{ ...,-3,-4,-5,0,5,4,3,...}
Furthermore, each <> is a normal subgroup of ℤ_{6}.
For example, take n = 2 from {2,4,0} and g = 3
from ℤ_{6}.
3 + 2 + (-3) = 2
This is the equivalent of gng^{-1} ∈ N for additive
groups.
Now, let us consider (ℤ/6ℤ)^{x}. The Cayley
table for mod 6 is:
x | 0 1 2 3 4 5
--+-----------------
0 | 0 0 0 0 0 0
1 | 0 1 2 3 4 5
2 | 0 2 4 0 2 4
3 | 0 3 0 3 0 3
4 | 0 4 2 0 4 2
5 | 0 5 4 3 2 1
ℤ/6ℤ under + satisfies all the axioms of a group.
The set of number in each row and column in the
table obey the axioms of closure, associativity,
contains the identity 0, and have inverses. However,
this is not the case for (ℤ/6ℤ)^{x}. The element 0
can never have an inverse (0^{-1}·0 = 1 does not exist).
Likewise, the elements 2,3 and 4 also fail to have
an inverse (i.e. x^{-1}·x = 1 does not exist in each
case). Therefore, as it stands (ℤ/6ℤ)^{x} is not a
group.
One method to make (ℤ/6ℤ)^{x} a group is to only
consider the subset of elements that do have
inverses. These elements are called UNITS. The
multiplication table then reduces to:
x | 1 5
--+------
1 | 1 5
5 | 5 1
Therefore, (ℤ/6ℤ)^{x} = {1,5} with 5 as its generator,
i.e.
<5> = {1,5,25,125,625,...} mod 6
= {1,5,1,5,....}
Greatest Common Divisor, gcd(n,k)
---------------------------------
The gcd(n,k) is the largest positive integer that
divides each of the integers n and k. For (ℤ/6ℤ)^{x}
the gcd's are:
gcd(6,1) = 1
gcd(6,2) = 2
gcd(6,3) = 3
gcd(6,4) = 2
gcd(6,5) = 1
gcd(6,6) = 6
Two numbers are called relatively prime, or
coprime, if their greatest common divisor equals
1.
Units Modulo n
--------------
For a given integer, n, with 1 ≤ m < n and
gcd(n,m) = 1 the set of all integers m forms
a group denoted U(n) called the UNITS MODULO n.
Euler's Totient Function, φ(n)
------------------------------
ETF counts the positive integers up to a given
integer n that are relatively prime to n. More
precisely,
|(ℤ/nℤ)^{x}| = φ(n) = number of coprimes of n
Coprimes of 6 = 1,5 ∴ φ(6) = 2
Coprimes of 8 = 1,3,5,7 ∴ φ(8) = 4
(ℤ/7ℤ)^{x}
-------
If we were to go through the identical procedure
for (ℤ/7ℤ)^{x} we would find:
<3> = {1,3,2,6,4,5}
<5> = {1,5,4,6,2,3}
So (ℤ/7ℤ)^{x} is isomorphic to ℤ/6ℤ.