Prove: If p and q are primes and p 6= q, then (pq) = (p 1)(q 1).

The procedure of proof should follow the following format. The answer should like that.

Example

Prove:For all integers a,b,c,m where m > 0, if ab (mod m) and bc (mod m),then ac (mod m)

Proof. Let a,b,c,m be arbitrary integers, suppose that m > 0.

(1)Suppose that ab (mod m) and bc (mod m)

(2)From (1) and using a result from last class, we conclude that m(a-b) and m(b-c)

(3)From (2) and the definition of divides, a-b = mk1and b-c = mk2for some integers k1and k2

(4)From (3), we write (a-b) + (b-c) = mk1+ mk2= m(k1+ k2),which means that a - c = m(k1+ k2). By definition of divides, m(a-c)

(5)From (4) and a result from last class, m(a-c) implies that ac (mod m).