13
$\begingroup$

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

  • 1
    But many of your $n$ are not primes, so why did you skip 26?2011-03-05

8 Answers 8

22

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

  • 0
    Small note $24 | (n^2-1)$, \forall \text{ odd } n > 32014-12-19
8

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.

5

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.

  • 0
    Uhhh... That's difficult. Thanks for this link.2011-02-13
3

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

  • 14
    I read the 25! as 25 factorial initially. I was quite confused ;-).2011-02-13
1

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

0

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.

0

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

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