2
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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]$

$\endgroup$
2
  • $\begingroup$ Sorry, I write the question wrongly....the size of S is now updated. Updated to "$\geq$" instead “=” $\endgroup$
    – Will
    Sep 27, 2019 at 4:03
  • $\begingroup$ @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. $\endgroup$
    – Marios Gretsas
    Sep 27, 2019 at 4:08
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ if $S=\{1, 2\}, 2 + 2 \equiv 0\pmod{4}$ $\endgroup$
    – Will
    Sep 27, 2019 at 3:35
  • $\begingroup$ Yes I changed my answer, I was assuming they had to be unique. $\endgroup$
    – J P
    Sep 27, 2019 at 3:36
  • $\begingroup$ Thank you for your answer, sir, but this is a number theory problem... I am afraid I can use abstract algebra concepts... $\endgroup$
    – Will
    Sep 27, 2019 at 3:42
  • $\begingroup$ 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$. $\endgroup$
    – J P
    Sep 27, 2019 at 3:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .