Remainder when $p$ is divided by $6$ 
Let $p$ be a prime. If there is a remainder of $1$ on division of $p$ by $3$, then what is the remainder when $p$ is divided by $6$? why?

I know the remainder is $1$ in both the cases, but I'm not sure how to explain why.
Help is appreciated. 
 A: We have
$$p=3k+1$$
and since $p$ is odd then $k$ is even hence $k=2k'$ so
$$p=6k'+1$$
and the result follows.
A: If $p\equiv 1\pmod3$ then either $p\equiv 1\pmod6$ or $p\equiv 4\pmod6$. But if the latter is true $p$ must be even, a contradiction.
A: Ignoring the prime-ness of $p$ for a moment, which remainders would be possible? Which of these is impossible for a prime?
A: It is not true in both cases.
If the remainder is 1
on division of $n$ by 3,
then
$n = 3m+1$
for some $m$.
We want to see
what values the remainder $k$
can take
when $n$ is divided by $6$.
In this case
$n = 6j+k$
or
$3m+1=6j+k$
or
$3(m-2j)=k-1$
and we want to choose $j$
so that
$k$ is from $0$ to $5$.
If $m$ is even,
we can choose $j$
so that
$m=2j$
so that
$k=1$.
But if $m$ is odd,
$m-2j$ is never zero,
so the smallest value
for $m-2j$ is one.
In this case,
$k=4$.
Therefore,
if $n$ leaves a remainder of 1
when divides by 3,
then $n$ must leave 
a remainder of 1 or 4
when divided by 6,
and both cases can happen.
However,
if $n$ leaves a remainder of 1
when divided by 6,
then $n$ must leave 
a remainder of 1
when divides by 3.
A: Hint:


*

*There are only two possible remainders $\bmod 2$, that is $0$ and $1$.

*There is only one prime number with $p = 0 \pmod 2$.

*Knowing the remainders of $p$ for both $2$ and $3$ you can find the remainder for $6$ using the Chinese remainder theorem.


I hope this helps $\ddot\smile$
