# Checking whether a number is prime or not

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.

• But $18|198$ and $18$ is not prime. – saulspatz Nov 19 '18 at 12:27
• en.wikipedia.org/wiki/… – lab bhattacharjee Nov 19 '18 at 12:31
• @Russ No, $71$ works. Note: it's easy to avoid overflow here, at least for a specific prime. The sequence $L_n$ is defined by $L_0=2,L_1=1, L_n=L_{n-1}+L_{n-2}$. If you are interested in $p=71$ then you can just compute this $\pmod {71}$ for which all the numbers are small. We get $L_{71}\equiv 1 \pmod {71}$. as desired. (the numbers we are checking are $L_n-1$) – lulu Nov 19 '18 at 12:47
• Thanks, @lulu. One important point to the original poster - the "only if" part is not necessarily true; per Robert Z's answer below, 705 passes the test, but is not prime. Otherwise, this would be a deterministic test of primes, right? – Russ Nov 19 '18 at 12:50
• @Russ Yes, that's my understanding. – lulu Nov 19 '18 at 12:52

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.

• "... is divisible by $p^2$" by $p^2$ or by $p$? Note that $198$ is not divisible by $11^2=121$ – Hussain-Alqatari Nov 19 '18 at 12:35
• @Hussain-Alqatari Sorry, you are right! – Robert Z Nov 19 '18 at 12:37
• @Hussain-Alqatari I edited my answer with the proof of the implication that holds.. – Robert Z Nov 19 '18 at 12:55
• Nice. Also note that the Bruckman definition for Lucas pseudoprimes is not used outside of his paper (Baillie and Wagstaff defined them over a decade earlier). Bruckman's pseudoprimes overlap substantially with strong pseudoprimes, so are not very useful for primality testing, unlike the earlier definition which is used in the very common BPSW primality test. – DanaJ Nov 19 '18 at 22:14

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.)