In number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, a branch of mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a highly cototient number is a positive integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 k which is above one and has more solutions to the equation

Equation

An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...

x − φ(x) = k,

than any other integer below k and above one. 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...

. There are infinitely many solutions to the equation for k = 1 so this value is excluded in the definition. The first few highly cototient numbers are:

2, 4, 8, 23

23 (number)

23 is the natural number following 22 and preceding 24.- In mathematics :Twenty-three is the ninth prime number, the smallest odd prime that is not a twin prime. Twenty-three is also the fifth factorial prime, the third Woodall prime...

, 35

35 (number)

35 is the natural number following 34 and preceding 36.- In mathematics :35 is the sum of the first five triangular numbers, making it a tetrahedral number....

, 47

47 (number)

47 is the natural number following 46 and preceding 48.-In mathematics:Forty-seven is the fifteenth prime number, a safe prime, the thirteenth supersingular prime, and the sixth Lucas prime. Forty-seven is a highly cototient number...

, 59

59 (number)

59 is the natural number following 58 and preceding 60.-In mathematics:Fifty-nine is the 17th smallest prime number. The next is sixty-one, with which it comprises a twin prime. 59 is an irregular prime, a safe prime and the 14th supersingular prime. It is an Eisenstein prime with no imaginary...

, 63

63 (number)

63 is a natural number following 62 and preceding 64.-In mathematics:Although a number of the form 2n - 1, 63 is not a Mersenne prime since n is not prime and 63 is certainly not prime either. It is a Woodall number and a Harshad number. It is a highly cototient number. It is a repdigit in base 4...

, 83

83 (number)

83 is the natural number following 82 and preceding 84.-In mathematics:Eighty-three is the sum of three consecutive primes as well as the sum of five consecutive primes ....

, 89, 113

113 (number)

113 is the natural number following 112 and preceding 114.-In mathematics:One hundred [and] thirteen is the 30th prime number, following 109 and preceding 127, a Sophie Germain prime, a Chen prime and a Proth prime as it is a prime number of the form 7 × 24 + 1...

, 119

119 (number)

119 is the natural number following 118 and preceding 120.- Mathematics :* 119 is a Perrin number, preceded in the sequence by 51, 68, 90 ....

, 167

167 (number)

167 is the natural number following 166 and preceding 168.-In mathematics:* 167 is an odd number* 167 is a Chen prime, since the next odd number, 169, is a square of a prime...

, 209

209 (number)

209 is the natural number following 208 and preceding 210. It is written as "two hundred and nine".-In mathematics:* 209 is a highly cototient number* 209 is a Harshad number* 209 is a self number* 209=16+25+34+43+52+61-In other fields:...

, 269

269 (number)

269 is the natural number between 268 and 270. It is also a prime number.-In mathematics:269 is a regular prime, an Eisenstein prime with no imaginary part, a long prime, a Chen prime, a Pillai prime, a Pythagorean prime, a twin prime, a sexy prime, a Higgs prime, a strong prime, and a highly...

, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889 .

There are many odd highly cototient numbers. In fact, after 8, all the numbers listed above are odd, and after 167 all the numbers listed above are congruent to 9 modulo

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

 10.

The concept is somewhat analogous to that of highly composite number

Highly composite number

A highly composite number is a positive integer with more divisors than any positive integer smaller than itself.The initial or smallest twenty-one highly composite numbers are listed in the table at right....

s. Just as there are infinitely many highly composite numbers, there are also infinitely many highly cototient numbers. Computations become harder, since integer factorization

Integer factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

 does, as the numbers get larger.

Primes

The first few highly cototient numbers which are primes

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...

are

2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839.