# Modular arithmetic finding the lowest number which solve equation

Let $\phi$ be Euler's totient function. There is set of natural numbers $|A| = n$. We know that there are at least 3 different two-element subsets A having this same sum (mod 50). What is the lowest possible n?

I have answers to choose for this

A) $\phi(27)$

B) $17$

C) $15$

D) $\phi(21) + 3$

I know how is modular arithmetic working nad how to find $\phi(n)$ but I don't know why the correct answer here is C and D.

So we have set A containing 15 elements. Numbers with the same sum of $(mod50)$ can be for example:

$50+100(mod 50) = 100+150(mod50) = 200+250 (mod50) = 300+350(mod50)$

So for this numbers my set A looks $A = {50,100,150,200,250,300,350}$

And we can have here 2-elements subsets like:

$\{50,100\} , \{150,200\}, \{250,300\}...$

I don't know that i am thinking about it correctly. So if there would be additional answer like

E) $10$

So E answer would be correct?

• You are correct, in fact all you need is $3$ or $4$ elements that satisfy the sum condition and the three subset condition. But I guess, the question is asking to pick choices among the ones given. Perhaps they just want to check if you know C and D are exactly the same number. – Anurag A Jan 29 '17 at 23:42
• Thank you for fast answer. – MatNovice Jan 29 '17 at 23:47

The question is a little bit ambiguous and vague, but I think it asks you to find the lowest possible number $n$, s.t. each set of $n$ elements has to have three distinct subsets of 2 elements having the same sum modulo $50$.
Here's why the answer is $15$. First if $n=15$, there are $\binom{15}{2} = 105$ subsets of 2 elements and therefore by Pigeonhole Principle at least three of them have to have the same sum modulo $50$, as there are $50$ different congruence classes modulo $50$.
Now it's enough to prove that there exists a set of $14$ elements, which doesn't satisfy the condition. As previously we have $\binom{14}{2} = 91$, so it's not impossible to find such a set, although generating one might not be an easy task.