# $n \equiv 5$ (mod $6$) has a prime factor $p$ of $n$ such that $p \equiv 5$ (mod $6$)

Let $$n\in \mathbb{N}$$ such that $$n \equiv 5$$ (mod $$6$$). Then there must be a prime factor $$p$$ of $$n$$ such that $$p \equiv 5$$ (mod $$6$$).

Let $$n \equiv 5$$ (mod $$6$$) such that $$n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$$ where $$p_i$$'s are distinct primes. Any prime is either congruent to $$1$$ or $$5$$ modulo $$6$$, so if all $$p_i$$ are congruent to $$1$$ (mod $$6$$), i.e. $$p_i=6k_i+1$$, for some $$k_i$$ in $$\mathbb{N}$$, then $$n=(6k_1+1)^{a_1}\cdots(6k_m+1)^{a_m}$$. But then $$n\equiv 1$$ (mod $$6$$) because the constant factor in this product will always be $$1$$.

Is this proof correct? Did I miss any details?

• You got the idea; there are primes congruent to $2$ and $3$ mod $6$, and you may wish to rule those out Jun 9 '20 at 13:07
• Which ones exactly? $2$ and $3$? Jun 9 '20 at 13:10
• Yes, those ones exactly Jun 9 '20 at 13:15

Your proof is pretty good, though you missed that there are primes congruent to $$2$$ and $$3$$ mod $$6$$ (namely, $$2$$ and $$3$$), though we would not have $$n\equiv5\pmod6$$ if $$2$$ or $$3$$ divided $$n$$.
If all prime factors of $$n$$ are congruent to $$1$$ mod $$6$$, then so is $$n$$.
• You do have to take care of when $n$ could have $2$ or $3$ as a prime factor. (This can be easily done because $5$ is coprime to both.) Jun 9 '20 at 13:14