I came across this Proposition in my book, and I know it's something

[lttlbbygurl]

I came across this Proposition in my book, and I know it's something really simple that I'm missing, but I can't seem to prove it.

Let n be an odd composite integer.
a) n is a pseudoprime to the base b where gcd (b,n)=1 if and only if the order of b in (Z/nZ)* divides (n-1).
b) If n is a pseudoprime to bases b_1 and b_2 then n is pseudoprime to base b_1b_2 and also to the base b_1b_2^{-1}

 

[rasmhop]

a)
If n is a pseudoprime to the base b, then we have:
b^{n-1} \equiv 1 \pmod n
From this you should be able to derive that the order k of b in Z/nZ divides n-1, because otherwise:
b^{k} \equiv 1 \pmod n
and by the division algorithm we could find an integer r such that 0 < r < k and n-1 = kq + r, but we have:
b^{n-1}\left(b^k\right)^{-q} \equiv 1 \pmod n
which contradicts that the order is the smallest integer with the property.

On the other hand if the order k of b in Z/nZ divides n-1 we can write n-1 = kq and we have:
b^k \equiv 1 \pmod n
from which it follows that:
b^{n-1} \equiv 1 \pmod n

b)
I guess you forgot to state that \gcd(b_2,n) = 1 because otherwise b_2^{-1} makes no sense.

This is pretty similar. If n is a pseudoprime to both bases b_1 and b_2, then,
b_1^{n-1} \equiv 1 \pmod n
b_2^{n-1} \equiv 1 \pmod n
Multiplying these we get the first result, and taking inverses in the second congruence and then multiplying we get the second result.