Checking whether a number is prime or not

Question

Is it true that a natural number $n>1$ is prime if and only if $n|\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n-1$?

We know that $11$ is a prime number, but let us assume that we do not know, and let us also assume that the statement is true;

$$\left ( \frac{1+\sqrt{5}}{2} \right )^{11}+\left ( \frac{1-\sqrt{5}}{2} \right )^{11}-1=198.$$

Clearly, $11|198$. Therefore, as our assumption that the statement is true, the number $11$ is a prime number.

Answer 1

Note that $\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n$ is the $n$-th Lucas number.

It is true that if $p$ is a prime then $L_p-1$ is divisible by $p$: $2$ divides $L_2-1=2$ and for any prime $p>2$, $$L_p-1=\frac{1}{2^{p-1}}\sum_{k=1}^{(p-1)/2}\binom{p}{2k}5^k=0\pmod{p}$$ because $p$ divides each $\binom{p}{2k}$.

On the contrary $705$ is not a prime but it divides $L_{705}-1$.

See Bruckman-Lucas_pseudoprimes and compare with the Wall-Sun-Sun prime.

Answer 2

Note that the Bruckman-Lucas criterion is a partial, special case of the family of Lucas sequence tests described by Baillie and Wagstaff:

Let $P$, $Q$ be integers such that $D := P^2 - 4Q \ne 0, P > 0$. Let $n$ be the natural number to be tested. Define sequences:

$$ U_0 := 0, U_1 := 1, U_{n+2} := PU_{n+1} - QU_n $$

$$ V_0 := 2, V_1 := 1, V_{n+2} := PV_{n+1} - QV_n $$

Now, if $n$ is prime, and coprime with $Q$, then some identities hold, among them:

$$ U_n \equiv \left(\frac{D}{n}\right) \left(mod\ n\right) $$

$$ V_n \equiv P \left(mod\ n\right) $$

If $n$ is an odd natural number and coprime with $P$, $Q$ and $D$, then any two identities imply the others mentioned in the paper (identities (1) through (4)).

Note that for $P=1, Q=-1$ (and hence $D=5$), the $V_n$ test is exactly the same as the Bruckman-Lucas test, but if you check any other identity, and use the divisibility tests mentioned above, some more composites are eliminated, e.g.:

• The first two Bruckman-Lucas PPs, 705 and 2465, are eliminated as divisible by $D=5$.
• The next BLPP, 2737 is eliminated by any other of the listed identities, e.g. $U_{2737} \equiv 1 \left(mod\ 2737\right)$, but $U_{2737}$ should be congruent to $\left(\frac{5}{2737}\right) = -1$.

Also note that I know of two possible ways to calculate the residue of $V_k\ mod\ n$ (i.e. $k$ need not be equal to $n$) efficiently, that is, with O($log\ n$) multiplications and additions, and both of them give you the $U_k$ residue as well with almost no additional effort. Since checking $U_n$, as mentioned above, strengthens the test a fair amount, you should always do that.

Strong tests also choose $P$, $Q$ such that $\left(\frac{D}{n}\right) = -1$. Such can be found for all $n$ that aren't perfect squares (and these can be caught with Heron's square root algorithm). Strong forms are much preferred. In fact, look at Baillie-PSW which combines a strong Fermat-like test with a strong Lucas test and still has no known pseudoprimes.

(Even so, the BL test, like most Lucas sequence tests and most Fermat-like tests, succeeds rarely for large composite $n$. I don't have proof, but numerical evidence strongly suggests that the density of pseudoprimes in all probable primes is zero.)

TL;DR:

• The Bruckman-Lucas test you described is a weak form of a Lucas sequence test checking only $V_n \equiv 1 \left(mod\ n\right)$ for $P = 1$ and $Q = -1$.
• Baillie-PSW is a safe choice usually.
• If you absolutely need a deterministic test, I suggest you to look at APR-CL or AKS. (AKS eventually outperforms APR-CL for very large numbers, both are much slower than probabilistic tests.)