How small can a multiplicative group be?
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.
The post How small can a multiplicative group be? first appeared on John D. Cook.