A cyclic number is a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
''n'' such that ''n'' and φ(''n'') are
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
. Here φ is
Euler's totient function. An equivalent definition is that a number ''n'' is cyclic
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
any
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
of
order ''n'' is
cyclic
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in s ...
.
Any
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
is clearly cyclic. All cyclic numbers are
square-free {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
.
[For if some prime square ''p''2 divides ''n'', then from the formula for φ it is clear that ''p'' is a common divisor of ''n'' and φ(''n'').]
Let ''n'' = ''p''
1 ''p''
2 … ''p''
''k'' where the ''p''
''i'' are distinct primes, then φ(''n'') = (''p''
1 − 1)(''p''
2 − 1)...(''p''
''k'' – 1). If no ''p''
''i'' divides any (''p''
''j'' – 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, 37, 41, 43, 47, 51, 53, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 123, 127, 131, 133, 137, 139, 141, 143, 145, 149, ... .
References
{{Classes of natural numbers
Number theory