# Pigeonhole principle with congruence

Let $$S\subset \mathbb{Z}/n\mathbb{Z}$$ where $$n$$ is even and $$n\geq2$$, and $$\mid S\mid\geq n/2$$. Show that there exist $$x, y\in S$$ with $$x+y\equiv 0 \pmod{n}$$

The hint is the pigeonhole principle and it is my first time heard about it. I read the wiki page and some posts from the form. The definitions seem very clear, but I still don't know how to use it...

Any help will be great.

Let $$n=2k$$

Then $$\Bbb{Z}/n\Bbb{Z}=\{[0],[1],...,[k],[k+1],...,[2k-1]\}$$ and $$|S| \geq k$$

If $$S$$ contains the element $$[0]$$ or $$[k]$$ then take $$x=y=0$$ or $$x=y=k$$

If $$S$$ does not contain $$[0]$$ and $$[k]$$ then it is a subset of the set $$\Bbb{Z}/n\Bbb{Z} \setminus \{[0],[k]\}$$ which contains $$2k-2$$ elements.

Take as pigeonholes the couples $$([s],[2k-s]), s=1,...,k-1$$

So we have $$k-1$$ such couples and $$|S| \geq k$$ so by pigeonhole principle $$S$$ must have at least two elements $$[s],[2k-s]$$

• Sorry, I write the question wrongly....the size of S is now updated. Updated to "$\geq$" instead “=”
– Will
Sep 27, 2019 at 4:03
• @Will It works again..i slightly updated my answer..bu it a subset $S$ that does not contains $0,k$ has more that $k$ elements then again by the same argument we can find what we want. Sep 27, 2019 at 4:08

Suppose $$S$$ does not contain $$\frac{n}{2}$$. (Or else the problem is trivial). Proceed by contradiction and suppose that no element in $$S$$ had an inverse. (Using the group theory definition here). But this is a contradiction, since every element in a group has a unique inverse and half of the elements of $$\mathbb{Z}/n\mathbb{Z}$$ are in $$S$$. (If every element had a unique inverse not in $$S$$ there would be more than $$n$$ elements of $$\mathbb{Z}/n\mathbb{Z}$$).

• if $S=\{1, 2\}, 2 + 2 \equiv 0\pmod{4}$
– Will
Sep 27, 2019 at 3:35
• Yes I changed my answer, I was assuming they had to be unique.
– J P
Sep 27, 2019 at 3:36
• Thank you for your answer, sir, but this is a number theory problem... I am afraid I can use abstract algebra concepts...
– Will
Sep 27, 2019 at 3:42
• That's fine just don't use the definition of an inverse or the language of groups. You still know that for each element $x \in \mathbb{Z} / n \mathbb{Z}$ there is a unique element $y \in \mathbb{Z} / n \mathbb{Z}$ such that $x + y \mod n = n$.
– J P
Sep 27, 2019 at 3:46