Necessary and/or Sufficient Conditions with Modular Math

Date: 12/01/2006 at 19:24:49
From: Sam
Subject: Modulo

If x is congruent to y modulo 10 whenever there exists an integer k 
such that x - y = 10k, identify which of the conditions below are 
"sufficient", "necessary", "necessary and sufficient" or none of these
in order that x is congruent to y modulo 10.

(a) x - y = 50
(b) x - y = 5
(c) x - y is divisible by 10  
(d) x - y is divisible by 5
(e) x - y is divisible by both 5 and 2
(f) x and y are both even

I don't understand what is meant by sufficient, necessary, and 
sufficient and necessary.

Date: 12/01/2006 at 23:05:30
From: Doctor Peterson
Subject: Re: Modulo

Hi, Sam.

A condition A is "necessary" for a result B if B is true ONLY if A is
true; that is, A HAS TO be true in order for B to be true.  We say
that B implies A, or "B only if A".

A condition A is "sufficient" for a result B if B is true WHENEVER A
is true; that is, A is ENOUGH to force B to be true.  We say that A
implies B, or "B if A".

A condition A is "necessary AND sufficient" for a result B if both of
the above are valid; we say that A is true IF AND ONLY IF B is true. 
A and B are equivalent.

As an example, suppose I asked whether "x and y are both even" is a
necessary and/or sufficient condition for the product xy to be even.
Since IF x and y are both even, THEN xy is even, it is a sufficient
condition; knowing they are both even is enough to be certain that the
product is even.  But xy will also be even if only one of the factors
is even; so having both even is NOT necessary.

See also:

  Necessary and/or Sufficient
    http://mathforum.org/library/drmath/view/60701.html 

Now look at your definition:

  x is congruent to y modulo 10 whenever there exists an integer k
  such that x - y = 10k.

In ordinary language, x and y are congruent (mod 10) if they differ by
a multiple of 10.

So we can take the first condition:

  x - y = 50

This says that x and y differ by 50, which is a multiple of 10; so
they WILL be congruent.  This is a sufficient condition.

But is it necessary?  What if x and y differed by, say, 40?  They
would still be congruent, but this condition would not be true.  So it
is NOT necessary.

If you have any further questions, feel free to write back.  Give me
whatever answers you have, and we can discuss any mistakes you've made.


- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/