Explore BrainMass

Explore BrainMass

    Congruence modulo 43 (alternatively, equivalence modulo 43)

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    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 December 24, 2021, 5:05 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.