The previous post looked at the multiplicative group of integers modulo a number of the form *n* = *pq* where *p* and *q* are prime. This post looks at general *n*.

The multiplicative group mod *n* consists of the integers from 1 to *n*-1 that are relative prime to *n*. So the size of this group is φ(*n*) where φ is Euler’s “totient” function.

If *n* is a large number, how large might the multiplicative group of integers mod *n* be? Or equivalently, what can we say about the size of φ(*n*)?

Upper bounds are easy. If *n* is prime, then φ(*n*) is *n*-1, and so for large *n*, φ(*n*) can be essentially as large as *n*. The more interesting question is how small φ(*n*) can be.

The following lower bound comes from [1]. Theorem 15 from that reference says that for *n* > 2, we have [2]

Taking the reciprocal of both sides, we have a lower bound on the ratio of φ(*n*) to *n*.

We can use this to show that if *n* is a *k*-bit number, with *k* somewhere in the thousands, then φ(*n*) is at least a *k*-4 bit number.

## Related posts

[1] J. Barkley Rosser, Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math. 6(1): 64-94 (March 1962). DOI: 10.1215/ijm/1255631807

[2] Except when

*n* = 223092870 = 2×3×5×7×11×13×17×19×23,

the product of the first nine primes. With this value of *n*, φ(*n*)/*n* = 0.1636.