# Validity of a proof

1. Mar 25, 2004

### MathematicalPhysicist

i made a question by myself here it goes:
proove that the only solution to p is 3:
n^2-1=p where n is a natural number and p is a prime number.

now im not sure about my proof so dont kill me (-:

from what we are given n^2-1 is a prime number which is (n-1)(n+1)
we all know that a prime number can only be divided by itself and by one therefore we can put it into options either n-1=1 and n+1=n^2-1 or n-1=n^2-1 and n+1=1
from the solutions of this equations we find the answers to n are:
2,-1,2,0,1,0 respectively.
now the only number which suits the equality is 2 and therefore p is 3.

what do you think? easy question?

2. Mar 25, 2004

### matt grime

You can save time since the factorization (n+1)(n-1)=p implies

one of n-1 or n+1 must be 1, the only anwer then being n-1=1, n=2, p=3.

This is a very common style of problem, often stated along the lines of, find all integers, n, where n^2 = 7P+9, say, where p is prime

then (n-3)(n+3) = 7p.... can you solve this one?

3. Mar 25, 2004

### MathematicalPhysicist

(n-3)(n+3)=7p
n-3=7 => n=10 p=13 (a prime)
n+3=p
n-3=p
n+3=7 => n=4 p=1 (not a prime)

i see now the general form of equation:
n^2=qp+k n,k-natural number
q,p- primes

am i right? (btw this form of equation gives me somekind of dejavue like i saw at somewhere before).

4. Mar 25, 2004

### matt grime

You also need to consider

n-3 =1, n+3 = 7p

and finally
n-3=7p, n+3=1

This method only works when k is a square number, so that you can form the difference of two squares on the left.

5. Mar 25, 2004

### MathematicalPhysicist

so change my general equation into:
n^2=qp+k^2 the same notation as first.

now it raises the question how do you solve n^2=qp+k? i assume there isnt only one way.

6. Mar 25, 2004

### matt grime

There may or may not be solutions. There is a lot of high powered number theory involved in these minds of things. For a long time people kept coming up with proofs of Fermat's Last Theorem becuase they didnt' understand equations like this.

Here are somethings we could do.

Notice that n^2 =k mod(pq) so, for existence, it is necessary that k is a quadratic residue mod pq. Using legendre symbols one can come up with various necessary conditions on the p and q and k for there to be a solution.

Suppose q and k are given, eg find all integers n and primes p with

n^2= 7p+3

That requires us to find an n with n^2 = 3 mod7

the residues mod 7 are 1,4, and 2, so there can be no solutions for any n, irrespective of the p.

I can't think of anyway that always sovles this type of equation, and to be honest I can't think of getting sufficient conditions for a solution to exist either.