# Thread: Sequence of natural numbers

1. ## Sequence of natural numbers

The sequence $a_1,a_2, \cdots$ of natural numbers satisfies $\text{GCD}(a_i,a_j) = \text{GCD}(i,j)$ for all $i \neq j$. Prove that $a_i=i \ \forall \ i$

Can anyone show me a full solution to this question? (I'm quite noob at number theory since I just started it, please don't leave out any steps!!)

2. Originally Posted by usagi_killer
The sequence $a_1,a_2, \cdots$ of natural numbers satisfies $\text{GCD}(a_i,a_j) = \text{GCD}(i,j)$ for all $i \neq j$. Prove that $a_i=i \ \forall \ i$

Can anyone show me a full solution to this question? (I'm quite noob at number theory since I just started it, please don't leave out any steps!!)
$a_i=i \ \forall \ i$

What does above mean plz? Is it a std notation?

3. Originally Posted by usagi_killer
The sequence $a_1,a_2, \cdots$ of natural numbers satisfies $\text{GCD}(a_i,a_j) = \text{GCD}(i,j)$ for all $i \neq j$. Prove that $a_i=i \ \forall \ i$

Can anyone show me a full solution to this question? (I'm quite noob at number theory since I just started it, please don't leave out any steps!!)
The number 1 has the property that GCD(1,j) = 1 for all j, and it is the only number with that property. Therefore $\displaystyle a_1=1$.

The number 2 has the property that GCD(2,j) = 1 or 2 for all j, and it is the only number with that property. Therefore $\displaystyle a_2=2$.

Can you continue that line of reasoning?

4. Thanks for that, but I have no idea how to complete the proof... could you please show me?

thanks again.

5. Use proof by induction.

6. Originally Posted by Opalg
The number 1 has the property that GCD(1,j) = 1 for all j, and it is the only number with that property. Therefore $\displaystyle a_1=1$.
I'm probably missing something here, but does that not only tell you that $\displaystyle a_1$ is coprime to all the other terms in the sequence and is the only term in the sequence with this property?

CB

7. Originally Posted by CaptainBlack
I'm probably missing something here, but does that not only tell you that $\displaystyle a_1$ is coprime to all the other terms in the sequence and is the only term in the sequence with this property
No, it was me missing something (misreading the question, as so often). I was thinking that the sequence was meant to be a permutation of the natural numbers. But the question does not say that, so it is harder than I first thought. I doubt whether I'll have time to reconsider it on Christmas Day however.

8. I think I got it:

First assume $a_i \neq i$

Therefore for some $i$, let's call it $m$, $a_m \neq m$

$\implies (a_m, a_{2m}) = (m,2m) = m$

$\implies \frac{a_m}{m} = k$ for some $k$

$\therefore a_m = km$

Now $(a_{km}, a_{2km}) = (km,2km) = km$

$\therefore km | a_{km} \implies a_m | a_{km}$

$\implies (a_m, a_{km}) = a_m = km$

But $(a_m, a_{km}) = (m, km) = m$ Contradiction!

Thus $a_m = m$ so $a_i = i \ \blacksquare$