wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> prime or square of prime number
        
(Message started by: inexorable on Oct 19^th, 2005, 6:27am)

Title: prime or square of prime number
Post by inexorable on Oct 19^th, 2005, 6:27am

Let a be an odd positive integer and suppose that the equation (x^2)-(y^2) = a has exactly
one solution in positive integers x and y. Prove that either a is a prime number or it
is the square of a prime number.

Title: Re: prime or square of prime number
Post by Obob on Oct 19^th, 2005, 7:28am

Suppose that a is neither prime nor the square of a prime. Then there are distinct integers m, n >1 such that a=mn. Since a is odd, so are m and n. Therefore there are integers x and y such that m=x+y and n=x-y; namely take x=(m+n)/2 and y=m-(m+n)/2. Then (x-y)(x+y)=x^2-y^2=mn=a. However, there are also integers x and y such that mn=x+y and 1=x-y; this time take x=(mn+1)/2 and y=mn-(mn+1)/2. Note that these two solutions are unique, for if (m+n)/2=(mn+1)/2 then m+n=mn+1, so m(1-n)=1-n, forcing either m or n to be 1, a contradiction. Thus a must be prime or the square of a prime.

Note that this breaks down if m=n since then we picked y=0, which was not allowed.