Q1

How many solutions does the congruence

have? What about the congruence

?

Q2 (18.2 from the textbook)

It may appear that RSA decryption does not work if the message a is not relatively prime to the modulus n=pq (p,q are distinct primes).

Show that in fact RSA works for all messages.