We pick two arbitrary prime numbers p and q. We let n = pq. We let e be a number that is relatively prime to (p 1)(q 1). Use Fermat's little theorem for both parts..

(i) First show there exists a number d such that 1 d < (p 1)(q 1), and ed 1 (mod (p 1)(q 1)).

(ii) Then, show x^(ed) x (mod n) for any x {0, 1, 2, . . . n 1}. Here, a fact about prime numbers may be useful: if an integer a is divided by two distinct prime numbers p and q, then a is divided by pq.