# Puzzles

## 3n+1

Let \(S=\{3n+1:n\in\mathbb{N}\}\) be the set of numbers one more than a multiple of three.

**(i)** Show that \(S\) is closed under multiplication.

ie. Show that if \(a,b\in S\) then \(a\times b\in S\).

Let \(p\in S\) be irreducible if \(p\not=1\) and the only factors of \(p\) in \(S\) are \(1\) and \(p\). (This is equivalent to the most commonly given definition of prime.)

**(ii)** Can each number in \(S\) be uniquely factorised into irreducibles?

#### Show answer & extension

#### Hide answer & extension

**(i)** Let \(a,b\in S\). Then \(\exists \alpha,\beta\in \mathbb{N}\) such that \(a=3\alpha+1\) and \(b=3\beta+1\).

(This says that if \(a\) and \(b\) are in \(S\) then they can be written as a multiple of three plus one.)

$$a\times b=(3\alpha+1)\times (3\beta+1)$$
$$=9\alpha\beta+3\alpha+3\beta+1$$
$$=3(3\alpha\beta+\alpha+\beta)+1$$

This is a multiple of three plus one, so \(a\times b\in S\).

**(ii)** No, as \(36\times 22=4\times 253\) and 36,22,4 and 253 are all irreducible.

#### Extension

Try the task again with \(S=\{a+b\sqrt{2}:a,b\in\mathbb{Z}\}\).