# Let $n\in \mathbb{N}, n > 1$ Show that some numbers are coprimes.

Let $$n\in \mathbb{N}, n > 1$$. Show that

$$\{a^2+a-1,a^3+a^2-1,...\}$$

contains an infinite subset $$S$$ s. t. every $$2$$ distinct elements are coprimes.

I don't know how to even approach this.. can you give me some places to start? Attempt:

$$a^3+a^2-1=a(a^2+a-1)+a-1$$. Using Euclid algorithms we determine that:

$$a^2+a-1=(a+2)(a-1)+1\implies (a^3+a^2-1,a^2+a-1)=1$$ so they are relatively prime.

I was thinking of something like this:

Let $$p,q \in\mathbb{N}, p > q > 1$$ then some random elements of that set should be: $$a^p+a^{p-1}-1, a^q+a^{q-1}-1$$. Then we need to show that:

$$(a^p+a^{p-1}-1,a^q+a^{q-1}-1)=1$$

Right?

• Does $a=n$? Also...aren't $a^3+a^2-1$ and $a^2+a-1$ always relatively prime? So just take $S$ to be those two. – lulu Jan 20 at 14:15
• @Peter it's an infinite subset – C. Cristi Jan 20 at 14:20
• We must show that every pair (not only neighboured pairs) are coprime. Moreover, you did not clarify what $n$ is. – Peter Jan 20 at 14:29
• @Dr.Mathva And that is equivalent to proving that $$(a^{n-p}-1,a^{p+1}+a^p-1)=1 \;\;\forall n,p\in \mathbb N : n>p$$ – Servaes Jan 20 at 16:49
• This is a tough problem, and is very similar to an old Romanian problem, I don't remember the year. Read my proof below. By the way, I strongly suggest that for contest problems, you better try AoPS forums, as the people there are, much more comfortable with contest math type of problems, where in here and MathOverFlow, the value of these elegant problems are underestimated. – Kawa Jan 20 at 21:44

Nice problem.

Here it is. Let $$a_k=a^k+a^{k-1}-1$$. We will construct such a set inductively. First, take any $$k_1$$, and add $$a_{k_1}$$ to the list. Now, let $$k_2=\phi(a_{k_1})$$, where $$\phi(\cdot)$$ is the Euler's totient function. Since $$(a,a_k)=1$$ for every $$k$$, it follows from Euler's theorem that, $$a^{k_2+1}+a^{k_2}-1\equiv a\pmod{a_{k_1}}$$, which is coprime with $$a_{k_1}$$, as $$a$$ is coprime with $$a_{k_1}$$.

Now, having constructed this set up to its $$n^{th}$$ element, that is, $$S\supset \{a_{k_1},a_{k_2},\dots,a_{k_n}\}$$, we now search for an $$k_{n+1}$$ so that, $$(a_{k_{n+1}},a_{k_i})=1$$ for each $$1\leq i \leq n$$. To do so, it suffices to select $$k_{n+1}=\phi(a_{k_1})\cdots \phi(a_{k_n})$$.

This is not an answer, as John Omielen commented below. It just responded Peter's comment in the question by proving that as polynomials in $$a$$, the elements in the set are pairwise coprime. I do not see a direct proof of the original question from this fact.

By the Euclid algorithm, for any pair of natural numbers $$p > q$$,

\begin{aligned} \gcd(a^{p+1} + a^p - 1, a^{q+1} + a^q - 1) &= \gcd(a^{p+1} + a^p - 1 - a^{p-q}(a^{q+1} + a^q - 1)), a^{q+1} + a^q - 1)\\ &= \gcd(a^{p-q}-1, a^{q+1} + a^q - 1). \end{aligned}

Taking them as polynomials in $$a$$, if the g.c.d. is not 1, then there is an element $$\xi \in \mathbb C$$ such that

\begin{aligned} \xi^{p-q} &= 1;\\ \xi^{q+1} + \xi ^q &= 1. \end{aligned}

The first equation tells that $$\xi$$ is a root of unity, and the second equation tells us that $$\xi^{q+1}$$ and $$\xi$$ lies on the unit circle on the complex plane, and the angle between them and the origin is $$120^\circ$$. The only chance for this to be true is $$\xi$$ be a primitive root of unity. But in this case $$\xi^{q+1} + \xi^q = -\xi^{q-1} \neq 1$$.

Therefore, $$\gcd(a^{p+1} + a^p - 1, a^{q+1} + a^q - 1) = 1$$ for all $$p \neq q$$.

• Thank you for pointing out. The purpose of this was to reply Peter’s comments on the relative primality of the sequence as polynomials in $a$. I thought it was sufficient but it was not. Maybe I will delete my post later. – Hw Chu Jan 21 at 2:41
• You are welcome. As you have explicitly addressed my concerns stated in my comment at the top of your answer, I have deleted my original comment as I don't believe it's needed any more. – John Omielan Jan 22 at 9:12