Solutions of the diophantine equation are called pythagorean triples.

Let be an integer. A natural number is called a divisor of if there exists such that We write , say divides . We denote the set of all divisors by We write for the number of divisors of .

A natural number is called pime if it has exactly two divisors. Hence .

Let be integers. If and are not both , then the set of common divisors is finite and nonempty. We then define the greatest common divisor as and denote it by .

For every where there exists a unique pair of numbers and such that and .

Proof. The set is not empty, thus contains a minimal element . This gives us existence. Now to uniqueness: Let there be two pairs that fullfill our requirements. We now have . This gives us , but , which is only possible with . This forces as well.

The euclidean algorithm starts with two integers and and performs successive division with remainder until it is zero, like follows.

The algorithm computes the the greatest common divisor of and . For a proof see the Euclid's Theorem.

Two natural numbers are called coprime if their greatest common divisor is 1.

The euclidean algorithm computes the greatest common divisor.

Proof. TODO

For any natural numbers . There exist integers such that the gcd of can we written as .

Proof. Do the Euclidean Algorithm in reverse.

Let with the gcd of and equal to 1, and . Then .

Proof. From Bezout's Lemma there exists integers with . Multiply by to get . Since and by hypothesis, it follows that .

A natural number is called pime if it has exactly two divisors. Hence .

Let and prime with then or .

Proof. We only need to show the case where . Because is prime, it has exactly the divisors . does not divide so their only common divisor is . Thus . We are done by applying this corollary.

For any natural number there exists a unique finite series of primes such that .

Proof. To show existence we perform induction over . If there is nothing to show. Thus let . If is prime there is nothing to show, so let be not prime. In that case ther exist with By induction hypothesis and are themselves products of primes, and by extension as well.

To show uniqueness we assume two factorizations and . Without loss of generality we assume that . By Euclid's Lemma there exists such that thus . We now perform induction over . if then must also be 1, since dividing by shows that is contradictory otherwise. For we can divide both sides by (since ) and apply the induction hypothesis.

There are infinitely many primes.

Proof. Suppose are the only primes. Since has a prime factorization there exists with . But so must also divide . That is a contradiction.

For and with we write .

The residue class of modulo is given by the equivialence class .

We denote the set of residue classes mod with .

is a field if and only if is prime.

Proof.

• Let be prime then . thus is a field.
• Assume is a field and with . Then thus has no solution. So , which is contradictory.

We have already established here, that is a cummutative unitary ring. ( TODO)

Euler's totient function is defined by .

If is prime then .

Proof. By definition of the totient function.

Let and with then .

Proof. TODO

Let be coprime. And let be systems of representatives of and respectively. Then is a complete system of representatives.

For an integer we call a diophantine equation of the form Pell's equation.

1. If , or , then is the only solution.
2. If all solutions are and an aritrary .
3. If all solutions are .

Proof.

1. In the first case we can write the equation as , then . If , write . This forces and thus . If is of the form , then we have , forcing and .
2. This is clear.
3. We have . Our only options are and

Let be a natural number and not a square. We denote the set by , read as adjoint with .

For an element of we define its conjugate by .

We can identify a solution of the Pell equation with the pair . In this case is the inverse of , since . From this point of iew, the solutions of the Pell equation are precisely the units of .

We obtain new solutions by multiplying solutions we have already found.

Proof. Let and in be invertible; then is also invertible since . Therfore, also corresponds to a solution.

The minimum element of the set is well-defined. We call this element the fundamental solution of the Pell equation and denote it by .

Proof. TODO

Sei be non-square. Then the solutions of the Pell equation are exactly . where is the fundamental Solution.

Proof. TODO