What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, , ,

Newbie at Number Theory (Part Four): Prime Numbers

Published by

Valt

on

Wow, we are already four articles in and haven’t mentioned prime numbers yet! Blasphemy! We have to fix this! I’m sure you’ve heard about prime numbers before, but to make sure we are on the same page here’s what it means for a number to be prime:

Definition: (Prime Numbers) A positive integer p \neq 1 is a prime number if the only positive divisors of p are 1 and itself. Or, to be more mathy:

We call p a prime number if p\neq 1 and for all positive integers d such that d \mid p, then d=1 or d=p.

A number that is not 1 or prime is called composite.

Remark: You might be asking, “Why exclude 1 as a prime number?” This is a great question! One justification comes in the form of the Fundamental Theorem of Arithmetic, which states that every nonzero integer has a unique prime factorization. If 1 was a prime, then this wouldn’t be true. We could factor say 6 as,

6 = 1 \cdot 2\cdot 3 = 1\cdot 1\cdot 2\cdot 3 = 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 3 = etc.

Basically, we want to exclude all the variation that the 1’s allow in the above factorization. This is done most simply by excluding 1 as a prime number.

Remark Two: Since the integer 1 is not prime or composite it is called the unit.

Remark Three: Composite numbers are numbers that have at least one factor other than 1 and itself. Or, n is composite if there exists a positive integer d\neq 1,n such that d\mid n.

Some prime examples (haha) of prime numbers are: 2, 3, 5, 7, 11, 101, etc. All these numbers have no divisors other than 1 and itself. Most numbers that you might guess are composite. For example, 9, 15, 21, 25, 35, are composite, as well as every even number besides 2.

Oh, a quick theorem before we get to the Fundamental Theorem of Arithmetic:

Theorem: The prime 2, is the oddest prime.

Proof: Since 2 is the only even prime number, it is the strangest prime number. And a synonym of strange is odd. Therefore 2 is the oddest prime.

\square

Fundamental Theorem of Arithmetic

We are going to make use of a corollary of Euler’s Lemma from last time, called Euclid’s Lemma.

Euclid’s Lemma: Let p be a prime number and let a and b be integers. If p\mid ab and p\nmid a , then p\mid b .

Proof of Euclid’s Lemma: (Click in the Discovery)

Since p is a prime number only 1 and p divide it. This means that \gcd{(a,p)}=1 \;\mathrm{or}\;p. But, since p\nmid a , we know \gcd{(a,p)}\neq p so it must be that \gcd{(a,p)}=1 . Now apply Euler’s Lemma to arrive at Euclid’s Lemma.

\square

Comment: I know this proof isn’t very enlightening if you are unfamiliar with Euler’s Lemma. Moreover, if you aren’t familiar with Bézout’s Identity then Euler’s Lemma isn’t very enlightening either. To help out check out this footnote if you don’t want to read this article.1

Here’s a quick and useful corollary (left to the reader!) of Euclid’s Lemma:

Euclid’s Lemma (COROLLARY): Let p be a prime number and let p_1 , p_2 , and p_n be more prime numbers. If p\mid p_1p_2\cdots p_n , then there is some prime in the product such that: p\mid p_i . Hence p=p_i for some i.

Now, the pièce de résistance:

Theorem: (The Fundamental Theorem of Arithmetic) Every positive integer n (other than 0 and 1) can be expressed as a unique product of primes up to rearrangement. We call this product of primes n‘s prime factorization, or simply n‘s factorization.

By rearrangement, we mean that we consider factorizations like, 6 = 2\cdot 3 = 3 \cdot 2 to be the same factorization.

Proof of The Fundamental Theorem of Arithmetic: (Click in the Discovery)

We will break up this proof into two parts: (i) every integer larger than one has a prime factorization, and (ii) this prime factorization is unique up to rearrangement.

(i) Every number (other than 0 and 1) has a prime factorization

We use strong induction on n.2 Our base case starts with n = 2. Since 2 is prime, the prime factorization is simply n = 2.

Now assume that every integer greater than 1 but less than n has a prime factorization.

Consider n + 1. Here’s an obvious statement: Either n + 1 is prime, or it’s composite. In the case that n + 1 is prime, we’re done since its prime factorization is just n + 1. If n + 1 is composite, then there are integers a and b (not necessarily distinct) such that n=ab where 1<a\leq b<n+1 ( can you see why????).

Now we employ the induction hypothesis in order to conclude that a and b themselves have a prime factorization since: 1<a\leq b\leq n. Let’s denote their factorization,

a = p_1^{t_1}\cdot p_2^{t_2}\cdots p_m^{t_m} and b = q_1^{s_1}\cdot q_2^{s_2}\cdots q_l^{s_l}

Where the p‘s and q‘s are primes and not necessarily distinct from one another, and the t‘s and s‘s are natural numbers.3 Then, we conclude that n + 1 has the prime factorization,

n+1 = p_1^{t_1} \cdot p_2^{t_2} \cdots p_m^{t_m}\cdot q_1^{s_1} \cdot q_2^{s_2}\cdots q_l^{s_l}.

Now all we have to do is show that this prime factorization is unique.

(ii) Uniqueness of the prime factorization

Assume that n has two prime factorizations,

n = p_1\cdot p_2\cdots p_m and n = q_1\cdot q_2\cdots q_l.

Where all the p’s and q’s are primes. NOTE: We are choosing not to group primes together so we can have situations where p_i = p_j with i\neq j. (For example, 12 = 2\cdot 2\cdot 3.)

We will show that there is an equal number of p’s and q’s, ie m = l, and that each p equals some q.

p_1\cdot p_2\cdots p_m\;=\;q_1\cdot q_2\cdots q_l.

Consider the prime p_1. Since p_1\mid p_1\cdot p_2\cdots p_m we know that p_1\mid q_1\cdot q_2\cdots q_l as well. Thus, by Euclid’s Lemma (COROLLARY), p_1 = q_i for some 1\leq i\leq l. Hense, we can cancel out these primes to conclude:4

p_2\cdot p_3\cdots p_m\;=\;q_1\cdot q_2\cdots q_{i-1}\cdot q_{i+1}\cdots q_l.

Do this again for the prime p_2, and then for the prime p_3 and then, etc. . . We’ll see that for each prime p_x we’re considering we’ll find some prime q_y that equals p_x. If for some reason there were more p primes than q primes, then we would end up with the nonsensical statement concerning the left-over p primes:

p_a\cdot p_{a+1}\cdots p_m=1.

Likewise, if there were more q primes than p primes then we’d find that the product of left-over q prime must equal 1 as well,

1=q_a\cdot q_a\cdots q_l.

Thus, there must be equal number of p’s and q’s with each p equaling some q. We conclude that both factorizations are rearrangements of one another and hence are the same.

\square

More Questions…

There are so many more question that you can ask regarding prime numbers! And it’s not long before you’ll reach the limits of modern mathematics! One question that we do know the answer to is,

“How many primes are there?”

This question was answered by Euclid wayyy back in around 300BC!

There are Infinitely Many Primes ala Euclid

This theorem is considered to be the third most beautiful theorem in all of mathematics, at least according to a polling from planetmath.org.

Theorem (Euclid): There are infinitely many primes.

Proof: (Click in the Discovery)

Assume for the hope of a contradiction that there were only finitely many primes, say there are n primes. Call them,

p_1,\;p_2,\cdots,\;p_n.

Consider the integer N that is the product of all the primes (plus 1),

N=(p_1\cdot p_2\cdot\;\cdots\;\cdot p_n) +1.

Two things can happen. Just like earlier, either N is prime of it’s composite.

(i) If N is prime, then we found a new prime number contradicting that we had a complete list at the beginning.

(ii) Or, if N is composite then there exists at least one prime that divides it. But N is not N divisible by any of the primes p_1,\;p_2,\cdots,\;p_n. For if it was divisible by say, p_1, then N = p_1k and,

N-(p_1\cdot p_2\cdot\;\cdots\;\cdot p_n) = p_1(k-p_2\cdot p_3\cdot\;\cdots\;\cdot p_n)=1.

Implying that p_1\mid 1, or that p_1=1, which is impossible! Hence, the primes that divide N are not on the list, contradicting that we had a complete list (again).

\square

Final Remarks

There are a lot of mysteries concerning prime numbers. For example, we don’t yet know if there are infinitely many twin primes, (primes separated by two like 3 and 5 or 101 and 103). We don’t know if there is always a prime between square numbers. For example, we know that 11 is in between 32 and 42 , but it’s unknown that this is true for any n^2 and (n+1)^2!?! We also don’t have a formula to generate only prime numbers. And we don’t have a fast way to check if a number is prime.

Maybe you, the reader, will solve one of these!

We do know some things, however. We know that there is a prime between n and 2n. This is called Bertrand’s Postulate and the great mathematician Paul Erdős gave a really beautiful proof. We also know that the number of prime numbers up to x “behaves like” x/\ln{(x)}, this is known as the Prime Number Theorem. And we also know that there are infinitely many primes in the sequence a+d\;,\;a+2d\;,\;a+3d\;,\;\cdots if \gcd{(a,d)}=1. This is known as Dirichlet’s Theorem about Arithmetic Progressions.

Primes are and endless source of beautiful mathematics.

To end this article, I’ll figured I’d give you some of my favorite conjectures:

UNNAMED Conjecture: Let q_n be the smallest prime that is larger than P_n = p_1\cdot p_2 \cdots p_n+1. Where p_1,\;p_2,\cdots,\;p_n are the first n primes. Here’s the conjecture, the difference q_n - P_n is a prime number. (Feel free to check this for a few n’s)

Grimm’s Conjecture: If n+1\;,\; n+2\;,\; \cdots,\;n+k are all composite, then there exists k-different prime numbers such that, p_i \mid n+i, with 1\leq i \leq k. (For example, 24, 25, 26, 27, 28 are composite, and the primes 2, 5, 13, 3, 7 divide them respectively.)

Legendre’s conjecture: We already mentioned this one: For any integer n there is a prime in between n^2 and (n+1)^2.

Footnotes:

  1. Here’s the idea. Take the integers 7 and 490. Since 7\mid 490 and 7 is prime, and we claim that any way we break down 490 into a product of its factors, we are guaranteed that 7 divides at least one of them. Let’s check when we write 490 as a product of two factors:
    490 = 1\cdot \underbrace{490}_{7\mid 490} = 2 \cdot \underbrace{245}_{7\mid 245} = 5\cdot \underbrace{98}_{7\mid 98} = \underbrace{7\cdot 70}_{7\mid 7\;\mathrm{and}\;7\mid 70} =10\cdot \underbrace{49}_{7\mid49} = \underbrace{14\cdot35}_{7\mid14\;\mathrm{and}\;7\mid35}
    This works because 7 must show up in one of the two factors, otherwise we couldn’t have 7\mid 490 . And with Euclid’s Lemma, we are assuming that 7 isn’t showing up in the first facts. This is like 490 = 5\cdot 98. Thus, 7 must show up as a factor of 98. ↩︎
  2. Note strong induction is just like standard induction, but our induction hypothesis assumes that our proposition P(k) is true for all k less than or equal to n. Not just true for P(n). ↩︎
  3. A natural number is the subset of the integers given by: {1, 2, 3, 4, 5, 6, … }. ↩︎
  4. Note that I’m using loose language, since division is not defined on the integers. But this is ok, since the integers are known as an integral domain, we can use cancellation without issues. ↩︎

3 responses to “Newbie at Number Theory (Part Four): Prime Numbers”

  1. Newbie Number Theory (Part 6): Fermat’s Fantastic Little Theorem – A Kick in the Discovery Avatar
    Newbie Number Theory (Part 6): Fermat’s Fantastic Little Theorem – A Kick in the Discovery

    […] that or (by Euclid’s Lemma). But since it must be that and hence But recall that we chose , meaning that And note that no […]

    Like

    Reply
  2. Newbie at Number Theory (Part 1.414…): Irrational Numbers – A Kick in the Discovery Avatar
    Newbie at Number Theory (Part 1.414…): Irrational Numbers – A Kick in the Discovery

    […] Euclid’s Lemma, (see footnote for a reminder).1 Since 2 is prime and , it must be that (by Euclid’s lemma). […]

    Like

    Reply
  3. Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery Avatar
    Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery

    […] Consider some natural numbers and such that . We are aiming to show . In the case that is prime we uses Fermat’s Little Theorem and we are done. So, let’s assume that is composite (we disregard the case ). Therefore, factors uniquely into distinct primes (by the Fundamental Theorem of Arithmetic): […]

    Like

    Reply

Leave a reply to Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery Cancel reply