Explore BrainMass

Explore BrainMass

    Congruence modulo 43 (alternatively, equivalence modulo 43)

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com March 4, 2021, 6:04 pm ad1c9bdddf


    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.