I have two problems I'm working on that I can't figure out. Could anyone please help?(adsbygoogle = window.adsbygoogle || []).push({});

1. show that if p and q are distinct odd primes, then pq is a pseudoprime to the base 2 iff order of 2 modulo p divides (q-1) and order of 2 modulo q divides (p-1)

I've been trying this proof by manipulating 2^(p-1)(q-1) congruent to 1 (mod pq) and 2^p congruent to 2 (modp) and 2^q congruent to 2 (modq) I also was trying to play around with the thm if (a,n)=1 n>0 then a^i congruent to a^j (modn) iff i is congruent to j (mod order of a modulo n) but I can't come up with anything.

2. Find the number of incongruent roots modulo 6 of the polynomial x^2 - x

I don't know how to solve this problem modulo 6 I only know how to solve it modulo p where p is a prime. Could anyone help me?

Thanks

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Roots and order of an integer

**Physics Forums | Science Articles, Homework Help, Discussion**