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.

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 ?

share|improve this question
    
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

2 Answers 2

Rewrite your equation as:

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

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

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

Your Answer

 
discard

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.