-3
$\begingroup$

Background and Motivation

The golden ratio, $$ \phi = \frac{1 + \sqrt{5}}{2}, $$ is a well-known irrational constant that appears frequently in geometry, algebra, and in the Fibonacci and Lucas sequences. Though fundamentally irrational and geometric, it surprisingly shows up in discrete number theory as well.

Primality testing, on the other hand, is a central topic in number theory with both theoretical and practical importance, especially in cryptography. Most known primality tests rely on modular arithmetic, integer sequences, or algebraic identities — but very few, if any, directly involve irrational constants like $\phi$.

While experimenting numerically with powers of $\phi$, I noticed an unexpected and elegant pattern. The simplicity and strength of this condition — despite its seemingly irrational origin — suggest a potentially deep connection between the golden ratio and prime numbers, possibly via the Lucas or Fibonacci sequences.

This motivates the following natural questions:

  • Why does this work?
  • Is there a theoretical explanation rooted in recurrence sequences or algebraic number theory?
  • Could this inspire a new class of primality tests?

I am sharing this in hopes of uncovering deeper insights or connections that could explain the phenomenon.

The Golden Ratio Primality Test (GRPT)

If any positive integer $n>5$ is not divisible by $2$ or $5$, and satisfies the condition: $$ \lfloor \phi^n \rfloor \mod n = 1, $$

then,
$$ n \text{ is prime}. $$

Here,

$$ \phi=\frac{1+\sqrt{5}}{2}.$$

Empirical Evidence

I have verified GRPT for the range $5<n\leq 1{,}000{,}000 $ using Wolfram GPT.

No false positives or false negatives found.

Let's see how this applies to the first few $n>5$ (excluding the multiples of $2$ and $5$):

$$\begin{array}{|c|c|c|} \hline n & \lfloor \phi^n \rfloor & \lfloor \phi^n \rfloor \mod n & \\ \hline 7 & 29 & 1 & \text{Prime}\\ \hline 9 & 76 & 4\neq1 & \text{Not prime}\\ \hline 11 & 199 & 1 & \text{Prime}\\ \hline 13 & 521 & 1 & \text{Prime}\\ \hline 17 & 3571 & 1 & \text{Prime}\\ \hline 19 & 9349 & 1 & \text{Prime}\\ \hline 21 & 24476 & 11\neq1 & \text{Not prime}\\ \hline 23 & 64079 & 1 & \text{Prime}\\ \hline 27 & 439204 & 22\neq1 & \text{Not prime}\\ \hline 29 & 1149851 & 1 & \text{Prime}\\ \hline 31 & 3010349 & 1 & \text{Prime}\\ \hline 33 & 7881196 & 4\neq1 & \text{Not prime}\\ \hline 37 & 54018521 & 1 & \text{Prime}\\ \hline 39 & 141422324 & 17\neq1 & \text{Not prime}\\ \hline 41 & 370248451 & 1 & \text{Prime}\\ \hline 43 & 969323029 & 1 & \text{Prime}\\ \hline 47 & 6643838879 & 1 & \text{Prime}\\ \hline 49 & 17393796001 & 29\neq1 & \text{Not prime}\\ \hline 51 & 45537549124 & 4\neq1 & \text{Not prime}\\ \hline 53 & 119218851371 & 1 & \text{Prime}\\ \hline 57 & 817138163596 & 4\neq1 & \text{Not prime}\\ \hline 59 & 2139295485799 & 1 & \text{Prime}\\ \hline 61 & 5600748293801 & 1 & \text{Prime}\\ \hline 63 & 14662949395604 & 41\neq1 & \text{Not prime}\\ \hline 67 & 100501350283429 & 1 & \text{Prime}\\ \hline 69 & 263115950957276 & 50\neq1 & \text{Not prime}\\ \hline 71 & 688846502588399 & 1 & \text{Prime}\\ \hline 73 & 1803423556807921 & 1 & \text{Prime}\\ \hline 77 & 12360848946698171 & 73\neq1 & \text{Not prime}\\ \hline 79 & 32361122672259149 & 1 & \text{Prime}\\ \hline 81 & 84722519070079276 & 22\neq1 & \text{Not prime}\\ \hline 83 & 221806434537978679 & 1 & \text{Prime}\\ \hline 87 & 1520283919093591604 & 62\neq1 & \text{Not prime}\\ \hline 89 & 3980154972736918051 & 1 & \text{Prime}\\ \hline 91 & 10420180999117162549 & 3\neq1 & \text{Not prime}\\ \hline 93 & 27280388024614569596 & 35\neq1 & \text{Not prime}\\ \hline 97 & 186982561199565069121 & 1 & \text{Prime}\\ \hline 99 & 489526700523968661124 & 76\neq1 & \text{Not prime}\\ \hline 101 & 1281597540372340914251 & 1 & \text{Prime}\\ \hline \end{array}$$

Why does this work?

Can this become a deterministic primality test?

Any insights, references, counterexamples, or theoretical developments would be greatly appreciated.

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ I am curious: in addition to using Wolfram GPT, did you happen to use AI in any other way in conceptualizing or writing this question? $\endgroup$ Commented Jun 29 at 15:11
  • 8
    $\begingroup$ You should’ve asked GPT to write a Python script to perform the numerical check. $\endgroup$ Commented Jun 29 at 15:28
  • 1
    $\begingroup$ The statement "I have verified ... using GPT" is an oxymoron, and should not appear in any serious argument, mathematical or otherwise. $\endgroup$ Commented Jun 30 at 5:53

2 Answers 2

Reset to default
17
$\begingroup$

The primality test fails. For odd integers $n$, one has $\lfloor \phi^n \rfloor =L_n$, the $n$-th Lucas number. Now $L_{2737}\bmod 2737=1$, but $2737=7\cdot 17\cdot 23$ is composite.
There are three more counterexamples below 10,000:
$4181=37\cdot 113$, $5777=53\cdot 109$, and $6721=11\cdot 13\cdot 47$.

Conjecture: The full set of counterexamples is OEIS:A337625. (See the proof by Wojowu.)

skip if you're not interested in Wolfram AI

These counterexamples are smaller than the range $10^6$ on which the OP tested the conjecture, using Wolfram AI (Wolfram GPT). I played around a bit with Wolfram AI and it is utterly unreliable; for example, it claimed $L_{5}=12$ (while $L_5=11$) and after some prompts to help it find a counterexample insisted that $37\cdot 73=2737$.
Improve this answer
$\endgroup$
5
  • 13
    $\begingroup$ I hope we're not entering an era in which published claims of the form "we checked the conjecture numerically" are increasingly less reliable. $\endgroup$ Commented Jun 29 at 14:41
  • 6
    $\begingroup$ I'm happy that Magma and Gap don't go in for this AI shite. $\endgroup$ Commented Jun 29 at 16:43
  • 1
    $\begingroup$ Asking AI is like asking a stranger on the internet. The advice can be totally helpful or utterly wrong. And without background knowledge it might be hard to tell. $\endgroup$ Commented Jun 30 at 10:01
  • $\begingroup$ @JFabianMeier But the crazy thing in this case is that it is easy to tell that the advice is wrong, because checking up to $n=2737$ is straightforward using a computer in the conventional manner. And yet Dev Sharma posts the claim publicly without bothering to check. $\endgroup$ Commented Jul 1 at 10:42
  • 1
    $\begingroup$ @TimothyChow --- the OP was apparently not aware of the identity $\lfloor \phi^n \rfloor =L_n$; a direct evaluation of $\lfloor \phi^n \rfloor $ for $n=2737$ is not feasible, at least Mathematica gives up on this. $\endgroup$ Commented Jul 1 at 11:16
8
$\begingroup$

This is a variation of the Fermat primality test and it has pseudoprimes, related to the notion of a Lucas or Fibonacci pseudoprime. As Carlo says we are essentially considering the Lucas numbers

$$L_n = \phi^n + \varphi^n.$$

This sequence satisfies $L_p \equiv L_1 = 1 \bmod p$ for all primes $p$, so the condition that $L_n \equiv 1 \bmod n$ is a necessary but not a sufficient condition for $n$ to be prime.

A general result along these lines is the following: if $M$ is a square integer matrix, then

$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p$$

for all primes $p$. This is "Fermat's little theorem for matrices," see e.g. this blog post. We get the Lucas numbers by taking $M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$, the Fibonacci matrix, whose powers have entries given by the Fibonacci numbers and whose eigenvalues are $\phi$ and $\varphi$, so it satisfies $\text{tr}(M^n) = L_n$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.