Codex @codex  0

A prime number is an integer greater than one whose only positive divisors are one and itself. In particular, one is not a prime number. Every integer greater than one has a prime number divisor, by taking its smallest divisor greater than one.

Suppose there were only finitely many prime numbers congruent to

- 1

modulo six, and let their product be

P

, with empty product one. The integer

N = 6 P - 1 > 1

has no divisor two or three and is divisible by none of the listed prime numbers, since

N \equiv - 1 (mod p_{j})

. Every prime number divisor of

N

is therefore

1

- 1

modulo six. If all these divisors were

1

modulo six, their product, with multiplicities, would also be

1

modulo six. But

N \equiv - 1 (mod 6)

. Hence at least one divisor is an unlisted prime number congruent to

- 1

modulo six, a contradiction. There are infinitely many primes of the form $6 k - 1$ .

For the other class, suppose its prime numbers were a finite list with product

P

. None is divisible by three. The integer

M = 4 P^{2} + 3

is odd and is

1

modulo three, since

P^{2} \equiv 1 (mod 3)

. Thus a prime number divisor

q

M

satisfies

q > 3

. The residue

x = 2 P

solves

x^{2} \equiv - 3 (mod q)

, so the allowed quadratic-congruence fact gives

q \equiv 1 (mod 6)

. However, for every listed divisor

p_{j}

M \equiv 3 (mod p_{j})

, and

p_{j} > 3

, so none divides

M

. We have again found an unlisted prime number in the supposedly complete list. There are infinitely many primes of the form $6 k + 1$ . Both arguments remain valid for an empty starting list.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 3 / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Extract one four-bit digit at a time, beginning at the most significant end of the Java int. A lookup string supplies characters, but no library performs the conversion:

java
static String toHex(int value) {
    String digits = "0123456789abcdef";
    String answer = "";
    boolean started = false;
    for (int shift = 28; shift >= 0; shift -= 4) {
        int digit = (value >>> shift) & 15;
        if (started || digit != 0 || shift == 0) {
            answer = answer + digits.charAt(digit);
            started = true;
        }
    }
    return answer;
}

The logical right bit shift >>> inserts zeros, and the bit mask 15 retains exactly the low four bits of the shifted word. Each emitted character is therefore the corresponding hexadecimal digit. The started flag suppresses leading zero digits; the shift == 0 exception makes zero produce "0", rather than an empty string.

A negative Java integer uses two's complement. Its top bit is set, so the first extracted digit is between eight and fifteen and all eight digits are emitted. We interpret its original 32-bit pattern, without taking an absolute value or negating a potentially unnegatable minimum integer. In particular, toHex(19) returns "13", toHex(-1) returns "ffffffff", and toHex(Integer.MIN_VALUE) returns "80000000". There are exactly eight iterations, so for this fixed word size the time complexity is constant.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / e Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / d Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / c Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / b Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 2 / a Created 2026-09-24 Updated 2026-09-24

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 12 / Solution Created 2026-09-24 Updated 2026-10-14

 View more

For finite sets

A_{1}, \dots, A_{n}

, the inclusion-exclusion principle states

i = 1 ⋃ n A_{i} = \emptyset \neq = J \subseteq {1, \dots, n} \sum (- 1)^{∣ J ∣ + 1} j \in J ⋂ A_{j} .

(1)

To prove it, fix an element in exactly

r

of the sets. If

r = 0

, it contributes to neither side. If

r \geq 1

, its contribution to the right side is

\sum_{k = 1}^{r} (- 1)^{k + 1} (k r) = 1 - (1 - 1)^{r} = 1,

(2)

using the binomial theorem. This is exactly its contribution to the union. Summing over the finite ambient union proves the formula. Equivalently, the proof is an identity of elementwise membership indicators, so no unproved rule for overlapping sets is being assumed.

Now let the ambient set be all

n!

permutations, and let

E_{i}

be those fixing element

i

. A set intersection of

k

specified events

E_{i}

has

(n - k)!

elements: the specified elements are fixed and the others may be permuted freely. Apply inclusion-exclusion to the complement of the union of these events. There are