Factorise the following integers into their prime factors:
(a) $2^{20}− 1$
(b) $2^{21}− 1$
(c) $2^{24}− 1$
(a) We have $20 = 2^2 \times 5$, and so by Proposition (4.9) we have
$$ 2 \mid 20 \implies (2^{2}-1) \mid (2^{20}-1) $$
$$ 5 \mid 20 \implies (2^{5}-1) \mid (2^{20}-1) $$
So two non-trivial factors of $2^{20}-1$ are $2^2-1 =3$ and $2^5-1 = 31$. These are not the only factors.
So far we have
$$ 2^{20}-1 = 3 \times 5^2 \times 13981 $$
By trial and error, we have 11 and 31 as factors too, which leads us to
$$ 2^{20}-1 = 3 \times 5^2 \times 11 \times 31 \times 41 $$
(b) We have $21 = 3 \times 7$, and so by Proposition (4.9) we have
$$ 3 \mid 21 \implies (2^{3}-1) \mid (2^{21}-1) $$
$$ 7 \mid 21 \implies (2^{7}-1) \mid (2^{21}-1) $$
So two non-trivial factors of $2^{21}-1$ are $2^3-1 =7$ and $2^7-1 = 127$. These are not the only factors.
This quickly gives us the required prime factorisation
$$ 2^{21}-1 = 7^2 \times 127 \times 337 $$
(c) We have $24 = 2^3 \times 3$, and so by Proposition (4.9) we have
$$ 2 \mid 24 \implies (2^{2}-1) \mid (2^{24}-1) $$
$$ 3 \mid 24 \implies (2^{3}-1) \mid (2^{24}-1) $$
So two non-trivial factors of $2^{24}-1$ are $2^2-1=3$ and $2^3-1=7$. These are not the only factors.
So we have
$$ 2^{24}-1 = 3^2 \times 7 \times 266305 $$
By experimenting, we have 5 and 13 as factors, leading to a full prime factorisation
$$ 2^{24}-1 = 3^2 \times 5 \times 7 \times 13 \times 17 \times 241 $$