Question

let p be a prime number greater than 15. Determine the remainder of p^360 divided by 1001.

You may wish to use the following Proposition.
If gcd(m1,m2) = 1, then
x = a (mod m1*m2) iff
x = a (mod m1) and x = a (mod m2) let p be a prime number greater than 15. Determine the remainder of p^360 divided by 1001.

You may wish to use the following Proposition.
If gcd(m1,m2) = 1, then
x = a (mod m1*m2) iff
x = a (mod m1) and x = a (mod m2) @Mathematics

Answer 1

I did some tests and I found that the remainder seems to be 1 consistently for primes over 15

Answer 2

Since 1001= 7*11*13, we should find out:\[p^{360}\mod 7, p^{360}\mod 11,p^{360}\mod 13\]
Since p is greater than 15, (p,7)=(p,11)=(p,13)= 1
(note, (a,b) means gcd of a and b)

Using Fermat's Little Theorem, we have:\[p^{6}\equiv 1\mod7\]\[p^{10}\equiv 1\mod11\]\[p^{12}\equiv 1\mod13\]

Therefore, because 360 is divisible by 6, 10 and 12, we have:\[p^{360}\equiv 1 \mod 1001\]

Answer 3

Thanks, that makes a lot of sense