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
$\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$
    – William
    Sep 27 '19 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$ Sep 27 '19 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$
    – William
    Sep 27 '19 at 3:35
  • $\begingroup$ Yes I changed my answer, I was assuming they had to be unique. $\endgroup$
    – J P
    Sep 27 '19 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$
    – William
    Sep 27 '19 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 '19 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.