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í standartní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í standartní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:
  1. 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) .\]
  2. Nad polem \(\mathbb{Z}_7\) vyřešte soustavu rovnic \[ \begin{eqnarray} 2x + 3y &=& 4\\ 4x + 5y &=& 6.\\ \end{eqnarray} \]
  3. 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}. \]
  4. 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.

  • 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.

  • 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“.

  • 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é.

  • 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\).

Úroveň náročnosti: Vysokoškolská úloha
Úloha s vysvětlením teorie
Zaslat komentář k úloze