[Teoria liczb] Podział zbioru reszt, podzielność

[limes123]

Spoko zadanko - mamy liczbę pierwszą \(\displaystyle{ p>17}\) i dzielimy zbiór \(\displaystyle{ \{1,2,\ldots ,p-1\}}\) na trzy rozłączne zbiory. Pokazać, że istnieją liczby \(\displaystyle{ x,y,z}\), każda z innego z tych zbiorów, takie że \(\displaystyle{ p|x+y-z}\).

[timon92]

zacznij od wypisania wszystkich trójek \(\displaystyle{ (x,y,z)}\) takich, że \(\displaystyle{ p|x+y-z}\) a następnie wykaż, że dla dowolnego podziału zbioru \(\displaystyle{ \{1,2,...,p-1\}}\) na trzy rozłączne zbiory \(\displaystyle{ A, B, C}\) istnieje trójka \(\displaystyle{ (x,y,z)}\) taka, że każdy ze zbiorów \(\displaystyle{ \{x,y,z\} \cap A}\), \(\displaystyle{ \{x,y,z\} \cap B}\), \(\displaystyle{ \{x,y,z\} \cap C}\) jest jednoelementowy

[limes123]

Spoko pomysł, dzięki.

[timon92]

spoko, nie ma za co

[limes123]

To chyba jednak nie pomaga za bardzo, jakieś inne pomysły?

[timon92]

hmmm faktycznie lipa sory

poczytaj o twierdzeniu Cauchy'ego-Davenporta, może się przydać

[timon92]

i co, przydało się?

[limes123]

Nie, a masz może jakiś pomysł, który działa?

[arek1357]

Czemu p musi być liczbą pierwszą większą lub równą od siedemnaście, czemu wogóle musi być liczbą pierwszą przecież to działa nawet dla \(\displaystyle{ p=4}\)

[timon92]

no ale dla niektórych liczb złożonych nie będzie dobrze (pewnie nawet dla żadnej liczby złożonej większej niż \(\displaystyle{ 4}\)), np. dla \(\displaystyle{ p=6}\) i zbiorów \(\displaystyle{ A=\{2\}, B=\{4\}, C=\{1,3,5\}}\) teza nie zachodzi

[arek1357]

Mam taki pomysł otóż, podzielmy zbiór:

\(\displaystyle{ X=\left\{ 1,2,3,...,p-1\right\}}\) na dowolne rozłączne: \(\displaystyle{ A,B,C}\)

Zbiór \(\displaystyle{ G=X \cup \left\{ 0\right\}}\) z działaniem plus modulo jest grupą rzędu p.

Z tego wynika, że ponieważ rząd G jest liczbą pierwszą grupa ta nie ma podgrup właściwych,
a więc żaden ze zbiorów: \(\displaystyle{ A \cup \left\{ 0\right\} ,B \cup \left\{ 0\right\},C \cup \left\{ 0\right\}}\) nie jest podgrupą właściwą zbioru \(\displaystyle{ G}\).

Tym bardziej podgrupą nie jest np:

\(\displaystyle{ A \cup B \cup \left\{ 0\right\}}\)

Skoro nie jest to grupą to musi istnieć takie: \(\displaystyle{ x \in A , y \in B}\), że:

\(\displaystyle{ x+y}\) nie należy do \(\displaystyle{ A \cup B \cup \left\{ 0\right\}}\)

znaczy, że:

\(\displaystyle{ x+y=z \in C}\)

czyli: \(\displaystyle{ x+y-z=0}\),

a co za tym idzie:

istnieją takie: \(\displaystyle{ x,y,z}\) ,że:

\(\displaystyle{ p|x+y-z}\)

cnd...

[timon92]

Skoro \(\displaystyle{ A \cup B \cup \{0\}}\) nie jest to grupą to musi istnieć takie: \(\displaystyle{ x \in A , y \in B}\), że:

\(\displaystyle{ x+y}\) nie należy do \(\displaystyle{ A \cup B \cup \left\{ 0\right\}}\)

dlaczego?

[arek1357]

Tak tu jest luka w rozumowaniu moim!

[limes123]

jakies inne pomysly?