# How do I rephrase this implication to be less hand-wavy?

I have a homework problem asking me to prove that it's impossible to construct a set of integers so that the set has certain characteristics. I've showed the following things:

1. It's impossible to construct a set of integers modulo 100 so that the set has the required characteristics.
2. Any set of integers with the required characteristics cannot contain two integers which are equivalent modulo 100.

How do I conclude the target assertion from these two facts? I would probably get full credit if I played the "clearly" card, but it isn't really clear (to me). Is there some simple proof by contradiction here which I'm not seeing?

-
Too abstract! Please tell us what the question is. And then, What have you showed! This way, we can tell you, how to conclude. –  user21436 Feb 14 '12 at 23:48
@KannappanSampath I think that any more detail will just confuse what I'm trying to ask. If you can, just imagine that the detail is left unspecified and you have to give a proof with only the information I gave. That will give me exactly what I need. :) But if you're really curious, the homework question is asking me to prove that it's impossible to construct a set of 52 different integers such that no two of them have a sum or difference divisible by 100. –  Brian Gordon Feb 15 '12 at 0:14

It depends on just what you mean by (1). If you mean that no set whose members are pairwise incongruent modulo $100$ can have the required characteristics, then you’re done: (1) and (2) impose contradictory requirements on a set having the required characteristics. If, on the other hand, you mean that no subset of $\{0,1,\dots,99\}$ has the required properties, then you need to show something like this:
(3) If $S$ is a set of integers with the required properties, $n\in S$, $m\equiv n\pmod{100}$, and you form a new set $S'$ by replacing $n$ by $m$, (i.e., $S'=(S\setminus{m})\cup{m}$), then $S'$ also has the desired properties.
Then you can argue as follows. Suppose that $S$ is a set of integers with the required characteristics. Using (3) repeatedly, replace each member of $S$ by the unique member of $\{0,1,\dots,99\}$ congruent to it. The resulting set set still has the required characteristics, contradicting (1).