1
$\begingroup$

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?

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

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$.

$\endgroup$
1
$\begingroup$

Your proof is correct but is better phrased as proof of the contrapositive:

If all prime factors of $n$ are congruent to $1$ mod $6$, then so is $n$.

$\endgroup$
2
  • $\begingroup$ Yes, I agree. I was just wondering if I missed any cases. $\endgroup$
    – mandella
    Jun 9 '20 at 13:13
  • $\begingroup$ 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.) $\endgroup$ Jun 9 '20 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.