These exercises are optional extra material for students who are done with the exercises of the day but have the time for and the interest in more.
Extra (Optional) Exercises – Long Day#
Extra Exercise 1: There Exist Infinitely Many Primes#
A natural number \(d\) is said to be a divisor of (or to divide evenly) another natural number \(n\) if \(n/d\) is a natural number. A prime number is a natural number \(n\) greater than \(1\) such that only \(1\) and \(n\) are divisors of \(n\). Primes are of theoretical interest but they are also used, for example, to achieve secure online banking.
The aim of this exercise is to show that there are infinitely many primes. You may use without proof that any integer can be written as a product of primes.
Question a#
Show that for every natural number \(n\) greater than \(1\), there exists at least one prime that is a divisor of \(n\).
Hint
Assume that there are natural numbers \(n\) greater than \(1\) that have no prime divisors. Then there exists a smallest possible natural number \(N\) greater than \(1\) that has no prime divisors. Show that this leads to a contradiction.
Question b#
Assume that there are only finitely many primes. Show that there then exists a natural number \(N\) greater than \(1\) that has no prime divisors.
Hint
Euclid (around 300 BCE) had the following idea: If there only are finitely many primes, let’s say \(p_1,\dots,p_\ell\), which primes are then divisors of the number \(1+p_1\cdot \cdots \cdot p_\ell\)?
Question c#
Conclude from Questions a og b that there in fact are infinitely many primes.
Extra Exercise 2: A Few Words on Boolean Algebra#
When logical operations take place inside a computer, two bit values \(0\) and \(1\) are used for truth values: \(1\) represents \(\mathrm T\) and \(0\) represents \(\mathrm F\). This redefinition allows for other ways of describing logical operations, and is related to a structure known as Boolean algebra.
Question a#
Applying the usual arithmetic multiplication on the numbers \(0\) and \(1\) produces the following multiplication table for bits, which we now interpret as a truth table:
\(P\) |
\(Q\) |
\(P\cdot Q\) |
|---|---|---|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Which logical operation does multiplication describe?
Answer
AND \(\wedge\).
Question b#
We define the operator \(\oplus\) on the bit values \(0\) and \(1\) as follows: \(0\oplus 0=0\), \(0\oplus1=1\), \(1\oplus 0=1\) and \(1\oplus 1=0\). We will call this operation addition, although not exactly the usual arithmetic addition. This produces the following table, which we again interpret as a truth table:
\(P\) |
\(Q\) |
\(P\oplus Q\) |
|---|---|---|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
Which logical operation does addition describe?
Hint
Have a look at Exercise 2 from the ordinary exercise programme.
Answer
XOR (“exclusive or”).
Question c#
How should we interpret \(1 \oplus P\)?
Answer
As \(\neg P\).
Question d#
What is the truth table of the logical expression \(P\cdot (1 \oplus Q)\)? Also, try to formulate a logical expression that takes the truth value \(1\) if \(P=1\) and \(Q=1\), and otherwise takes the value \(0\).
Question e#
Let \(a,b,c,d \in \{0,1\}\) be bit values. Find a logical expression \(X\) containing \(P\) and \(Q\) whose truth table is:
\(P\) |
\(Q\) |
\(X\) |
|---|---|---|
1 |
1 |
a |
0 |
1 |
b |
1 |
0 |
c |
0 |
0 |
d |
Hint
Two logical expressions can be added together using \(\oplus\). Note that \(P \oplus P =0\) for any value of \(P\).
How can disjunction \(\vee\) be described using addition and multiplication of bit values?
Answer
\(P \vee Q\) can be described as \(P\cdot Q \oplus (1\oplus P)\cdot Q \oplus P\cdot(1 \oplus Q)=P \oplus Q \oplus P \cdot Q.\)