Математичні основи, Детальна інформація

Теорема. Китайська теорема про залишки. Нехай n1, n2, …, nk – взаємно прості числа. Тоді система порівнянь

x \xF0BA a1 (mod n1)

x \xF0BA a2 (mod n2)

. . . . . .. . .. . . .

x \xF0BA ak (mod nk)

має єдиний розв'язок за модулем n = n1 * n2 * … * nk.

Алгоритм Гауса розв'язку системи лінійних порівнянь з китайської теореми про залишки.

Значення x обчислюється наступним чином:

mod ni.

Приклад. Розв’язати систему порівнянь:



n = 11 * 13 = 143. Обчислимо Ni та їх обернені хначення Mi:

N1 = 143 / 11 = 13, N2 = 143 / 13 = 11

M1 = 13-1 (mod 11) = 6, M2 = 11-1 (mod 13) = 6

Таким чином

x = 5 * 13 * 6 + 8 * 11 * 6 ( mod 143) \xF0BA 390 + 528 (mod 143) \xF0BA 60

Відповідь: x = 60 (mod 143).

Приклад. Обчислити значення виразу 46 * 67 mod 561, якщо відомо розклад модуля на прості множники: 561 = 3 * 11 * 17.

Обчислимо лишки множників за модулями 3, 11 та 17.

{46 mod 3, 46 mod 11, 46 mod 17} = {1, 2, 12},

{67 mod 3, 67 mod 11, 67 mod 17} = {1, 1, 16}.

46 * 67 = {1, 2, 12} * {1, 1, 16} = {1 * 1 mod 3, 2 * 1 mod 11, 12 * 16 mod 17} = {1, 2, 5}

Тепер для обчислення значення 46 * 67 mod 561 слід розв’язати систему лінійних порівнянь