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

The product of all the prime numbers between 1 and 100 is equal to $P$. What is the remainder when $P$ is divided by 16?

I have no idea how to solve this, any answers?

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?

Yes, there is another way, if you don't mind using the computer.

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
61, 67, 71, 73, 79, 83, 89, 97]
import operator
import functools
ptot = functools.reduce(operator.mul, primes, 1)
print ptot/16

Yay python! It just multiplies all the numbers in the list together, puts it in a variable, divides that variable by 16, prints it, etc. As for the result, you get to compile it with an online compiler to find out.

Or, you know, you could do it the boring way and multiply it all and divide it with google/a calculator's help. But python is much cooler.

Edit:

Thanks to user2357112 for commenting that the OP wanted the remainder. In that case, you would use very similar code, but using the % operator instead of a normal divide:

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
61, 67, 71, 73, 79, 83, 89, 97]
import operator
import functools
ptot = functools.reduce(operator.mul, primes, 1)
print ptot%16

giving, of course, 6.