2
$\begingroup$

If I have a composite odd number $p_1$, then adding $2$ to $p_1$ will make it a number that is either a prime or that shares none of its factors: $p_2$. If I have the equation $p_1+2=p_2$ and I can make a new number, $p_3=p_2+2$ that will therefore not share any of the factors of $p_1$ or $p_2$, my question is: is there a way to do this to an arbitrary number, such that $p_n$ will share none of the factors of any $p_i$ with $i<n$?

$\endgroup$
3
  • 1
    $\begingroup$ Let $a_1\gt 1$, and let $a_{n+1}=a_n^2-a_n+1$. $\endgroup$ Jun 7, 2015 at 22:54
  • $\begingroup$ @AndréNicolas what is $a_n$? $\endgroup$
    – GuPe
    Jun 7, 2015 at 23:10
  • $\begingroup$ I could have called it $p_n$ like in your post, but $p_n$ has a standard meaning in number theory (the $n$-th prime) so I avoided using it for something else. $\endgroup$ Jun 7, 2015 at 23:44

1 Answer 1

1
$\begingroup$

I interpret your question as follows. We are given a number $a_1\gt 1$, and want to produce a sequence $a_1,a_2,a_3,a_4,\dots$ such that for all $i$ and $n$, with $i\lt n$, the numbers $a_i$ and $a_n$ have no common factor greater than $1$.

We describe a recurrence that produces such a sequence. For $j\ge 1$, let $a_{j+1}=a_j^2-a_j+1$.

Note that $a_{i+1}\equiv 1\pmod{a_i}$. It follows that $$a_{i+2}=a_{i+1}^2-a_{i+1}+1\equiv 1^2-1+1\equiv 1\pmod{a_i}.$$ But then by the same reasoning $$a_{i+3}=a_{i+2}^2-a_{i+2}+1\equiv 1\pmod{a_i}.$$ And so on forever.

In particular, if $n\gt i$, then $a_n\equiv 1\pmod{a_i}$ and therefore $a_i$ and $a_n$ have no common divisor greater than $1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .