Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

For every prime number p there is a number n such that

p = 4*n + 1

or

p = 4*n + 3

Apparently Euler has proven that

For every prime number p for which there is a number n such that

p = 4*n + 1

there are two numbers x and y such that

p = x^2 + y^2

I'd like to see the proof for this proposition.

p = 4*n + 1

or

p = 4*n + 3

Apparently Euler has proven that

For every prime number p for which there is a number n such that

p = 4*n + 1

there are two numbers x and y such that

p = x^2 + y^2

I'd like to see the proof for this proposition.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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.

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 found a lot of euler's theorems and proofs on the net, but not this one. Has it been prooven yet?

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

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();

}

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"

....

That is a very little contribution in solving the problem

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

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

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

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.

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

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

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

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.

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.

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.

>> 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 did meet with my colleague and after a little over an hour of discussion, we don't have a solution as yet, BUT some rather interesting deduction arose from the exchange. (To be honest, I was happy when the meeting was over, because my head was beginning to ache.)

Anyway, what we have agreed on is that the best approach to solving this theorem is to use the Legendre Symbol which states that:

(m/n) = (m|n)

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

let ~ denotes congruency such that

1) (m/n) ~ 0 (i.e. zero) if m|n

2) (m/n) ~ 1 if 'n' is a quadratic residue modulo 'm'

3) (m/n) ~ -1 if 'n' is a quadratic nonresidue modulo 'm'

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

NOTE: If 'm' is an ODD Prime, then the Jacobi Symbol reduces to the Legendre Symbol. Happily, we did not get into applying the Jacobi Symbol.

Also, needful of saying, is that the Legendre Symbol obeys

(ab|p) = (a|p)(b|p)

such that

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

let +/- means plus or minus

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

1) (3/p) = 1 if p ~ +/- 1(mod 12)

2) (3/p) = -1 if p ~ +/- 5(mod 12)

What this all means, is that in applying the Legendre Symbol we used the fact that (-3/p) = 1, in saying there is a solution to x^2 = -3(mod p).

We have another meeting arranged for tomorrow.

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

For those who don't understand congruency (or might be a little forgetful about it), here is a little brushing up.

If 'b - c' is integrally divisible by 'a', then 'b' and 'c' are said to be congruent with modulus 'a', and is written 'b ~ c(mod a)'. IOW, the minus sign gets replaced by the congruency sign followed by the modulus value denoted within parentheses, or

a|b - c

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

Finally, I did not mention it earlier, but here it is: To prove Euler's statement, 'n' must be greater than zero.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialp 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.

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

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

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.

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.

C++

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

First of all, all the numbers menthioned must be integer, right?

Also should it be p^2 = x^2 + y^2.