For a very large number n, how many divisibility tests are required to establish if its prime?
I know this has something to do with the Golden Number, but I can't figure out what. I did try searching for an answer but not much luck.
!!EDIT!!
(It wont let me answer my own question for upto 8hours)
I found something posted by someone else on the primality test by golden ratio, although just like Fermat's probability test, it also fails at times.
There is a primality test by Golden ratio that is used in conjunction with the Lucas N+1 primality test. It is based on the relation between Lucas numbers and Fibonacci numbers. Primality test by Golden ratio states that if
$g^p+(1-g)^p \equiv 1\mod p$ , where g is golden ration, is true then p is prime. In other words, if
$\frac{g^p+(1-g)^p-1}{p} $ divides wholly then p is prime. The expression
$g^p+(1-g)^p$ is a formula for the p-th Lucas number, i.e.
$g^p+(1-g)^p = L_p$. As a result, we can say that if p-th Lucas number minus 1 divides by p wholly then p is prime, i.e.
$ \forall p \in \mathbb{N}, \frac{L_p-1}{p}=a$ where a $\in \mathbb{N} \Rightarrow $ p is prime.Aaaand it is not true. If you check a composite number 705 which is equal to 3*5*47:
$ \frac{L_{705}-1}{705} = \frac{g^{705} +(1-g)^{705}}{705} = 3.031556 * 10^{144}$
$3.031556 *10^{144}$ is a whole number and the test fails. Fermat's primality test suffers from a similar problem.
Best Answer
To test if some $x$ is prime, we generally have to do divisibility tests only up to and including $\sqrt{x}$.
That's because if some $y > \sqrt{x}$ were a factor of $x$, then there would have to be some $z$ such that $zy = x$. And $z < \sqrt{x}$ because if $z > \sqrt{x}$, then clearly $zy > x$ (as both $z$ and $y$ would be greater than $\sqrt{x}$). But if $z < \sqrt{x}$, then we've already tested $z$ in going up to $\sqrt{x}$!
And we don't have to do trial division for every integer up to $\sqrt{x}$. Using the Sieve of Eratosthenes, for example, after testing some $n$, we 'cross out' the integers that are multiples of $n$, because if some multiple of $n$ divides $x$, then $n$ has to divide $x$. So we only need to check the case for $n$.
In that spirit, there are lots of heuristics we can use to make prime-testing more efficient. However, finding large primes remains computationally very difficult.
Finally, I cannot immediately find an application of the golden ratio to this. You may be misremembering. I could dig up Prime Number Spirals, but I don't see how they'd be related.