Модуларна аритметика — разлика између измена
Садржај обрисан Садржај додат
. |
. |
||
Ред 18:
Напомена у вези нотације: Пошто је уобичајено да се истовремено разматра неколико релација конгруенције за различите модуле, и модули се укључују у нотацију. Упркос овом тернарном запису, релација конгруенције по датом модулу је [[бинарна релација|бинарна]]. Ово би било јасније када би се користио запис ''-{a}-'' {{unicode|≡}}<sub>-{n}-</sub> ''-{b}-'' уместо традиционалног записа.
== Особине конгруенције ==
Следе својства која чине ову релацију релацијом конгруенције (у односу на сабирање, одузимање и множење).
;Пропозиција 1
* Нека су <math>a, a', b, b'</math> цели бројеви те <math>n</math> природан број. Нека је
<math>a \equiv a' (mod \ n)</math> и <math>b \equiv b' (mod \ n)</math> тада вреди
#<math>a+b \equiv a'+b' (mod \ n)</math>
#<math>a-b \equiv a'-b' (mod \ n)</math>
#<math>a\times b \equiv a'\times b' (mod \ n)</math>
;Доказ
Нека је <math>a-a'= mn</math> и <math>b-b' = m'n</math>.
: <math>ab- a'b'= ab-ab'+ab'-a'b'=a(b-b')+(a- a')b'=am'n+ b'mn</math>
: <math>n</math> дели <math>ab- a'b'</math> те је <math>ab \equiv a'b' (mod \ n)</math>
* Нека су <math>a, b, c</math> цели бројеви и <math>n</math> природан број. Нека су бројеви <math>a</math> и <math>n</math> релативно прости.
Тада вреди
<math>ab \equiv ac (mod \ n)=> b \equiv c (mod \ n)</math>
;Доказ
Како су <math>a</math> и <math>n</math> релативно прости, постоје цели бројеви <math>x</math> и <math>y</math> такви да је <math>ax + ny = 1</math>. Из конгруенције
<math>ab \equiv ac (mod \ n)</math> => постоји цели број <math>k</math> такав да је <math>a(b - c) = nk</math>. Множењем претходне једнакости са <math>x</math>, из <math>ax = 1 - ny</math> добија се <math>(b - c) - ny(b - c) = nkx</math>. Очито <math>n</math> дели <math>b - c</math> те је <math>b \equiv c (mod \ n)</math>
Ова тврдња не вреди генерално, тј. ако <math>a</math> и <math>n</math> нису релативно прости.
;Пример
*<math>60 \equiv 20 (mod \ 5)</math> тачно
*<math>6 \equiv 2 (mod \ 5)</math> није тачно
;Пропозиција 2
Нека је <math>ax \equiv ay (mod \ n)</math>
Тада вреди и <math>x \equiv y (mod \ n/d)</math>, где је <math>d = (a, n)</math>.
;Доказ
<math>ax \equiv ay (mod \ n)=></math>
постоји цели број <math>k</math> такав да вреди <math>ax - ay = kn.</math> Одатле је <math>\frac{a}{d}(x-y)=\frac{nk}{d}</math>, те је <math>\frac{n}{d}| \frac{a}{d}(x-y)</math>
Како су <math>\frac{n}{d}</math> и <math>\frac{a}{d}</math> релативно прости, јер немају заједничких простих фактора, добија се n
<math>d | (x - y)</math> чиме је тврдња доказана.
;Пропозиција 3
Нека је <math>n</math> природан број, те су <math>a</math> и <math>b</math> цели бројеви такви да је <math>a \equiv b (mod \ n)=></math>
Тада за полином <math>p(x)</math> са целобројним коефицијентима вреди
<math>p(a) \equiv p(b) (mod \ n)=></math>
;Доказ
Применом предходних пропозиција на
: <math>p(a)=\sum_{i=0}^k c_ia^i</math> добија се
: <math>a^i \equiv b^ i (mod \ n)</math> те
: <math>c_ia^i \equiv c_ib^ i (mod \ n)</math>
саберу ли се добијене конгруенције добија се
<math>p(a)=\sum_{i=0}^k c_ia^i \equiv \sum_{i=0}^k c_ib^i =p(b)</math>
;Пропозиција 4
Нека су <math>n_1, n_2,... n_k</math> природни бројеви. Тада су следеће тврдње еквивалентне:
<math>a \equiv b (mod \ n_i), i= 1, 2, ... k </math>
<math>a \equiv b (mod [ n_1, n_2,... n_k </math>
;Пример
Одредити <math>x \in \Z</math> за који вреди
<math>341x \equiv 1(mod \ 17)</math>
<math>340:17=2</math> (340 је дељиво са 17) tj.
<math>340x \equiv 0 (mod \ 17)</math>
Како је
<math> 341x =340x+x</math> добија се
<math>341x \equiv x (mod \ 17)</math>
Дату конгруенцију задовољава сваки цели број <math>x</math> који је конгруентан <math>1</math> modulo <math>17</math>, тј.
<math>x \in \begin{Bmatrix}
. . . ,-33,-16, 1, 18, 35, ...
\end{Bmatrix}
</math>.
== Потпуни и редуковани систем остатака ==
Нека је <math>n</math> природан број већи од <math>1</math>. Скуп <math>S = \begin{Bmatrix}
a_1, a_2, ... , a_n
\end{Bmatrix}</math> се назива потпуни систем остатака модуло <math>n</math> ако за сваки цели број <math>b</math> постоји јединствени <math>a_i \in S</math> за који вреди
<math>b \equiv a_i (mod \ n)</math>.
Сваки потпуни систем остатака модуло <math>n</math> има тачно <math>n</math> елемената. Такође, сваки -{''n''}--члани скуп који се састоји од целих бројева међусобно неконгруентних модуло <math>n</math> представља један потпуни сустем остатака модуло <math>n</math>.
Најчешће кориштен потпун систем остатака модуло <math>n</math> је скуп <math>\begin{Bmatrix}
0, 1, 2, . . . , n - 1
\end{Bmatrix}</math>
Ово су неки од потпуних система остатака модуло 5:
<math>\begin{Bmatrix}
{0, 1, 2, 3, 4}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
{-2,-1, 0, 1, 2}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
{1, 2, 3, 4, 5}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
{-10,-8,-4, 13, 39}
\end{Bmatrix}</math>
Постоји их бесконачно много.
;Лема 1
Нека је <math>\begin{Bmatrix}
{a_1, a_2, . . . , a_n}
\end{Bmatrix}</math> потпуни систем остатака модуло <math>n</math>. Тада је и <math>\begin{Bmatrix}
{b \times a_1, b \times a_2, ... , b \times a_n}
\end{Bmatrix}</math> потпуни систем остатака модуло <math>n</math>, за сваки цели број <math>b</math> за који вреди <math>(b, n) = 1</math>.
;Лема 2
Нека су <math>a</math> i <math>n</math> природни бројеви. Конгруенција <math>ax \equiv b (mod \ n_i), i = 1, 2, ... k </math> има решења ако и само ако <math>d = (a, n)</math> дели <math>b</math>. Ако је <math>x_0</math> решење конгруенције <math>\frac{a}{d}x \equiv \frac{b}{d} (mod \frac{n}{d}</math> тада су сва међусобно неконгруентна решења модуло <math>n</math> полазне конгруенције дата с <math>x_0, x_0 + \frac{n}{d}, x_0 + \frac{2n}{d},...x_0 + \frac{(d-1)n}{d}
</math>
;Пример
Скупови {1, 2, 3, 4} и {-2,-6, 6, 7} су редуковани системи остатака модуло <math>5</math>, док је {1, 5} редуковани систем остатака модуло <math>6</math>.
== Прстен класа конгруенције ==
| |||