6

I got the correct answer for the following problem by trying all numbers. It's very time consuming. Can anyone tell me whether there is a simple and easy way to solve the problem?

What is the smallest composite number generated by $p^2-p-1$ where p is a prime?

learning
  • 1,749
  • 4
    It is quick if one does it in one's head. To use machinery, note that $4$ times our expression is $(2p-1)^2-5$. If $2p-1$ is divisible by $5$ but not equal to $5$, our number is composite. – André Nicolas Jun 03 '16 at 03:13
  • Whatever you do, I think it's physically impossible to be quicker than writing $p^2 - p - 1 = p(p - 1) - 1$ and performing very modest arithmetic for a handful of primes. – pjs36 Jun 03 '16 at 03:33

1 Answers1

2

Not a complete answer by all means, but a way to make a smart guess:

It is clear that neither $2$ nor $3$ divides $p^2-p-1$ when $p$ is prime. This is because, in $\mathbb{Z}_2$, $p=1$ or $p=0$, which implies $p^2-p-1=1^2-1-1=1$ or $p^2-p-1=0-0-1=1$. The similar computation can be made in $\mathbb{Z}_3$.

Therefore, if we want $p^2-p-1$ to be composite and to be the smaller possible, it is reasonable to try instances where $5$ will be in the factorization. Note that in $\mathbb{Z}_5$, if $p=3$, then $3^2-3-1=9-3-1=0$. Therefore, we can start looking at the numbers which leave remainder $3$ when divided by $5$:

$$3,8,13,18,23...$$ Therefore, it may be a good idea to try out $3$ or $13$. $3$ is readily seen not to work (only because it results exactly in $5$), but $13$ works... this leaves us only to check the (quite small) sample of prime numbers smaller than $13$.

Aloizio Macedo
  • 34,292