UVa 106

From Algorithmist

Contents 1 106 - Fermat vs. Pythagoras 2 Summary 3 Explanation 4 Input 5 Output

[edit] 106 - Fermat vs. Pythagoras

• http://acm.uva.es/p/v1/106.html

[edit] Summary

We will need to find another relationship that generates the Pythagorean triples that will allow us to generate all pairs easily.

[edit] Explanation

This is a relatively difficult Math problem. The intuition is that we would brute force on x, y, and z would take too long. The easy optimization is that you can calculate z, but since x and y can be as big as a million, the O(n²) solution is still not good enough.

The actual solution takes a little bit of Number Theory.

Assume that you have two numbers, r, and s. (for now, assume they're given) Then this equation is true:

(r² - s²)² + (2rs)² = (r² + s²)²

Given an r, s pair, it is trivial to create a Pythagorean triple. The difficult thing is to prove that all of them can be generated from them. If this is proven, then it is easy to generate all the triples, since we only have to check all .

Why does this generate all triples?

Let's assume that x,y,z is a triple which is relatively prime. This implies that one, but not both, of x,y must be even. (Otherwise, z would be divisible by 2, but not by 4) Assuming, without the loss of generality, that y is even, and x,z are odd, we can rewrite the equation as:

y² = (z + x)(z - x)

Since y is even, y² is divisible by 4. Also, note that z+x and z-x are both divisible by 2 (adding/subtracting an odd number to another odd number). So we can further write it as:

Now and must be relatively prime (if they had a common factor, then their sum[z] and their difference[x] would have a common factor). It is now easy to see that each of these number must themselves be squares (thru unique factorization theorems). Setting and , and you will finally reach the previous equation of:

(r² - s²)² + (2rs)² = (r² + s²)²

Since , we can use all r,s pair to generate the triples.

You can also prove that, x,y,z are relative prime iff r,s are relative prime. ( using that fact that R.PRIME(r,s) and one and only one of r,s is even number ==> R.PRIME(r+s, r-s) ). This can further reduce the run time.

[edit] Input

10
25
100
1000000

[edit] Output

1 4
4 9
16 27
159139 133926