Consider the following conditional statement. If p is a prime number greater than 3, then 3 has a multiplicative inverse modulo p. We can prove this by supposing the "if" clause is true, and deducing that the "then" clause is true. (Remember here that in the expression "x mod m = y", we must have 0 < y < m.) Proof. Suppose that p is a prime number greater than 3. Then 3 + p, so either p = 3k + 1 or p = 3k + 2 for some positive integer k. We consider each case in turn. Case 1: If p=3k+ 1 for some integer k, then 3- mod p = 5 5 %. because the product of this number and 3 is congruent to 1 modulo p. Case 2: If p=3k+ 2 for some integer k, then 3- mod p = because the product of this number and 3 is congruent to 1 modulo p. In all possible cases, we have shown 3 has a multiplicative inverse modulo p. Thus the statement has been proven.