Elementary Number Theory with Programming

2FIBONACCI SEQUENCE, PRIMES, AND THE PELL EQUATION

A prime number is a number that has no divisors other than itself or 1. The subject of prime numbers is a big part of number theory.

PRIME NUMBERS AND PROOF BY CONTRADICTION

The first few primes are 2, 3, 5, 7, 11, 13, 17, and 19. A number that has divisors (or factors) other than itself and 1 is called composite. A composite number must have a prime divisor. Let n be a composite number. Then it has a factor, say, m, smaller than n. For example, 100 has the divisor 25. Now, if m is a prime, we have the desired prime divisor. If, on the other hand, m is composite, then m has a smaller divisor, say, k. Once again, if k is a prime, we have the desired prime divisor. If not, continue the process by producing a still smaller divisor, say, j, of k. Note that these divisors (m, j, and k) are divisors of the original number, n. Now, this process can’t go on forever, since n has finitely many divisors. It follows that sooner or later, this process produces a prime divisor.

The great Greek geometer and number theorist Euclid, who lived in Alexandria, Egypt, circa 300 b.c., proved that there are infinitely many primes. He began by assuming that there are only finitely many primes and proceeded to obtain a contradiction. (The proof may have been known before Euclid wrote it down in his 13-volume book, “Elements.”)

If there are finitely many primes, call them a, b, c, and so on up to the supposed last (or greatest) prime, say, p. Then ...