If $p_x ^2 = 2n+1$ then $n$ is always even?

Question

If an odd prime squared $p_x ^2$ is written in the form $2n+1$, is $n$ always even?

Furthermore, is it true that $k\cdot p_x + n$ is always prime when $k\cdot p_x + n < p_{x+1} ^2$ and $\gcd(k,n)=1$ where $k \in \mathbb{N}$ and $n$ is as above?

Lastly, for $p_x ^2 = 2m-1$, is it true that $k\cdot p_x + m$ is always prime when $k\cdot p_x + m < p_{x+1} ^2$ and $\gcd(k,m)=1$ where $k$ is a positive even number?

Yes, to the question posed in the title. It has not so much to do with $p_x$ being a prime as with being odd. Any odd number squared is of the form $4k+1$. — hardmath, Sep 07 '15 at 03:26
The OP asks about a case where $p^2 = 2n + 1$, so $p$ is not $2$. — hardmath, Sep 07 '15 at 03:30
Could you provide some context for this question? Where did it comes from? What have you tried so far? — mweiss, Sep 07 '15 at 03:32
@mweiss Just a question i thought up trying to sleep, and i've tested it for numerous values in my head. — Brad Graham, Sep 07 '15 at 03:36
Let $p_x=17$. Then $n=144$. Let $k=1$. Then $kp_x+n=161$, and $161$ is not prime. I would expect that when $p_x$ is at all big, "most" legal choices of $k$ will yield a non-prime/ — André Nicolas, Sep 07 '15 at 03:59
@AndréNicolas thanks alot, i guess $k$ has to be coprime to $p_x$-primorial.. (For the second question to be true, third is abit more complicated) — Brad Graham, Sep 07 '15 at 04:04
For the revised third question, let $p_x=13$. Then $m=85$. Let $k=2$. Then $2p_x+m=111$. Lots of similar examples. — André Nicolas, Sep 07 '15 at 04:10

score 2 · Answer 1 · 2015-09-07T04:46:17.867

Any odd number squared is of the form $4k+1$, so that $p^2 - 1 = 4k$ for some integer $k$. If $p^2 - 1 = 2m$ then of course $m$ would be even (because $2m$ is divisible by 4).

Take $p = 5, k = 3, n = 1$. Then $16 < 25$ and $16$ is not prime.

EDIT: $p = 17, n=144, k=1$. So $161 < 289$ and $161 = 7\cdot23$ is not prime. I suspect that the counterexamples come very easily if we consider Fermat primes, though I can't prove this right now.

EDIT 2: If we consider $p = 2^k + 1$, then $p^2 = 2^{2k} + 2\cdot 2^k + 1$ so $n = 2^{2k-1} + 2^k$. Then, letting $k = 1$, we have $n + p = 2^k(2^{k-1} + 1) + 2^k + 1 = (2^k + 2)(2^{k-1} + 1) - 1 = 2(2^{k-1} + 1)^2 - 1$. My guess is that many numbers of this form are composite. Maybe if we set up some sort of Pell equation $2a^2 - 1 = b^2$ some good things will happen?

Lastly, if $p = 11$, then $m = 61$, and if $k = 4$ we have $105$ divisible by $5$ but $105 < 121$

Thanks for the answer, i see you disproved the 3rd question, and showed how the first was trivial. For the second question, I ment $n=0.5 (p_x ^2 -1)$ — Brad Graham, Sep 07 '15 at 04:00

If $p_x ^2 = 2n+1$ then $n$ is always even?

1 Answers1