Euler, Prime p, p = 4n+1 => p = x^2 + y^2

Sorry, we can't do your homework for you.  :-)

First of all, all the numbers menthioned must be integer, right?
Also should it be p^2 = x^2 + y^2.

:-))

Indeed integers, I should should have been more precise :) p, n, x and y are all elements of N.

We are quite sure it's p = x^2 + y^2;
for p = 13, n = 3, x = 2 and y = 3.

Well, a mathematical proof is a little unusual for this forum.  How do I make my aliens bounce seems to be more up our street at the moment.

Whats the problem?  I think Euler is a  fairly respectable mathematician(:-)). The brtitannica article on this says that Gauss gave the first complete proof, so you might want to try looking him up.  (The brittanica article: http://britannica.com/bcom/eb/article/6/0,5716,117296+8,00.html)

I was thinking the proof had something to do with the pythagorean theorem.  (Which Euler prooved.)

I found a lot of euler's theorems and proofs on the net, but not this one.  Has it been prooven yet?

As I mentioned above, the britannica article says that Gauss proved it.  In fact it says that he liked this theorem so much, he provided six different proofs for it!  

Overacheiver.

:) Everyone has his 'weaknesses' :)

Thanks for your support so far. The Brittanica article looks good, we are looking in to it tonight.

I think you can use mathematical induction to prove this formula.
Let me revise the method, if a condition is true for 1 then assume
that it true for any number n and then prove that it is true for (n+1)
Then the condition is true for all numbers 1 to n.

I have coded this program which demonstrates that for every prime
number satisfying p=4*n+1 has a valid pair of x and y such that
p=x^2+y^2

#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <conio.h>

void main(void)
{
     unsigned int p,n,c,sroot,x,y;
     char at_least_one_factor=0;
     float p_xx;

     for(n=0;n<=16250;n++)
     {
       p=4*n+1;
       sroot=sqrt(p);
       at_least_one_factor=0;
       for(c=3;c<=sroot;c+=2)
        {
             if((p % c)==0)
             {
              at_least_one_factor=1;
              break;
             }
        }
       if(at_least_one_factor==0)
        {
             cout << "n=" << n << setw(8) << "p=" << p;
             for(x=1;x<=sroot;x++)
            {
                 p_xx=sqrt(p-x*x);
                 if((unsigned int)p_xx==p_xx)
                  {
                     y=p_xx;
                     cout << " x=" << setw(3) << x
                        << " y=" << setw(3) << y << '\n';
                     break;
                  }
            }
        }
     }
    cout << "\nEnd.";
    getch();
}

That doesn't use induction so that doesn't prove the theory.  In particular, you don't know that the next prime after the last one tested won't break the rule.

It reminds me of the prolbem where a mathmatician, a physicist and a programmer are all asked to prove that all odd numbers are prime.

The mathmatician says, "1 is prime, 3 is prime, 5, is prime, 7 is prime, by induction all odds are prime."

The Physicist says that is incorrect and resorts to experimentation  He tests 1 and finds it is prime, then finds that 3 is prime, 5 is prime, 7 is prime, 9 is...an error in measument..11 is prime, so all odd numbers are prime."

The programmer says that is incorrect and writes a program to prove it.  he runs the program and it prints out

"1 is prime"
"1 is prime"
"1 is prime"
"1 is prime"
"1 is prime"
"1 is prime"
"1 is prime"
....

I know that this problem is a really BIG DEAL among mathematicians. What I know is I am not the one who is going to solve this problem. I gave the code and answer for the seck of an attempt.
That is a very little contribution in solving the problem

Sumant, your effort is appreciated just the same. I don't think trying for a large set of numbers is 'proof'.

Although this is the C++ I did ask the (mathimatical) proof or a good link to it. I can see no decent area for this kind of questions (maybe in Pascal or The Lounge)...

I can understand.

 p = 4*n + 1


is there any typos on this formula.....
i guess it's
  p = 4^n + 1

but p=4^n=1 is not correct for n=5, 6 , or 7
which formula are you trying to prove.......
 
 

even for
     p = x^2 + y^2

not every prime number can be represented by x^2 + y^2 .........

But it said that every prime number can be represented as 4*n+1 OR 4*n+3. In the first case you can also find x and y so that p = x^2+y^2

Oh BTW, if p is a prime and there is an n such that p = 4*n+3 then there are no (x,y) such that p = x^2 + y^2

Can I ask why you even want to know?  This sorts of theories are good for only one thing--proving other theories that are just ase useful.  :-)

Hehe. My collegua brought up the subject (he is a mathematician) and I thought someone around here would know something about it.

I think what you are referring to is known as Euler's Rule (of Amicable Numbers).  The reason I think this, is from what you stated that, "if 'p' is a prime and there is an 'n' such that 'p = 4*n=3' then there is no (x,y) such that 'p = x^2 + y^2', which fits exactly with this Rule.

To show the Rule in notational form, I shall use the following terms:

~   means:  is approximately equal to
^   means:  raised to the power of
<=  means:  less than or equal to

-----------------------------------

The Rule states that the numbers 2^n times pq, and 2^n times r, are Amicable Numbers if the three Integers (i.e. p, q, and r) are such that

p ~ 2^m times (2^(n-m) + 1) - 1
q ~ 2^m times (2^(n-m) + 1) - 1
r ~ 2^(n+m) times (2^(n-m) + 1)^2 - 1

are all Prime numbers for some Positive Integer 'm' satisfying  1 <= m <= n - 1.

However, there are exotic Amicable Numbers which do not satisfy Euler's Rule, so it is a 'Sufficient' but not 'Necessary' condition for amicability.

--------------------------------------

It was the last part of your statement and the last part of his Rule which led me to believe that this is what you're talking about.

Mh, it's a bit different and my collegua (who brought it up in the first place) is quite sure about the x^2 + y^2 thingy.

http://www.utm.edu/research/primes/notes/

I don't see it there.

In further researching Euler's works, I did find the following, simply labeled "Euler's 6n + 1 Theorem".  It states, "Every Prime of the form '6n + 1' can be written in the form 'x^2 + 3y^2".

There was no proof accompanying it, but I shall keep researching further.

Try, thats closer!
rbr, couldn't find this particular 'problem' Can you elaborate?

Maybe it should be called "Euler's last theorm"  :-).  I.e.

"Every Prime of the form '6n + 1' can be written in the form 'x^2 + 3y^2"

I have found an ingenious proof of this, but time does not permit me to provide it here.

:-))

What I'm beginning to suspect (after having looked through many texts, encyclopedias, and talking to several of my peers) is that, in the tradition of many past mathematicians, a person would announce a rule, a formula, or a conjecture, and leave their fellow mathematicians to try and solve the statement themselves.  Sometimes, when the person making the announcement felt that no one would be able to solve the riddle, he would offer a prize or some reward as enticement for his peers to prove (or disprove) the statement.  That is my suspicion of what Euler has done.  He first refined, and then proved what Fermat had earlier stated.

The original statement came from Pierre de Fermat, himself, in a letter he wrote to a friend named, Bernard Frenicle de Bessy in 1640, in which he (Fremat) stated, that for any Prime 'p' and any whole number 'N', 'p' divides (N^p - n) [later proven by Euler].  That same year, Fermat wrote to another friend by the name of Marin Mersenne, stating that a Prime of the form '4n + 1' can be expressed in exactly one way as the sum of two squares (e.g. 13 = 4 + 9) and hence is the hypotenuse of exactly one right angle triangle with sides of integral length.  This is what Euler later picked up on (after disproving it), refined it and issued his (Euler) own statement that "Every Prime of the form '6n + 1' can be written in the form 'x^2 + 3y^2".

Tomorrow I'll be meeting with a fellow colleague of mine at one of the local universities to hear what he may have discovered.  But from initial inquiries, no one seem to have ever come across Euler's proof of this particular statement, and if it turns out to be anything like Fermat's Last Theorem, I recall seeing a documentary of a Princeton Math professor, who spent seven long and arduous years proving it, having retreated and abstained from all but the essential social events.  In the end, his voice began cracking up, his eyes became filled with liquid, and his demeanor succumbed to emotion as he related the epiphanic moment the solution manifested itself to him.  (What can I say!  For some people, fame hits them hard.)

hello,

I've been waiting for the proof quite some time.  I am really curious how Euler actually prove this theorem.

Is there really a proof for this theorem, I doubt it since we are still competing on the biggest prime number right now.  

As such, is the proof only work for those prime til the biggest prime number known to the world.  How could it be a proof for all prime numbers if we are still looking for the biggest prime number right now in this century(new).

Is this question out of the scope for C++ section.  Should we have another section dealed with MATH?  

But still it's a good question after all and I am curious abt it.

nietod,
could you at least tell us abt your ingenius proof.  Just the idea of how you prove it if you really dont have time to show us.  

I think this 'proof' is referring to some anekdote about Fermat :-)) nietod?

>> could you at least tell us abt your ingenius proof.
That was a "Fermat" spoof.  In his notes he proposed his famous theorem and said he had an elegant and simple proof, but could not include it at the time.  He never wrote the proof down and for nearly 3 centuries (is that right?) no one ever could proove it.  As a result his theorem has failed to be prooved many times.  Once it appeared as graffetti on a New York City Subway station but the mathematician's train came before he was able to complete the proof so once again the world missed an opportunity for an answer.  It was finally prooved and _published_ about 10 years ago.  The proof required 100s of pages and extremely complex mathematics not know in Fermet's time.  There is no doubt that this is not the proof Fermet had in mind.  It is quite possible that Fermat was mistaken, that his proof did not work, and so he never wrote it down and unfortunately never made mention of this fact.

The proof of the pudding (they say), is in the eating!  The proof of the substance of Euler's Prime Theorem, is how well it holds up, and if you were to take his premise that a Prime expressed in the form of '6n + 1' can also be expressed in the form 'x^2 + 3y^2', take the challenge and test it!

Let 'n' = 1  ||  6n + 1 = 7
Let x=2; y=1  ||  2^2 + 3(1)^2 = 7


Let 'n' = 2  ||  6n + 1 = 13
Let x=1; y=2  ||  1^2 + 3(2)^2 = 13


Let 'n' = 3  ||  6n + 1 = 19
Let x=4; y=1  ||  4^2 + 3(1)^2 = 19

....

Let 'n' = 10  ||  6n + 1 = 61
Let x=7; y=2  ||  7^2 + 3(2)^2 = 61

....

Let 'n' = 101  ||  6n + 1 = 607
Let x=10; y=13  ||  10^2 + 3(13)^2 = 607


It holds up!  7, 13, 19, 61, 607 are all Primes.

-----------------------------------

There's no such thing as the 'biggest' prime number, because there is no such thing as the 'biggest' number.  Any number you can conceive, you can always add 1 to it, which is what Euler has demonstrated as '6n + 1'.  'n' can be any number, ... ANY NUMBER; multiply it by 6, ... and then add 1 to it.

I'll be meeting with my colleague later today, and I'm sure he'll have something interesting to tell.

>> The proof of the substance of Euler's Prime
>> Theorem, is how well it holds up,
O course, technically that is not proof.  Of course if it failed to hold up in any example, that would be proof that it is incorrrect.

I am not even going to dignify your comment with a response.

The other way around is very simple:

p prime is sum of two quadrates  =>

= = 4*n + 1.

Proof: assume p = x^2 + y^2 for p a prime greater than 2. Then p is odd. Then it results that x is even and y is odd, OR , x is odd and y is even.
(If x and y are even numbers, then x^2 and y^2 are even numbers, and their sum will be even ! If x and y are odd, then x^2 and y^2 are both odd, and thier sum will be even !)
Conclusion: there are k and l elements of Natural Numnbers, for which is true: x = 2*k + 1 and y = 2*l or
x = 2*k and y = 2*l + 1
Assume x = 2*k + 1 and y = 2*l. then: p = x^2 + y^2 = (2*k + 1) ^2 + (2*l)^2 = = 4*k^2 + 4*k + 1 + 4*l^2 =
= 4( k^2 + k + l^2) + 1
This is a number with shape 4n + 1.

The other way around is more difficult:

p prime, p = 4n + 1 => There are x,y such that p = x^2 + y^2.

Assume P prime , p = 4n +1 . Then Legendre symbols say: (-1/p)= 1. This means there is an x such that x^2 = -1 (mod p). Therefore there is an x such that x^2 + 1^2 = 0 (mod p).
This means p is a diviser of x^2 + 1^2, but it does not say that it is exactly the same as p.

If you can prove there is a z such that z^2 ( x^2 + 1) = 0 (mod p) and
(x*z mod p)^2 + z^2 = p then you have solved this matter.

Jack.          

Then Legendre symbols say: (-1/p)= 1

---------------------------------

The Legendre Symbol does not say that (-1/p) = 1.  It says (-3/p) = 1, which gives us the quadratic nonresidue modulo 'm' of 'n'.  Look at it again.  I'm 100% sure of that!

Your approach on first reading, sounds plausible.  I would have to look at it more deeply to determine if it holds up under scrutiny.

BTW, I'm NOT doing this for the points, OK!  I'm doing it purely for the enjoyment and as a homage to Euler as a sort of expression of gratitude for all I have gained from him.  I say this because EE has that feature wherein a questioner can convert a person's comment as an answer (even if the person responding did not submit an answer).  With due respect to you, I do not want any points.

(If, by chance, you should have a question on Riemannian Geometry, I'd  be happy to give it a shot.  He is another to whom I feel I owe an expression of gratitude for what I have learnt from his works.)

Sorry it took me so long to get back here. My colleguea Jack (he is the guy who actually wondered about this issue and I had him explain most of the stuff to me) hasn't found the entire answer. I think the question has been open long enough and want to award it before it gets deleted.
So, Try, you always state you don't want points I'm going to nag you. Besides, your comments seem to be the right ones.
Oh, and I will get back to you if I ever have any questions on Riemann Geometry. I just wish I could understand that.

Thanx all of you, it has been an enjoyable thread.

Frans.

I would be remiss if I did not express some form of gratitude for being awarded your recognition.  It was not necessary, however, for you to have divested yourself of the resources I feel you might have found a more suitable use for, at some purposeful time in the future.  Nevertheless, I can understand the decency in you to have done what you did, and for that alone, I remain thankful.

My colleague (at the university) and I, are still battling with this theorem, meeting at least for an hour every week, to examine and evaluate what progress we might have made, and what additional information we may have discovered during the interim.  I will say this, our efforts are not altogether confined to mathematics for we (at least I am) conducting research into Euler's "Omnia Opera" to see if some mention of this theorem from him to a friend (by way of correspondence) might shed a time period when (perhaps) another of his peers might have done collateral work.  It was not unusual (I have discovered) for one person to have introduced a theorem (based on extrapolation) without any proof to the statement, many times leaving someone else to either prove or disprove it.  Fermat was especially famous for this practice, and I would not be surprised if after many more hours we may not find a proof to this particular theorem, leaving us (my friend and I, in this 21st century) to produce the proof.  Such thought has not escaped us.

I shall keep you updated with any revelation.  ITM, the exercise is both fun and (this part is true) ... nurturing.

this mightproove it..

http://math.ucsd.edu/~okikiolu/104b/l11.pdf