Does the formula $\sqrt{ 1 + 24n }$ always yield prime? I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. 
 n: 1 -> 5
 n: 2 -> 7
 n: 5 -> 11
 n: 7 -> 13
 n: 12 -> 17
 n: 15 -> 19
 n: 22 -> 23
 n: 35 -> 29
 n: 40 -> 31
 n: 57 -> 37
 n: 70 -> 41
 n: 77 -> 43
 n: 92 -> 47

I wonder,  if 
$$\sqrt{1+24n}$$ 
is an integer, will it also be a prime?
Is there any interesting theory about this formula?  
Thanks,
Chan
 A: HINT $\rm\: \mod\ 24\::\ \ x^2 \equiv 1\ \Rightarrow\ (5x)^2 \equiv 1\:,\ $ but $\rm\:5\:x\:$ is prime iff $\rm\: x= \pm1$
Note that this yields a general structural reason explaining why such integers can't all be primes. Namely, the integers you describe are simply those integers that, when reduced modulo $24\:,$ yield square roots of $1\:.\:$ But such roots are closed under multiplication: $\rm\ x^2\equiv 1,\ y^2\equiv 1\ \Rightarrow\ (xy)^2\equiv 1\:.\:$ But primes are not closed under multiplication. For example, one can take any of your prime solutions and multiply them to obtain a composite solution, e.g. $\rm\ 5^2 = 25,\: \ 5\cdot 7 = 35\:,\:$ etc.
Notice that there are precisely $8\:$ square-roots of $\rm 1\ (mod\ 24)\ $ viz. $\rm \pm 1,\:\pm 5,\:\pm 7,\: \pm 11\:,\:$ corresponding (by $\rm CRT$) to the product of the two roots $\rm\ \pm 1\ (mod\ 3)\ $ times the four roots $\rm\ \pm 1,\: \pm 3\ (mod\ 8)\:.\:$ Note that these are precisely the congruence classes of all the integers coprime to $\:3\:$ and $\rm\:2\:,\:$ which includes all primes $> 3$. This explains your empirical observations above. The key observation, that $\rm\ x^2\equiv 1\ (mod\ 24)\ \iff\ x\:$ is coprime to $\:6\:,\:$ is nothing but a very special case computation of Carmichael's generalization of Euler's phi-function - see my post here for details.
A: Nope. $\sqrt{1+24*381276} = 3025 = 605 * 5$
There are many such formulars which seem to yield only primes, but most of them aren't.
A: $\sqrt{1+24\cdot 26} = \sqrt{625} = 25$!
$$\sqrt{1+24\cdot n} = x$$
$${1+24\cdot n} = x^2$$
$$ n = \dfrac{x^2 -1}{24}$$
So if $x=25$, $\dfrac{x^2 -1}{24}$ is an integer.
A: How about $n=26$?
In general, take a composite number of the form $12k+1$ and take $n = k + 6k^2$ to arrive at a contradiction for your statement.
For instance,
$k=2 \Rightarrow n=26 \Rightarrow \sqrt{1+24n} = 25$
$k=4 \Rightarrow n=100 \Rightarrow \sqrt{1+24n} = 49$
$k=7 \Rightarrow n=301 \Rightarrow \sqrt{1+24n} = 85$
and so on.
There are infinite composite numbers of the form $(12k+1)$ which gives infinite counterexamples to your claim.
Your observation though is a nice one, since $24 | (p^2-1)$, $\forall \text{ primes } p > 3$. So you will find that all the primes $>3$ can be written as $\sqrt{1+24n}$.
A: (p-1)(p+1) must be divisible by 2 times 4 if p is an odd integer (since p-1 and p+1 are then "consequtive even numbers" so both are divisible by 2, and one of them is even divisible by 4). If p is not divisible by 3, then one of the numbers p-1 or p+1 must be divisible by 3. Thus for any odd integer p which is not divisible by 3, the product (p-1)(p+1) must be divisible by 2*4*3=24. So for ANY odd integer p not divisible by 3 there exists some integer n (depending on p) such that p^2-1=24 n. So... but you can fill in the blanks now, n'est-ce pas?
A: take n=$24k^2$+$2k$  , $\Rightarrow \sqrt{1+24n}=24k+1$
24k+1, is composite infinitely, to give one such case..
if $k=24^{2r}$ r=0,1,2,3... then 25 divides $24k+1$ always
it follows, for $n$=$24^{4r+1}$+$(2.24^{2r})$ , r=0,1,2... the value $\sqrt{1+24n}$ is divisible by 25, and hence definitely not prime.
A: $$x=\sqrt{1+24n}\iff x^2=1+24n\iff x\text{ is an odd number not divisible by }3$$
A: Right ! I've proven recently this formula which at least englobes all prime numbers for sure. until now I didn't find a prime number that is not written as √24n+1. 
