Using the Definitions of Prime and Composite Numbers

Subsection 6.2.3 Using the Definitions of Prime and Composite Numbers

Let’s use our definitions of primes and composites to describe other useful classes of integers.

Definition of Mersenne Primes

An integer is a Mersenne number if and only if it is one less than some positive integer power of 2. Another way to say this is that a Mersenne number is the value of 2n-1 for some positive integer n.

Table 6.2.1.

n	2n	2n -1
1	2	1
2	4	3	*
3	8	7	*
4	16	15
5	32	31	*
6	64	63
7	128	127	*
8	256	255

If a Mersenne number is also prime, then it is a Mersenne prime. The Mersenne primes are marked with a * in the table above.

Let’s represent this definition as a logical expression. Let the universe be the set of positive integers. Define:

MersenneP(x): True if x is a Mersenne prime.

Then we can write:

[6] ∀x (MersenneP(x) ≡ (Prime(x) ∧ ∃n (x = 2n-1)))

Nifty Aside

Mathematicians have been studying Mersenne primes since the early 17th century. The French monk Marin Mersenne got his name attached to them. Mersenne claimed to have checked all values for n up to 257 and to have determined those for which 2n-1 was prime. It turns out that he got several of them wrong. By 1947 (with the aid of some computing), Mersenne’s range had been completely checked. The only values of n, in Mersenne’s range, for which 2n-1 is prime are 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127. By the way, it can be proved that if n is composite, then 2n-1 is also composite. So it’s only necessary to check prime values of n.

The Great Internet Mersenne Prime Search (GIMPS) project has been responsible for finding all the Mersenne primes that have been discovered since 1997. As of October, 2014, 48 Mersenne primes were known. It’s conjectured that are infinitely many of them, but they are so big that it’s not straightforward to compute with them.

Definition of Fermat Numbers

A Fermat number is an integer that can be expressed as \(2^{2^{n}}\)+1, for some positive integer n.

Nifty Aside

The Fermat numbers are named for the 17th century French mathematician Pierre de Fermat, who first studied them. The first seven Fermat numbers are 3, 5, 17, 257, 65537, 4294967297, and 18446744073709551617, of which only the first five were actually computed by Fermat.

Fermat was particularly interested in whether Fermat numbers are necessarily prime. All the ones he studied (i.e., the first five) are prime and he thought that all Fermat numbers were prime. It is now thought that the only prime ones are those first five, although there’s no proof that that’s so. Visit http://www.prothsearch.net/fermat.html ¹ to find out more about a distributed effort on the Internet to find factors of very large Fermat numbers.

We’ll leave stating this definition as a logical expression as a problem for you to solve.

Fermat’s Last Theorem

Pierre de Fermat did many different things. Here’s another one (pretty much unrelated to the Fermat numbers that we just discussed).

Consider this equation:

[7] xn + yn = zn

Suppose that n = 1. Then, if x = 1, y = 1 and z = 2, we have that 11 + 11 = 21 and the equation is satisfied.

Suppose that n = 2. Then, if x = 3, y = 4 and z = 5, we have that 32 + 42 = 52, and the equation is satisfied.

Fermat conjectured that, if n > 2, then there are no three positive integers x, y, and z that can satisfy the equation.

Nifty Aside

In 1637, Fermat wrote this conjecture in the margin of a book but claimed that his proof wouldn’t fit in the margin. Mathematicians struggled for a couple of centuries to find a real proof. Andrew Wiles finally discovered one in 1995.

Fermat’s conjecture may appear to be little more than a claim about a few numbers. But there’s also a striking geometric interpretation of it.

Visit http://www.youtube.com/watch?v=xG63O03lWZI ² to try to visualize it.

Fermat’s Last Theorem fascinated and puzzled mathematicians for so long that it has made its way into popular lore. Visit http://www.youtube.com/watch?v=ReOQ300AcSU ³ for a video that gives several examples of this, including a fascinating one in which it appears that Homer Simpson (of all people) has shown that Fermat’s conjecture is false. (You may only want to watch the first half or so of this one.)

We’ll leave stating Fermat’s famous claim as a logical expression as a problem for you to solve.

Goldbach’s Conjecture

We’ll next consider perhaps the most famous mathematical conjecture that remains unproven:

[8] Every even integer greater than 2 can be expressed as the sum of two primes.

For example, 18 = 5 + 13

= 7 + 11

Nifty Aside

This conjecture is named for the German mathematician Christian Goldbach, who stated a slightly different version of it in a letter to Leonhard Euler in 1742. While it remains unproven to this day, it is widely believed to be true. It is actually known to be true for all even integers up to 4  1018.

We also know that almost all even integers greater than 2 can be expressed as the sum of two primes in multiple different ways. For example:

100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53

Again, we’ll leave stating this famous claim as a logical expression as a problem for you to solve.

Exercises Exercises

1.

1. A Fermat number is an integer that can be expressed as \(2^{2^{n}}\)+1, for some positive integer n. Define:

FermatN(x): True if x is a Fermat number.

Which (one or more) of the following logical expressions define(s) the Fermat numbers:

I. ∃n (x = \(2^{2^{n}}\)+1)) → FermatN(x))

II. ∀x (FermatN(x) ≡ ∃n (x = \(2^{2^{n}}\)+1))

III. ¬∃n (x = \(2^{2^{n}}\)+1)) → ¬FermatN(x))

Just I.
Just II.
Just III.
I and II.
II and III.

Answer.

Correct answer is B.

Solution.

Explanation: Just II. A definition requires an equivalence statement. I captures the fact that a number is a Fermat number if it possesses the key property. But it fails to say that any number that doesn’t possess the property isn’t a Fermat number. III does that, but it doesn’t say what it takes to make something a Fermat number.

2.

2. Fermat’s Last Theorem is the conjecture, first made by Pierre de Fermat, that, if n > 2, then there are no three positive integers x, y, and z that can satisfy the equation:

[1] xn + yn = zn

All we’re going to do here is to state the claim formally. Since Fermat first made the claim in 1637, yet it wasn’t proved until 1995, the proof is clearly beyond the scope of our effort here.

Assume a universe of positive integers. Which of the following logical expressions does not correspond to Fermat’s claim:

∀n ((n > 2) → (∀x, y, z (xn + yn ≠ zn)))
∀n, x, y, z ((n ≤ 2) ∨ (xn + yn ≠ zn))
∀n ((n > 2) → ¬∃x (¬∃y (¬∃z (xn + yn = zn))))
∀n ((n > 2) → ¬∃x (∃y (∃z (xn + yn = zn))))

Answer.

Correct answer is C

Solution.

Explanation: The only incorrect one is n ((n > 2)  x (y (z (xn + yn = zn)))). To see why, push the nots through the existential quantifiers and see what you get. To see why the other expression that contains  is correct, push the not all the way through it. You will get one of the other correct expressions.

3.

Goldbach’s Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes. Clearly we’re not going to try to prove it. (No one ever has.) But let’s express it formally. Assume a universe of positive integers. Which of the following logical expressions does not correspond to Goldbach’s Conjecture:

∀x (¬Even(x) ∨ (x ≤ 2) ∨ ∃y, z (Prime(y) ∧ Prime(z) ∧ (x = y+z)))
∀x ((Even(x) ∧ (x > 2)) → ∃y, z (Prime(y) ∧ Prime(z) ∧ (x = y+z)))
∃x (¬Even(x) ∧ (x > 2) ∧ ∃y, z (Prime(y) ∧ Prime(z) ∧ (x = y+z)))
¬∃x (Even(x) ∧ (x > 2) ∧ ¬∃y (∃z (Prime(y) ∧ Prime(z) ∧ (x = y+z))))

Answer.

Correct answer is C.

Solution.

Explanation: The only incorrect one is the one that begins x ( … We can see right away that it can’t be correct since it asserts simply the existence of some set of values x, y and z. We know that we need to make a universal claim. You can check that the others are all logically equivalent.

fermat

You