Selecting integers from a set

[Tomas314]

An odd prime number [MATH]p[/MATH] and a [MATH](p + 1)[/MATH] element set [MATH]S[/MATH] of integers are given.
Prove that from [MATH]S[/MATH] it is possible to choose unique numbers [MATH]a_1, a_2, a_3, \dots, a_{p-1}[/MATH]* such that [MATH]1\cdot a_1+2\cdot a_2+\cdots + (p-1)a_{p-1}[/MATH] is a multiple of [MATH]p[/MATH].

\* [MATH]a_1 \neq a_2 \neq ... a_{p-1}[/MATH]
My observations

If [MATH]p[/MATH] is odd, then [MATH]S[/MATH] contains an even number of elements, that is, the last term [MATH](p-1)a_{p-1}[/MATH] must also be even, that's all for now.

 

[Steven G]

You really have to try.

Maybe look at some specific cases and see if can learn from them.

Please try with p=3, 5 and 7. Do you see why it works for those numbers? Can you generalize things?

 

[Tomas314]

If [MATH]p=3[/MATH], then [MATH]S={a_1,a_2,a_3,a_4}[/MATH] and [MATH]1\cdot a_1+2\cdot a_2=k3,\, k \in Z[/MATH]. So the expession is eaqual to [MATH]a_1-a_2=3(k-a_2) \implies a_1-a_2=3\alpha,\, \alpha \in Z[/MATH]. For a dispute, suppose that you cannot select a pair whose difference would be divisible by three, so [MATH]a_1=x, a_2=x+2, a_3=x+4 [/MATH] but [MATH]a_4[/MATH] we cannot choose such (I have not yet come up with a proof). This is for [MATH]p=3[/MATH].

 

[Tomas314]

You really have to try.

Maybe look at some specific cases and see if can learn from them.

Please try with p=3, 5 and 7. Do you see why it works for those numbers? Can you generalize things?

Hi,

Thank you very much for your advice. I started with the case where [MATH]p = 3[/MATH], So [MATH]a_1+2a_2 = 3k[/MATH], where [MATH]k[/MATH] is in integers, I converted it into [MATH]a_1 - a_2 = 3(k - a_2) \implies a_1 - a_2 = 3 \alpha [/MATH], where [MATH]\alpha[/MATH] is in integers.

If we take all four numbers from that set and divide each by 3, then we get a total of 4 residues, if we divide them into residual classes after division by three (0, 1, 2), then in one of them there will be, according to Dirichlet's principle, two identical residues. And the difference of two numbers with the same remainder after dividing three is the result of a multiple of three.

Now, [MATH]a_1 + 2a_2 + 3a_3 + 4a_4 = 5k, \, a_1, a_2, a_3, a_4 \in S[/MATH], and what I do is [MATH]a_1 - a_4 + 2(a_2 - a_3) = 5\alpha[/MATH]. And I am stuck, coul you help me?

Thank you in advance.