Congruence modulo 43 (alternatively, equivalence modulo 43)

Solution Preview

The steps in the proof:

1. Let S = Z_43. We could express S as any set of 43 consecutive integers. For the sake of definiteness (and without loss of generality), we can assume that S = {0, 1, 2, 3, ..., 42}.

2. For every integer "z," there is a unique pair (i, j) of integers such that z = 43*i + j and 0 <= j <= 42 (where "<=" denotes "less than or equal to"), hence "j" is an element of Z_43. This is often expressed by stating that "z is congruent to j (modulo 43)" or by stating that "z is equivalent to j (modulo 43)." Using the terminology given in the statement of this problem, it is expressed by stating that "z = j in Z_43."

To see this, consider division of "z" by 43, and let "i" and "j" denote the quotient and the remainder in the division (we can choose "i" and "j" so that 0 <= j <= 42):

(z/43) = i + (j/43) = [(43*i) + j]/43

Multiplying both sides by 43, we obtain

z = 43*i + j

3. Let Q be a subset of Z_43 that contains 10 non-zero numbers. Since the elements of Q are integers, the product "ab" of any two elements "a," "b" of Q is an integer, hence the product "ab" ...