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?

Guest Nov 14, 2019

#1**+3 **

Skip the first prime 22 and look for the product modulo 88. The twenty-four odd primes <100<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.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 88, 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,13,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

15375676≡3(mod8)15375676≡3(mod8)

(where we might profit from using x2≡1(mod8)x2≡1(mod8) for odd xx). Thus P≡6(mod16)P≡6(mod16).

Thus the Answer you are looking for

6

SVS2652 Nov 14, 2019