Cyclic number (group theory)
Encyclopedia
A cyclic number is a natural number
n such that n and φ(n) are coprime
. Here φ is Euler's totient function
. An equivalent definition is that a number n is cyclic iff
any group
of order
n is cyclic
.
Any prime number
is clearly cyclic. All cyclic numbers are square-free
.
Let n = p1 p2 … pk where the pi are distinct primes, then φ(n) = (p1 - 1)(p2 - 1)…(pk - 1). If no pi divides any (pj - 1), then n and φ(n) have no common (prime) divisor, and n is cyclic.
The first cyclic numbers are 1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, … .
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
n such that n and φ(n) are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
. Here φ is Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
. An equivalent definition is that a number n is cyclic iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
any group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of order
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
n is cyclic
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
.
Any prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
is clearly cyclic. All cyclic numbers are square-free
Square-free integer
In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
.
Let n = p1 p2 … pk where the pi are distinct primes, then φ(n) = (p1 - 1)(p2 - 1)…(pk - 1). If no pi divides any (pj - 1), then n and φ(n) have no common (prime) divisor, and n is cyclic.
The first cyclic numbers are 1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, … .