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. (Proposition: If gcd(m1,m2)=1then x ≡ a (mod m1*m2) iff x ≡a (mod m1) and x ≡ a (mod m2).) @Mathematics

Answer 1

waterloo algebra?? owning

Answer 2

1001 can be written as 7*11*13.

By Fermat's Theorem, p^6≡1(mod 7). This means that
\[p ^{6} = 7k + 1\]for some integer k. Since p^360 = (p^6)^60 we have
\[p ^{360} = (7k + 1)^{60}\]By the Binomial Theorem we can easily see that
\[p^{360} = 7j + 1^{60} = 7j + 1\]for some integer j. Hence p^360≡1(mod 7). In the same way we can show that p^360≡1(mod 11) and p^360≡1(mod 13) since 360 is divisible by 10 and 12 respectively. Therefore, by the proposition, p^360≡1(mod 1001).