Nonnegative Integers

please check for an error. If you can improve the solution in its
clarity/ do so. Please try and use more words to explain the proofs/
make them more elegant if possible. YOU CAN STILL PICK UP THE CREDIT,
JUST AS LONG AS YOU CHECKED THE SOLUTION.



If there is something wrong with the solution, PLEASE REWRITE THE ENTIRE
SOLUTION.







For every nonnegative integer n, there are unique nonnegative integers i
and j such that







and







To see this, consider division of n by 43, and let i and j denote the
quotient and the remainder, respectively:







j is an element of Z43, and n is said to be congruent modulo 43 to j,
which we could express by saying that n is EQUIVALENT to j (modulo 43).
(In YOUR notation, we would say that “n = j in Z43.�)



------------------------------------------------------------------



If nonnegative integers m and n are both equivalent to j (modulo 43),
then there are unique (but not necessarily DISTINCT) nonnegative
integers i1 and i2 such that







Thus







Note that m – n is a multiple of 43, since i1 – i2 is an integer.



------------------------------------------------------------------



The product mn of any pair (m, n) of nonnegative integers is also a
nonnegative integer, so mn will be equivalent to SOME element of Z43.



Thus the product ab of any two elements of Q is equivalent to SOME
element of Z43. Moreover, the difference ab – cd of the products of
any two pairs of elements of Q such that ab and cd are equivalent to the
SAME element of Z43 is a multiple of 43.



------------------------------------------------------------------



What we have to show is that there are distinct elements a, b, c, and d
of Q such that the product ab and the product cd are equivalent to the
SAME element of Z43 (modulo 43).



------------------------------------------------------------------



Since Q has 10 elements, the number of pairs (a, b) of distinct elements
of Q (i.e., the number of pairs (a, b) of elements of Q for which ) is







Note that 45 is greater than 43.



Since the number of pairs of distinct elements of Q is greater than the
number of elements of Z43, there must be at least two DIFFERENT pairs of
distinct elements of Q, which we will denote by (a, b) and (c, d), such
that the products ab and cd are equivalent to the SAME element of Z43.
Thus ab – cd is a multiple of 43.



------------------------------------------------------------------



Now and (since (a, b) is a pair of DISTINCT elements of Q, and
likewise for (c, d)). Also, the PAIRS (a, b) and (c, d) are different,
by the DEFINITION of (a, b) and (c, d). Thus we know that .



What we have NOT yet proved is that a, b, c, and d are ALL different
(i.e., we have not proved that NEITHER element of a, b is also an
element of c, d).



-------------------------------------------------------------------



Note that every element of Q is in the set 1, 2, 3, ..., 42, since the
elements of Q are chosen to be nonzero elements of Z43. Also, 43 is a
prime number, so the product of any two nonzero elements of Z43 cannot
be a multiple of 43, hence the product of any two nonzero elements of
Z43 must be equivalent to some nonzero element of Z43.



[If the product of two nonzero integers is a multiple of a prime number
p, at least one of those nonzero integers must itself be a multiple of
p. But every nonzero element of Zp is in the set 1, 2, 3, ..., p – 1,
so none of the nonzero elements of Zp is a multiple of p.]



Thus the products ab and cd are equivalent to some NONZERO element of
Z43.



-------------------------------------------------------------------



Now suppose that some element of a, b is ALSO an element of c, d). For
the sake of definiteness, suppose that a = c. (The cases a = d, b = c,
and b = d can be proved by analogous reasoning.)



Then cd = ad, and







Since ab – cd is a multiple of 43, and ab – cd = a(b – d), we know
that either a is a multiple of 43 (which can’t happen, since a is an
element of the set 1, 2, 3, ..., 42) or b – d is a multiple of 43.



Now we cannot have b – d =0, because that would mean that b = d, hence
that a, b = c, d, but, as shown earlier, we know that .



Thus b – d = 43k for some integer k with . But that can’t happen,
because b and d are DISTINCT elements of the set 1, 2, 3, ..., 42, so
the absolute value of their DIFFERENCE cannot be greater than 41, hence
it cannot be a nonzero multiple of 43.



Thus after all (and, by analogous reasoning, we know that , , and
). Thus a, b, c, and d are ALL DIFFERENT, and ab and cd are equivalent
to the SAME element of Z43 (hence in YOUR notation, “ab = cd in
Z43�).