# 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?

Thanks,
Chan

-
@Arturo Magidin: Thanks for the editing. I was trying to get rid of the \n ^_^! –  Chan Feb 12 '11 at 23:10
Do you mean, does it give a prime whenever it gives an integer? (Obviously, it doesn't always give a prime because it doesn't always give an integer). –  Arturo Magidin Feb 12 '11 at 23:11
@Arturo Magidin: Yes, that what I tried to say. –  Chan Feb 12 '11 at 23:14
@Chan: I'm not criticizing here, just curious: why did you skip $n = 26$ in your experiments? –  Pete L. Clark Feb 13 '11 at 20:12
But many of your $n$ are not primes, so why did you skip 26? –  Ross Millikan Mar 5 '11 at 5:48

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}$.

-
@Sivaram Ambikasaran: so what form could yield prime? –  Chan Feb 12 '11 at 23:12
@Chan: What form of what? –  user17762 Feb 12 '11 at 23:18
@Chan: If you want what form of $n$ will yield you prime, that might be a difficult question to answer. You can of course find what form of $n$ will yield an integer. –  user17762 Feb 12 '11 at 23:20
@Chan: Given that every prime number is spanned by the sequence, to know what values of $n$ yield a prime is equivalent to knowing the pattern of primes. –  user17762 Feb 12 '11 at 23:28
Sorry, I made a common mistake based on a proof that number of primes is infinite. –  InterestedGuest Feb 13 '11 at 0:25

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.

-

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.

-
I am not sure what you mean. There are many examples, including infinite series, and polynomials in several variables all of whose positive values are prime numbers. –  Andrés Caicedo Feb 12 '11 at 23:17
Changed. I thought it's very difficult or impossible to find a prime generating function which only yields primes. Can you give me an example? –  FUZxxl Feb 12 '11 at 23:21
Look up this wikipedia page. en.wikipedia.org/wiki/… –  user17762 Feb 12 '11 at 23:33
Uhhh... That's difficult. Thanks for this link. –  FUZxxl Feb 13 '11 at 11:43

$\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.

-
I read the 25! as 25 factorial initially. I was quite confused ;-). –  Jason DeVito Feb 13 '11 at 3:15

(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?

-

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.

-

$$x=\sqrt{1+24n}\iff x^2=1+24n\iff x\text{ is an odd number not divisible by }3$$

-

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.

-