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]

n/\varphi(n) \leq e^\gamma \log \log n + 5/(2 \log \log n)

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.

Leave a Reply

Your email address will not be published. Required fields are marked *