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.

Let $p$ be a prime number. Let $x,y,a,b$ be distinct positive integers. If $p=x^2 + y^2$ then $p\ne a^2+b^2$. Is this true ? If so why ? What are the proofs for this ? I know the Fibonacci identitity : http://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity , but I do not see how it follows.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

This is the basis of Eulers factorization method http://en.wikipedia.org/wiki/Euler%27s_factorization_method you can find full proof enclosed. (Brahmagupta-Fibonacci is an important part of it)

Given two different sums of square representations of a number, this produces a factorization. Euler used this to factor huge mersenne numbers and break the world record for biggest prime.

share|improve this answer
    
If people were interested in the relation between the two answers: This one is a constructive proof in that it actually gives you a factorization and it is elementary in the sense of not using complex numbers. The proof with Z[i] only gives existence of a factorization. –  user58512 Jan 28 '13 at 13:03
    
+1 At the moment I accepted your answer. It was better then the other from the start. However after the edit the other answer seems improved. See my comment there. –  mick Jan 28 '13 at 22:34

This is a consequence that $\mathbb{Z}[i]$ is a UFD; since $p$ can be factored as $(x+yi)(x-yi)$, and both $x+yi$ and $x-yi$ are clearly both primes, then by unique factorization $p$ cannot be factored in any other way (up to order and unit).

share|improve this answer
    
I do not consider this as an answer. Primes can not be factored is clearly true. –  mick Jan 27 '13 at 22:49
2  
@mick Do you understand what $\mathbb Z[i]$ is, and what a UFD is? –  Andres Caicedo Jan 27 '13 at 22:54
2  
@mick well, this does answer your question. What do you mean when you write "Primes can not be factored is clearly true"? –  Olivier Bégassat Jan 27 '13 at 22:56
    
@mick: $p$ is a prime in $\mathbb Z$, but is not in $\mathbb Z[i]$ as a factorization has been displayed. –  Ross Millikan Jan 28 '13 at 1:03
    
@mick The point is that in $\mathbb{Z}[i]$, the number $p=x^2+y^2$ is no longer prime; it has (non-unit) factors. On the other hand, the number $x+yi$ is prime; it has no non-unit factors. –  Steven Stadnicki Jan 28 '13 at 1:04

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.