Súčet zvyškových tried cez súčty prvkov

[Martin Sleziak]

$\newcommand{\Z}{\mathbb Z}\newcommand{\kong}[3]{#1\equiv #2\pmod{#3}}$

Nech $x,y,n\in\Z$. Ukážte, že množina
$$\{a+b; a,b\in\Z, \kong axn, \kong byn\}$$
sa rovná zvyškovej triede čísla $x+y$ modulo $n$. T.j. že do tejto množiny patria presne také čísla $c$, ktoré spĺňajú $\kong c{x+y}n$.

Riešenie.
Chceme ukázať rovnosť týchto dvoch množín:
\begin{align*}
S&=\{a+b; a,b\in\Z, \kong axn, \kong byn\}\\
T&=\{c\in\Z; \kong c{x+y}n\}
\end{align*}

V množine $S$ sú presne súčty prvkov takých, že jeden leží v triede $x$-u a druhý v triede $y$-u.
Množina $T$ je zvyšková trieda čísla $x+y$

$\boxed{S\subseteq T}$ Z kongruencií $\kong axn$ a $\kong byn$ vyplýva
$$\kong{a+b}{x+y}n.$$
Teda každý prvok z $S$ patrí do $T$.
$$\left.
\begin{aligned}
\kong axn\\
\kong byn
\end{aligned}
\right\}\Rightarrow
\kong{a+b}{x+y}n
$$


$\boxed{T\subseteq S}$ Nech $c\in T$. Chceme ukázať, že existujú $a$ a $b$ také že
\begin{gather*}
\kong axn,\\
\kong byn,\\
c=a+b.
\end{gather*}
Ak položíme $a=x$, $b=c-x$, tak samozrejme platí $a+b=c$.
Súčasne máme:
\begin{gather*}
\kong c{x+y}n\\
\kong {c-x}yn
\end{gather*}
Teda $b=\kong{c-x}yn$. Samozrejme, platí aj $a=\kong xxn$.
Skutočne sme teda vyjadrili $c$ ako súčet dvoch čísel $a$, $b$ takých, že $\kong axn$ a $\kong byn$.

$\square$

[Martin Sleziak]

Vlastne väčšina riešení, ktoré som dostal, vyzerala tak, že ste dokázali iba jednu inklúziu.$\newcommand{\Z}{\mathbb Z}\newcommand{\kong}[3]{#1\equiv #2\pmod{#3}}$
Aby som ich mohol okomentovať, jedno z nich som sem prepísal - ostatné vyzerali do značnej miery podobne.
(Ohodnotil som to tak, že ste dokázali jednu inklúziu, čiže to je polovica úlohy. U tých, ktorí už majú dosť bodov za d.ú., na bodovom hodnotení reálne nezáleží.)

Keďže $\kong axn$ a $\kong byn$ tak $n\mid a-x$ a $n\mid b-y$.
Ak $n$ delí dve čísla tak delí aj ich súčet $n\mid a+b-(x+y)$
Odtiaľ dostávame $\kong{a+b}{x+y}n$.

Teda existuje také $c$, že $\kong c{x+y}n$. Z tranzitívnosti dostávame, že $c\equiv\kong{x+y}{a+b}n$, teda $$\kong c{a+b}n.$$

Takže množina všetkých takých $c$, kde $\kong c{x+y}n$ je zhodná s množinou $\{a+b; a,b\in\Z, \kong axn, \kong byn\}$.

Aspoň trochu sa vás pokúsim presvedčiť, že v takýchto riešeniach naozaj niečo chýba.

Stručne sa to dá povedať aj takto: Snažím sa ukázať, že $c$ sa dá zapísať v tvare $c=a+b$ (pričom $a$, $b$ majú spĺňať nejakú podmienky.)
Ak nikde v riešení nie je povedané, čo sú $a$ a $b$ resp. ako sa dajú nájsť alebo odkiaľ s istotou viem, že existujú, tak tam evidentne niečo chýba.
(Opačný smer je trochu iný; tam mám zadané $a$, $b$ a snažím sa ukázať

Inak povedané:
Ukázali ste, že ak mám prvok tvaru $c=a+b$ (kde $a$, $b$ spĺňajú to čo treba), tak $c$ leží vo zvyškovej tried $\overline{x+y}$.
Treba ale ešte aj obrátene ukázať, že každý prvok $c\in\overline{x+y}$ sa dá napísať ako súčet ako súčet takýchto dvoch čísel.

[Martin Sleziak]

Z tejto úlohy vidíme iný pohľad na súčty zvyškových tried.

Ak sme definovali sčitovanie zvyškových tried predpisom
$$\overline x + \overline y = \overline{x+y},$$
tak tento predpis nejakým spôsobom využíva to, že som si zo zvyškovej triedy vybral niektorého reprezentanta.
Teda aby to bola zmysluplná definicia, musím sa presvedčiť, že výsledok bude rovnaký bez ohľadu na to, akého reprezentanta si vyberieme.
T.j. treba vyriešiť otázku, či je binárna operácia dobre definovaná. O takomto termíne sme sa už rozprávali, pridám ešte raz tú istú linku, ako vtedy: viewtopic.php?t=1293

Ak by som to definoval tak, že vezmem množinu všetkých súčtov, tak výsledok používa celú triedu a nie niektorého konkrétneho reprezentanta.
Problém s otázkou, či je to výsledok dobre definovaný, teda zmizol.
Ale na druhej strane potrebujem teraz ukázať, že výsledok je skutočne jedna zo zvyškových tried - toto som predtým mal zadarmo.