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 '15 at 22:54
  • $\begingroup$ @AndréNicolas what is $a_n$? $\endgroup$ Jun 7 '15 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 '15 at 23:44
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$

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.