Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?


share|improve this question
@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
show 1 more comment

6 Answers

up vote 21 down vote accepted

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

share|improve this answer
@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
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.

share|improve this answer
add comment

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

share|improve this answer
I read the 25! as 25 factorial initially. I was quite confused ;-). –  Jason DeVito Feb 13 '11 at 3:15
add comment

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.

share|improve this answer
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
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.