Index. Prime Numbers [002T]

    Definition 1. Prime Number [0034]

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

      Lemma 2. Euclid's Lemma [0050]

        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.

        Theorem 3. Fundamental Theorem of Arithmetic [0052]

          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.

          Theorem 4. Infinity of Primes [004X]

            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.

            Backlinks

            Theorem. Fundamental Theorem of Arithmetic [0052]

              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.