Exercise 1.3.10 (Any positive integer of the form $3k+2$ has a prime factor of the same form)

Proof.

(a)

Let $n$ be a positive integer of the form $n=3k+2$. Then $n\ne 1$ has a decomposition in prime factors $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}$.

Assume for contradiction that $p_i\equiv 1(\mathit{mod}3)$ for all indices $i\in [[1,l]]$, then $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}\equiv 1(\mathit{mod}3)$, so $n$, of the form $3k+1$, is not of the form $3k+2$. This contradiction shows that there is some prime $p=p_i$ such that $p\not\equiv 1(\mathit{mod}3)$. But $p\not\equiv 0(\mathit{mod}3)$, otherwise $p=3$, and $p=3\mid n=3k+2$, so $3\mid 2$: this is absurd. Therefore $p\equiv 2(\mathit{mod}3)$, i.e. $p$ is a prime factor of $n$ of the form $3k+2$.

With some “copy and paste”:

(b)

Let $n$ be a positive integer of the form $n=4k+3$. Then $n\ne 1$ has a decomposition in prime factors $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}$.

Assume for contradiction that $p_i\equiv 1(\mathit{mod}4)$ for all indices $i\in [[1,l]]$, then $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}\equiv 1(\mathit{mod}4)$, so $n$ is not of the form $4k+3$. This contradiction shows that there is some prime $p=p_i$ such that $p\not\equiv 1(\mathit{mod}4)$. But $p\not\equiv 0\text{ or }2(\mathit{mod}4)$, otherwise $p$ is even, so $p=2\mid n=4k+3$, which gives $2\mid 3$: this is absurd. Therefore $p\equiv 3(\mathit{mod}4)$, i.e. $p$ is a prime factor of $n$ of the form $4k+3$.

(c)

Let $n$ be a positive integer of the form $n=6k+5$. Then $n\ne 1$ has a decomposition in prime factors $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}$.

Assume for contradiction that $p_i\equiv 1(\mathit{mod}6)$ for all indices $i\in [[1,l]]$, then $n=p_1^{a_1}{p}_2^{a_2}\cdots p_l^{a_l}\equiv 1(\mathit{mod}6)$, so $n$ is not of the form $6k+5$. This contradiction shows that there is some prime $p=p_i$ such that $p\not\equiv 1(\mathit{mod}6)$. But $p\not\equiv 0,2\text{ or }4(\mathit{mod}6)$, otherwise $p$ is even, so $p=2\mid n=6k+5$, so $2\mid 5$: this is absurd. Moreover $p\not\equiv 3(\mathit{mod}6)$, otherwise $3\mid p$, so $p=3\mid n=6k+5$, which gives $3\mid 5$: this is absurd. Therefore $p\equiv 5(\mathit{mod}6)$, i.e. $p$ is a prime factor of $n$ of the form $6k+5$.