<em>Z</em> modulo <em>n</em>

Tato úloha neprošla kontrolou správnosti.

Z modulo n

Úloha číslo: 1303

V úlohách se často počítá nad konečnými tělesy \(\mathbb{Z}_p.\) V této úloze si ukážeme, jak se nad těmito strukturami počítá.

(i) Ekvivalence modulo \(n\)

Dvě čísla \(a,b\in \mathbb{Z}\) jsou ekvivalentní (kongruentní) v modulo \(n\), jestliže mají stejný celočíselný zbytek po dělení přirozeným číslem \(n\).

Díky takto udané ekvivalenci se množina všech celých čísel „rozpadne“ na třídy ekvivalence. V každé třídě ekvivalence jsou všechna celá čísla dávající stejný zbytek při dělení číslem \(n\). Uvědomte si, že žádné celé číslo nemůže být současně ve dvou třídách. Daný „rozpad“ množiny \(\mathbb{Z}\) představuje disjunktní rozklad.

Například jedna z tříd ekvivalence \(\mathrm{mod\,}3\) vypadá takto

\[\big\{\ldots,\,-7,\,-4,\,-1,\,2,\,5,\,8,\,11,\,\ldots\big\},\]

neboť všechny z čísel v této množině dávají při celočíselném dělení číslem \(3\) stejný zbytek \(2\).

Každé této třídě ekvivalentních prvků můžeme přiřadit vhodného reprezentanta – právě celočíselný zbytek po dělení číslem \(n\).

Vzhledem k tomu, že po dělení číslem \(3\) můžeme dostat pouze zbytky \(0,\,1,\,2\), bude množina všech reprezentantů

\[\mathbb{Z}_3 = \big\{0,\,1,\,2\big\}.\]

V obecném případě dělení číslem \(n\) bychom získali množinu reprezentantů

\[\mathbb{Z}_n = \big\{0,\,1,\,2,\,\ldots,\,n-1\big\}.\] Na zavedené množině \(\mathbb{Z}_n\) můžeme udat operace sčítání a násobení modulo \(n\).

(ii) Operace sčítání a násobení modulo \(n\)

Nechť \(a,b\) jsou prvky množiny \(\mathbb{Z}_n\).

Součtem modulo \(n\) čísel \(a,b\) rozumíme nejmenší nezáporný zbytek při dělení standardního součtu celých čísel \(a,b\) číslem \(n\).
Součinem modulo \(n\) čísel \(a,b\) rozumíme nejmenší nezáporný zbytek při dělení standardního součinu celých čísel \(a,b\) číslem \(n\).

Například \[ \begin{eqnarray} 4+7 &=& 1\quad (\mathrm{mod\,} 10), \\ 4+3 &=& 2\quad (\mathrm{mod\,} 5), \\ 4\,\cdot\, 6 &=& 3\quad (\mathrm{mod\,} 7), \\ 2\,\cdot\, 2 &=& 1\quad (\mathrm{mod\,} 3). \\ \end{eqnarray} \]

Lze ukázat, že struktura \((\mathbb{Z}_p;+,\,\cdot\,)\), kde \(p\) je prvočíslo a operace jsou sčítání a násobení modulo \(p\), je komutativní těleso (pole). Při počítání lze tedy využívat komutativity, asociativity a distributivity.

Počítání nad těmito poli si hned procvičíme.

Úkol:

Nad polem \(\mathbb{Z}_5\) určete hodnotu výrazu \[4\cdot \big(4{\cdot} 3 + 4{\cdot} 2 \cdot 3{\cdot} 2 + 4 + 2{\cdot} 3^3\big) .\]
Nad polem \(\mathbb{Z}_7\) vyřešte soustavu rovnic \[ \begin{eqnarray} 2x + 3y &=& 4\\ 4x + 5y &=& 6.\\ \end{eqnarray} \]
Nad polem \(\mathbb{Z}_3\) sečtěte matice \[ \begin{pmatrix} 1 & 2 & 0\\ 2 & 2 & 1\\ \end{pmatrix} + \begin{pmatrix} 2 & 2 & 1\\ 1 & 1 & 2\\ \end{pmatrix}. \]
Nad polem \(\mathbb{Z}_5\) vyřešte rovnici \[ 3x + 3 = 4 + 4x. \]

1. Nápověda – výraz
Nad polem \(\mathbb{Z}_5\) máte určit hodnotu výrazu \[4\cdot \big(4{\cdot} 3 + 4{\cdot} 2 \cdot 3{\cdot} 2 + 4 + 2{\cdot} 3^3\big).\]
Výpočet můžete nejprve provést nad \(\mathbb{Z}\) a až poté nalézet reprezentanta v \(\mathbb{Z}_5\).

Aby se nemuselo počítat s velkými čísly, je lepší „modulit“ už v mezivýpočtech.
1. Řešení nápovědy – výraz
Výpočet můžeme nejprve provést nad \(\mathbb{Z}\) a až poté nalézt reprezentanta v \(\mathbb{Z}_5\), tj.
\[4\cdot \big(4{\cdot} 3 + 4{\cdot} 2 \cdot 3{\cdot} 2 + 4 + 2{\cdot} 3^3\big) = \overset{\color{grey}{472}}{2}.\]
Museli jsme ale počítat s velkými čísly. Proto je lepší „modulit“ již v mezivýpočtech, tj.
\[4\cdot \big(4{\cdot} 3 + 4{\cdot} 2 \cdot 3{\cdot} 2 + 4 + 2{\cdot} 3^3\big) = 4\cdot \big(\overset{\color{grey}{12}}{2} + \overset{\color{grey}{48}}{3} + 4 + \overset{\color{grey}{54}}{4}\big) = 4 \cdot \overset{\color{grey}{13}}{3} = \overset{\color{grey}{12}}{2}.\] Šedá čísla ve výpočtech si v klasickém výpočtu pouze představujeme, do výpočtu je nelze psát – takové prvky v poli \(\mathbb{Z}_5\), nad kterým počítáme, vůbec nejsou!
2. Nápověda – soustava rovnic
Nad polem \(\mathbb{Z}_7\) máte vyřešit soustavu \[ \begin{eqnarray} 2x + 3y &=& 4\\ 4x + 5y &=& 6.\\ \end{eqnarray} \]
Soustavu řešte obdobně jako nad obvyklými obory. Abyste se nad \(\mathbb{Z}_7\) zbavili některé z proměnných, snažte se sečíst vhodné násobky rovnic tak, aby v součtu proměnná figurovala v násobcích sedmi – ty jsou totiž v \(\mathbb{Z}_7\) nulami.
2. Řešení nápovědy – soustava rovnic
Budeme využívat toho, že násobky sedmi jsou nad polem \(\mathbb{Z}_7\) nuly. \[ \begin{eqnarray} 2x + 3y &=& 4 \\ 4x + 5y &=& 6 \qquad | \cdot 3\\ ----&-&-----\\ 2x + 3y &=& 4 \\ \overset{\color{grey}{12}}{5}x + \overset{\color{grey}{15}}{1}y &=& \overset{\color{grey}{18}}{4} \\ ----&-&-----\\ \overset{\color{grey}{7}}{0}x + 4y &=& \overset{\color{grey}{8}}{1} \\ ----&-&-----\\ 4y &=& 1 \qquad | \cdot 2\\ y &=& 2 \\ \end{eqnarray} \] Neznámou \(x\) dopočítáme například z první rovnice dosazením \(y=2\). \[ \begin{eqnarray} 2x + 6 &=& 4 \qquad | +1\\ 2x + \overset{\color{grey}{7}}{0} &=& 5 \\ 2x &=& 5 \qquad | \cdot 4\\ x &=& \overset{\color{grey}{20}}{6} \\ \end{eqnarray} \] Uvedená soustava má nad polem \(\mathbb{Z}_7\) řešení \(x = 6,~ y = 2\).

Můžeme provést zkoušku:
\[\mathrm{L_1} = 2{\cdot} 6 + 3{\cdot} 2 = 4 = \mathrm{P_1},\] \[\mathrm{L_2} = 4{\cdot} 6 + 5{\cdot} 2 = 6 = \mathrm{P_2}.\]
Šedá čísla ve výpočtech si v klasickém výpočtu pouze představujeme, do výpočtu je nelze psát – takové prvky v poli \(\mathbb{Z}_7\), nad kterým počítáme, vůbec nejsou!
3. Nápověda – součet matic
Nad polem \(\mathbb{Z}_3\) máte provést součet matic \[ \begin{pmatrix} 1 & 2 & 0\\ 2 & 2 & 1\\ \end{pmatrix} + \begin{pmatrix} 2 & 2 & 1\\ 1 & 1 & 2\\ \end{pmatrix}. \]
Matice sečtěte podle definice. Počítáte nad polem \(\mathbb{Z}_3\) – nezapomeňte „modulit“.
3. Řešení nápovědy – součet matic
Nad polem \(\mathbb{Z}_3\) provedeme dle definice součet matic \[ \begin{pmatrix} 1 & 2 & 0\\ 2 & 2 & 1\\ \end{pmatrix} + \begin{pmatrix} 2 & 2 & 1\\ 1 & 1 & 2\\ \end{pmatrix} = \begin{pmatrix} \overset{\color{grey}{3}}{0} & \overset{\color{grey}{4}}{1} & 1 \\ \overset{\color{grey}{3}}{0} & \overset{\color{grey}{3}}{0} & \overset{\color{grey}{3}}{0} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 0\\ \end{pmatrix} . \] Šedá čísla ve výpočtech si v klasickém výpočtu pouze představujeme, do výpočtu je nelze psát – takové prvky v poli \(\mathbb{Z}_3\), nad kterým počítáme, vůbec nejsou!
4. Nápověda – rovnice
Nad polem \(\mathbb{Z}_5\) máte vyřešit rovnici \[ 3x + 3 = 4 + 4x. \]
K rovnici nejprve přičtěte vhodný prvek pole \(\mathbb{Z}_5\) tak, aby na jedné straně nebyl absolutní člen. Dále přičtěte vhodný násobek proměnné, aby na druhé straně nebyl lineární člen. Rovnici vhodně vynásobte k nalezení hodnoty neznámé.
4. Řešení nápovědy – rovnice
Nejprve k oběma stranám rovnice přičteme dvojku. \[ \begin{eqnarray} 3x + 3 &=& 4 + 4x \qquad | +2\\ 3x &=& 1 + 4x \\ \end{eqnarray} \] Dále k oběma stranám rovnice přičteme \(x\). \[ \begin{eqnarray} 3x &=& 1 + 4x \qquad | +x \\ 4x &=& 1 \\ \end{eqnarray} \] Rovnici vynásobíme čtyřkou a dostaneme výsledek. \[ \begin{eqnarray} 4x &=& 1 \qquad | \cdot 4 \\ x &=& 4 \\ \end{eqnarray} \]
Řešením udané rovnice nad polem \(\mathbb{Z}_5\) je \(x=4.\)

Můžeme provést zkoušku \[\mathrm{L} = 3{\cdot} 4 + 3 = 0,\] \[\mathrm{P} = 4{\cdot} 4 + 4 = 0,\] \[\mathrm{L} = \mathrm{P}.\]
Odpověď
Výsledky příkladů
1. \(V = 2\),
2. \(x = 6,~y = 2\),
3. \(\left(\begin{smallmatrix}0&1&1\\0&0&0\\\end{smallmatrix}\right)\),
4. \(x=4\).

Z modulo n

Úloha číslo: 1303

1. Nápověda – výraz

1. Řešení nápovědy – výraz

2. Nápověda – soustava rovnic

2. Řešení nápovědy – soustava rovnic

3. Nápověda – součet matic

3. Řešení nápovědy – součet matic

4. Nápověda – rovnice

4. Řešení nápovědy – rovnice

Odpověď