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**

Dismiss Notice

Join Physics Forums Today!

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

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**