Solutions modulo square of a number.

Question

Let $p$ be a prime such that $$p^n\equiv 5 \mod{6}$$ for each odd positive integer $n$. Then how to find the values of $p^n$ modulo $36$, i.e. I need to find $$p^n\equiv ?\mod{36}.$$ Please help.

Answer 1

$N\equiv 5 \mod 6$ means $N=5+6M$ for some integer $M$. Now, write $M=6Q+r$ with $r\in\{0,\dots,5\}$. Then you have $$ N=36Q+5+6r,\quad 5+6r\in \{0,\dots,35\},$$ and thus $$ N\equiv 5,11,17,23,29,35 \mod 36.$$

Answer 2

If $p^n \equiv 5 \pmod 6$ for every odd $n$ then $p^1 \equiv 5 \pmod 6$.

(Which is okay; that means $p^{2k+1} \equiv (p^2)^k*p \equiv (25^k)*5 \equiv 1^k*5 \equiv 5 \pmod p$.

So $p = 5 + 6M$ for some $M$ and $p \equiv 5 + 6m\pmod {36}$ where $m \equiv M \pmod 6$

$p^2 \equiv (5+6k)^2 \equiv 25 + 60m + 36m^2 \equiv 1+ 24m \pmod {36}$.

So $p^n = p^{2k + 1} = p*(p^2)^k\equiv 5*(1+24m)^k\pmod {36}$

Now $(1 + 24m)^k = 1 + k*24m + {k\choose 2}*24^2m^2 + ..... $ be notice that all the $24^i; k\ge 2$ are $24^i = 3^i2^{3i}=36*3^{i-1}2^{3i - 2} \equiv 0 \pmod {36}$ so

$(1 + 24m)^k \equiv 1 + k*24m\pmod {36}$.

So $p^n \equiv 5(1 + k*24m) \equiv 5 + k*120*m \equiv 5 + 12km \pmod {36}$

Where $n = 2k + 1$ and $p \equiv 5 + 6m \pmod {36}$