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$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Let $a_1\gt 1$, and let $a_{n+1}=a_n^2-a_n+1$. $\endgroup$– André NicolasJun 7, 2015 at 22:54
-
$\begingroup$ @AndréNicolas what is $a_n$? $\endgroup$– GuPeJun 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$– André NicolasJun 7, 2015 at 23:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Jun 7, 2015 at 23:59