Finding Roots and Order of an Integer: Two Problems in Number Theory

[buzzmath]

I have two problems I'm working on that I can't figure out. Could anyone please help?

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

 

[NateTG]

You should be looking at $2^{pq-1}$ for part one.

For part two, you might want to solve the problem for the prime factors of 6 to start.

 

[buzzmath]

for part one would saying that since we know that p doesn't divide p-1 and q doesn't divide q-1 then the orders have to divide the other primes for it to be a solution?

and part 2 i know that in the prime factors that the two factors can't have more than 2 incongruent roots by lagrange's theorem but how do I know exactly how many incongruent roots and how would I apply that to 6?

 

[shmoe]

... and 2^p congruent to 2 (modp) and 2^q congruent to 2 (modq)...

This may be just a typo and not a problem with your work, but you've swapped p and q in the modulus, the order of 2 mod p divides q-1 means 2^q=2 mod p, etc.

I'm not sure what you're asking in your second post, it's not clear which orders you're alking about, mod p? mod q?

Can you prove either direction of this if and only if statement?

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?

There are only 6 possibilities mod 6, you can check them all.

If you want to revert to the prime case, if x is a root mod 6 if and only if it is a root mod 2 and mod 3. Solve the mod 2 and 3 cases, then work out which numbers mod 6 fit the bill.