A cyclic number is a
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
''n'' such that ''n'' and φ(''n'') are
coprime
In number theory, 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 equiv ...
. Here φ is
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
. 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" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
any
group of
order ''n'' is
cyclic.
Any
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), 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 ...
is clearly cyclic. All cyclic numbers are
square-free.
[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