# number theory - approximate square root of a prime number

Some prime numbers can be written in this form-- $$p \cdot a^2 =b^2 \pm 1,$$ where $p$ is a prime number and $a$ and $b$ are integers. for example :- $3=2^2-1$; $5=2^2+1$; $7 \cdot 3^2 = 8^2 -1$ ; $11 \cdot 3^2 = 10^2 -1$; $13 \cdot 5^2 = 18^2 +1$ Question is --can all prime numbers be written in this form ?

-
I don't get it: you write $\,3=2^2-1\;,\;\;4=2^2+1\,$ , but then you also write $\,7\cdot 3^2=8^2-1\,$...but $\,7\cdot3^2=63\,$ is not a prime number, so: what exactly do you want?! Also, go to the FAQ section for directions how to write properly mathematics with LaTeX in this site. – DonAntonio Mar 2 '13 at 15:28
@DonAntonio $7=p$, $a=3$, $b=8$. – Thomas Andrews Mar 2 '13 at 15:37
@ThomasAndrews, I've no idea what you meant.... The OP wrote that "some primes can be written in the form...", yet he only gives two examples: $\,3,\,5\,$ , and then he adds to Pell-like expressions....so?? – DonAntonio Mar 2 '13 at 17:00
@DonAntonio Yeah, but the title mentions "approximate square root of prime numbers," so $pa^2=b^2\pm 1$ basically means $p$ can be written in the form $$\left(\frac{a}{b}\right)^2\pm \frac{1}{b^2}$$ If you are just objecting to the phrase "in the form of," I suppose you are sort of right. It's definitely sloppy language, but I knew what he meant. – Thomas Andrews Mar 2 '13 at 17:47
@ThomasAndrews, yes: thanks. Pretty sloppy, I guesss, till until you wrote me I didn't even saw the relation, not even after reading your answer. – DonAntonio Mar 2 '13 at 17:50

$$b^2-pa^2=\mp 1$$

This can always be solved for $(a,b)$ when $p$ is prime and the right side $+1$. More generally, if $D$ is any positive integer which is not a perfect square, there is a pair $x,y$ such that $$x^2-Dy^2=1$$

Your equation is just $D=p$.

Indeed, there are infinitely many solutions to this equation for any such $D$, and there is a method using continued fractions for $\sqrt D$ which computes the solutions.

Sometimes, the smallest solutions are very large for $D$ relatively small.

For example, when $p=199$, the smallest solution is $x=16266196520, y=1153080099$.

For details, see Pell's Equation.

The question of whether there are solutions to $$x^2-Dy^2=-1$$ is surprisingly complicated in comparison.

-
If prime $p \equiv 1 \pmod 4,$ there is always a solution to $x^2 - p y^2 = -1.$ – Will Jagy Mar 2 '13 at 15:41

With prime $p \equiv 1 \pmod 4,$ there is always a solution to $$x^2 - p y^2 = -1$$ in integers. The proof is from Mordell, Diophantine Equations, pages 55-56.

PROOF: Take the smallest integer pair $T>1,U >0$ such that $$T^2 - p U^2 = 1.$$ Since $p$ and $1$ are odd, we know that $T,U$ are not both even or both odd. One is even and one odd. Furthermore if $T$ were the even one and $U$ odd, as $p \equiv 1 \pmod 4$ we would have $T^2 - p U^2 \equiv 4 - 1 \cdot 1 \equiv -1 \equiv 3 \pmod 4,$ while it should be $1 \pmod 4.$ Therefore, we know that $T$ is odd and $U$ is even. We have the integer equation $$\left( \frac{T+1}{2} \right) \left( \frac{T-1}{2} \right) = p \left( \frac{U}{2} \right)^2.$$

We have $$\gcd \left( \left( \frac{T+1}{2} \right), \left( \frac{T-1}{2} \right) \right) = 1.$$

There are now two cases, by unique factorization in integers:

$$\mbox{(A):} \; \; \; \left( \frac{T+1}{2} \right) = p a^2, \; \; \left( \frac{T-1}{2} \right) = b^2$$

$$\mbox{(B):} \; \; \; \left( \frac{T+1}{2} \right) = a^2, \; \; \left( \frac{T-1}{2} \right) = p b^2$$

Now, in case (B), we find that $(a,b)$ are smaller than $(T,U),$ but $T \geq 3, a > 1,$ and $a^2 - p b^2 = 1.$ This is a contradiction, as our hypothesis is that $(T,U)$ is minimal.

As a result, case (A) holds, with evident $$p a^2 - b^2 = \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1,$$ so $$b^2 - p a^2 = -1.$$

For your listening pleasure, here are proofs (in Lagrange's style, "reduced" indefinite quadratic forms) that there are no solutions to $x^2 - 34 y^2 = -1$ or $x^2 - 205 y^2 = -1,$ despite the fact that there are solutions for $x^2 - 2 y^2 = -1,$ $x^2 - 17 y^2 = -1,$ $x^2 - 5 y^2 = -1,$ $x^2 - 41 y^2 = -1.$

=-=-=-=-=-=-=-=-=-=-=

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell
34

0  form   1 10 -9   delta  -1
1  form   -9 8 2   delta  4
2  form   2 8 -9   delta  -1
3  form   -9 10 1   delta  10
4  form   1 10 -9

disc   136
Automorph, written on right of Gram matrix:
5  54
6  65

Pell automorph
35  204
6  35

Pell unit
35^2 - 34 * 6^2 = 1

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell Input n for Pell 205 0 form 1 28 -9 delta -3 1 form -9 26 4 delta 6 2 form 4 22 -21 delta -1 3 form -21 20 5 delta 4 4 form 5 20 -21 delta -1 5 form -21 22 4 delta 6 6 form 4 26 -9 delta -3 7 form -9 28 1 delta 28 8 form 1 28 -9 disc 820 Automorph, written on right of Gram matrix: 881 24948 2772 78497 Pell automorph 39689 568260 2772 39689 Pell unit 39689^2 - 205 * 2772^2 = 1 ========================================= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ =-=-=-=-=-=-=-=-=-=-= The reason these are proofs is a fact, due also to Lagrange, that you may know from continued fractions: given a complete chain of reduced indefinite forms of discriminant$\Delta,$which is positive but not a square, all numbers$n$with$|n|< \frac{1}{2} \sqrt \Delta$and$n$properly represented by the form occur as the first coefficient of a form in the chain. This is Theorem 85 on page 111 of Introduction to the Theory of Numbers (1929) by Leonard Eugene Dickson. - You should make clear where you use$p\equiv 1\pmod 4$(at the step where you say "we know$T$odd and$U$even...") – Thomas Andrews Mar 2 '13 at 20:33 @ThomasAndrews, I put in something there. – Will Jagy Mar 2 '13 at 21:07 It's a nice proof - I'd never seen it before. It shows very clearly why prime-ness is important for this to be true. – Thomas Andrews Mar 2 '13 at 21:20 @ThomasAndrews, I like Mordell's book. Meanwhile, the first composite squarefree number with successful negative Pell for each prime factor is 34, no$x^2 - 34 y^2 = -1,$I've seen that in many books. The first odd one is 205, no$x^2 - 205 y^2 = -1,\$ the next odd failure 221. – Will Jagy Mar 2 '13 at 21:27