2
$\begingroup$

The question is,

Let $a_k$ be a countably infinite sequence of positive numbers st. $\gcd(a_1,a_2,...)=1$, does it exist a finite subsequence $a_{i_1},a_{i_2},...,a_{i_n}$ with $\gcd(a_{i_1},a_{i_2},...,a_{i_n})=1$?

or more generally,

Let $a_k$ be a countably infinite sequence of positive numbers st. $\gcd(a_1,a_2,...)=d$, does it exist a finite subsequence $a_{i_1},a_{i_2},...,a_{i_n}$ with $\gcd(a_{i_1},a_{i_2},...,a_{i_n})=d$?

Can anyone help with an elementary proof (pls. do not use advanced number theory stuff) or a counter example? Thank you.

$\endgroup$
3
$\begingroup$

This is a bit of a pedestrian argument, but you asked for one:

Recall that the GCD is $1$ if and only if no prime number divides all $a_i$. The number $a_1$ is divisible by a finite number of primes $p_1, \dots , p_k$. For each $p_j$ there exists some $a_{i_j}$ such that $p_j \nmid a_{i_j} $.

Now note that there is no prime number that divides each of $a_1, a_{i_1}, \dots , a_{i_k}$, and conclude.

(Note that the $a_{i_j}$ are not necessarily distinct.)

$\endgroup$
4
$\begingroup$

Hint: Let $d_n=\gcd(a_1,\dots,a_n)$. Then since $\{d_n\}$ is a non-empty set of positive integers, it must have a least element.

$\endgroup$
  • $\begingroup$ How do you know this least element will be the gcd of all $a_i$? $\endgroup$ – quid Jan 17 '16 at 17:23
  • 1
    $\begingroup$ That's why it is a hint. @quid $\endgroup$ – Thomas Andrews Jan 17 '16 at 17:25
  • 1
    $\begingroup$ Well, yes and no. I think the "least value" is a big part of the "trick." Also, restricting it to just the case $a_1,\dots,a_n$ rather than arbitrary subsets, makes it easier to write :) @quid $\endgroup$ – Thomas Andrews Jan 17 '16 at 17:26
  • 1
    $\begingroup$ Of course I thought about it. I wondered what I could give that would not give away the whole answer. I wrote the word "hint." What makes you think I wasn't aware this was not a complete proof? I actually wondered if it was too big a hint. @quid $\endgroup$ – Thomas Andrews Jan 17 '16 at 17:36
  • 1
    $\begingroup$ Perhaps you just don't realize how trivial the rest of the proof is from this start? @quid $\endgroup$ – Thomas Andrews Jan 17 '16 at 17:54

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.