Nonnegative Integers

PLEASE FOLLOW THE INSTRUCTIONS:

1. No programming

2. Show all steps

3. Explain your solution process in words

4. Proofs need to be explained primarily in words. If there is a lot
of algebra, explain the process in words as well.

5. ANSWER ALL PARTS OF THE QUESTION

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).

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

) 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.

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

.

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

.

. 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 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�).