What is the remainder when the product of the primes between 1 and 100 is divided by 16?

Skip the first prime $2$ and look for the product modulo $8$. The twenty-four odd primes $<100$ are $$3,5,7,11,13,17, 19,23,29,31,37,41, 43,47,53,59,61,67, 71,73,79,83,89,97. $$ Modulo $8$, these are $$3,5,7,3,5,1,3,7,5,7,5,1,3,7,5,3,5,3,7,1,7,3,1,1$$ so their product is $$1^53^75^67^6\equiv 3\pmod 8 $$ (where we might profit from using $x^2\equiv 1\pmod 8$ for odd $x$). Thus $P\equiv 6\pmod{16}$.

If the product of the odd primes is $8k+r$ then the product of all of them is $16+2r$. So we only need to work $\bmod 8$. We only need to find primes with residues $3,5$ and $7$. We do it as follows:

$$\begin{pmatrix} 3 && 5 && 7\\ 11 && 13 && 15 \\ 19 && 21 && 23\\ 27 && 29 && 31\\ 35 && 37 && 39\\ 43 && 45 && 47\\ 51 && 53 && 55\\ 59 && 61 && 63\\ 67 && 69 && 71\\ 75 && 77 && 79\\ 83 && 85 && 87\\ 91 && 93 && 95\\ 99\\ \end{pmatrix}$$

Then take out non-prime multiples of $3,5,7$

$$ \require{cancel} \begin{pmatrix} 3 && 5 && 7\\ 11 && 13 && \cancel{15} \\ 19 && \cancel{21} && 23\\ \cancel{27} && 29 && 31\\ \cancel{35} && 37 && \cancel{39}\\ 43 && \cancel{45} && 47\\ \cancel{51} && 53 && \cancel{55}\\ 59 && 61 && \cancel{63}\\ 67 && \cancel{69} && 71\\ \cancel{75} && \cancel{77} && 79\\ 83 && \cancel{85} && \cancel{87}\\ \cancel{91} && \cancel{93} && \cancel{95}\\ \cancel{99}\\ \end{pmatrix}$$

The only column with an odd number of remaining elements is $3\bmod 8$, so the answer is $6$

Hints:

• The primes will be $2, \pm 3, \pm 5, \pm 7$ mod $16$.
• $3 \cdot 5 = 15 \equiv -1$ mod $16$.
• $7 \cdot 7 = 49 \equiv 1$ mod $16$.

Can you take it from here?