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.