How To Determine If A Large Number is Prime? 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. 

 A: 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. 
A: Why would you not just check any given number to see if it is a prime number by simply attempting to divide it by preceding prime numbers? No matter how big the number is there can not be that many you would need to check it against. 
Other than that unless you know a formula that can tell you what any given prime number may be then there can be no way to test to see if a given number is a prime other that trial and error.
