# 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

1
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

3
@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

1
But many of your $n$ are not primes, so why did you skip 26? – Ross Millikan Mar 5 '11 at 5:48
show 1 more comment

## 6 Answers

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

1
@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

1
@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

2
Sorry, I made a common mistake based on a proof that number of primes is infinite. – InterestedGuest Feb 13 '11 at 0:25
show 5 more comments

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.

-

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

-

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

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. – Andres 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

1
– user17762 Feb 12 '11 at 23:33
Uhhh... That's difficult. Thanks for this link. – FUZxxl Feb 13 '11 at 11:43

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 49, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9112634062767029, "perplexity_flag": "middle"}