2
$\begingroup$

I came across this question in my undergraduate maths course. The question is: Find a number n with the property that for any prime $p$, $p \mid n \iff p-1 \mid n$. Prove that your method to find $n$ works.

My solution is to construct $n$ by the following method:

I start guessing $n_0=2$. Since $3$ is prime and $(3-1) \mid 2 \implies 3 \mid 2$, the condition on $n$ forces a factor of $3$, so let $n_1=2\cdot3$. Now the condition forces a factor of $7$. So $n_2=2\cdot3\cdot7$. Again, the condition forces a factor of $43$. Hence $n_3=2\cdot3\cdot7\cdot43=1806$.

$1806$ satifies the requirements, and does not encounter the same problem as the earlier numbers, because $1806+1=1807=13\cdot139$ is composite. Hence $n=1806$.

Question It is quite clear that this number satisfies the property required from the way it is constructed. However, I want to prove that this algorithm will terminate, i.e. Show that the sequence $b_n := a_n +1$ where $a_0=2, a_{n+1}=a_n(a_n+1)$is cannot be prime for all $n$.

Remarks I know that the sequence (b_n) is actually Sylvester's sequence, which has first few values $2, 3, 7, 43, 1807, 3263443, 10650056950807$. But I have not been able to find a proof that Sylvester's sequence isn't all primes.

link: https://en.wikipedia.org/wiki/Sylvester%27s_sequence

Edit

From the comments my question is unclear. I want a proof without actually calculating the sequence starting with $a_0=2$. Here is the revised statement that I want to prove:

Let $a_0$ be a prime number. We construct the sequence $(a_n)$ using the recurrence relation $a_{n+1}=a_n \cdot (a_n+1)$.

Using $(a_n)$, we then construct the sequence $(b_n)$, where $b_n=a_n+1$ for all $n\in \mathbb{N}$. Prove that $b_n$ cannot be prime for all $n$.

$\endgroup$
  • $\begingroup$ Do you mean to say that your recursions will terminate if $a_n$ is not prime for all $n$ ? $\endgroup$ – Ahmad Bazzi Sep 9 '18 at 13:17
  • $\begingroup$ What about p!, where p is a prime? $\endgroup$ – TheOscillator Sep 9 '18 at 13:35
  • 1
    $\begingroup$ Not sure I understand what you're asking. Isn't the fact that 1807 is in the sequence a proof that not all the members are prime? $\endgroup$ – rogerl Sep 9 '18 at 13:42
  • $\begingroup$ @Did It is a two way implication. Because $6|6$ you would need also $7|6$ because $(7-1)|6$ $\endgroup$ – Mark Bennet Sep 9 '18 at 13:53
  • $\begingroup$ @MarkBennet Oops, sorry for the noise. And thanks for notifying me. $\endgroup$ – Did Sep 9 '18 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.