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.