1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Does it really make sense to say that $gcd(\emptyset)=1$? $\endgroup$ – David Cohen May 27 '13 at 20:02
  • 2
    $\begingroup$ @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\}|$. $\endgroup$ – The User May 27 '13 at 20:16
  • $\begingroup$ Well, actually that is more a comment for wjomlex. However, it does not really matter. $\endgroup$ – The User May 27 '13 at 20:18
  • $\begingroup$ Ah, you're right, sorry. It should definitely be 0. I'll fix it up. $\endgroup$ – wjomlex May 27 '13 at 20:36
11
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.