Congruence modulo 43 (alternatively, equivalence modulo 43)
Let S = Z_43 (where the underscore, "_", indicates that what follows it, in this case 43, is a subscript). Let Q be a subset of S that contains ten non-zero numbers (i.e., that Q contains ten non-zero elements of S). Prove that Q contains four distinct numbers "a," "b," "c," "d" such that ab = cd in Z_43.
Attachments
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" ...
Solution Summary
A detailed, step-by-step proof (of the statement that Q contains four distinct numbers "a," "b," "c," "d" such that ab = cd in Z_43) is provided.