# What is the maximum number of distinct GCDs you can make out of a set of integers?

With $N$ integers, how many different GCDs can you make by taking subsets of them? More formally:

Let $S$ be a set of non-negative integers.

Define $G(S)$ as $\{gcd(T) : T \subseteq S \}$

Define $f(N)$ as $\max_{|S| = N} \{|G(S)|\}$

For example:

• $f(0) = 1$
• $f(1) = 2$
• $f(2) = 4$ (e.g. $S = \{4, 6\}$, $G(S) = \{0, 2, 4, 6\}$)
• $f(3) = 8$ (e.g. $S = \{12, 20, 30\}$, $G(S) = \{0, 2, 4, 6, 10, 12, 20, 30\}$)

Is it the case that $f(N) = 2^N$?

• Does it really make sense to say that $gcd(\emptyset)=1$? – David Cohen May 27 '13 at 20:02
• @David Cohen No, $gcd(\emptyset)=0$. $gcd(X)$ is “the” integer generating the (principal) ideal generated by the set $X$. The empty set generates the zero ideal, which is generated by the zero. Thus $f(1)=|G(\{1\})|=|\{0,1\}|$. – The User May 27 '13 at 20:16
• Well, actually that is more a comment for wjomlex. However, it does not really matter. – The User May 27 '13 at 20:18
• Ah, you're right, sorry. It should definitely be 0. I'll fix it up. – wjomlex May 27 '13 at 20:36

Yes, it is possible for each subset to have a different gcd, giving $2^{N}$ distinct gcds.
Let $\mathcal{P}$ be the set consisting of the first $N$ odd primes and let $P$ be the product of the first $N$ odd primes. Then if $S = \lbrace \frac{2P}{q} : q\in \mathcal{P}\rbrace$, each subset $T\subset S$ has a unique gcd, (we can recover $T$ from its gcd $x$ by seeing which primes do not divide $x$. I.e., $\frac{2P}{q}\in T\Leftrightarrow q\nmid x$.)
(The factor of $2$ takes care of the weird convention that $gcd(\emptyset)=1$, otherwise the empty set and the whole set would have the same gcd.)
Yes. Let $p_1,\dots,p_{N+1}$ be distinct primes, and let $S$ be the set of numbers that are products of $N-1$ of $p_1,\dots,p_N$ times $p_{N+1}$. Then $G(S)$ is the set of numbers that are products of up to $N-1$ of $p_1,\dots p_N$ time $p_{N+1}$, and also $1$. This has $2^N$ elements.