Minutes Class 3

by Shayn Tierney, Anja Komlenovic, and Erich Prisner

"If numbers aren't beautiful, I don't know what is." (Paul Erdös)

Divisibility

This concept, as well as the concept of prime numbers, only applies to natural numbers. We say that a natural number A divides a natural number B if

• B/A is natural
• equivalently: if B: A has no remainder
• equivalently: if there is a natural number C such that CxA=B,

Euclid's Algorithm (procedure) for computing the GCD.
The input are two natural numbers a < b. We divide b by a and get a remainder r. If this remainder is not equal to 0, we rename a as b₁, rename r as a₁, and divide b₁ by a₁ to get another remainder r₁. We continue until eventually we must (since r > r₁ > r₂ ...) obtain a remainder r_m=0 (when dividing b_m by a_m). The last nonempty remainder r_m-1 is the GCD of a and b.

There is also a version of this algorithm to find common units of two straight lines. We check how often the shorter one fits into the larger one. Then we proceed with the remaining part (remainder) and the former shorter line, and so on. Different from above, the process doesn't have to terminate and could in principle go on forever (if there is no common unit length contained in both lengths).

Prime Numbers

A prime number is a natural number that can only be divided by 1 and itself. Also remember that 1 is not a prime number!

The following fact is the foundation of a lot of number theory---that part of mathematics that investigates natural numbers, prime numbers, and divisibility:
Theorem: Every natural number is uniquely the product of some prime numbers.

Really large numbers are very difficult and time consuming to factor.

The notion of "Proof" was introduced as demonstration for something true.

Theorem [Euclid]: There are infinitely many prime numbers.

Proof: The method of proof is called "Reductuo Ad Absurdum", you assume the opposite of what you want to prove correct and show that this assumption logically leads to something obviously wrong.
Assume there are only finitely many prime numbers P₁, P₂, P₃...P_n. Now take the product of all these prime numbers and increase by 1, you get A=P₁xP₂xP₂…P_n+1. Dividing A by P₁ leads to remainder 1, the same for the other n prime numbers, thus none of the prime numbers divides A. Since A must have a unique factorization into prime numbers, the only remaining possibility is that A itself prime, which is a contradiction to the assumption that P₁, P₂, P₃...P_n are all the prime numbers (note that A is larger than all these). That means that the opposite of the assumption must be true.

go to previous class<<<<<     >>>>> go to next class