M.D.C, Diofantinas e Congruências (Cheat Sheet)

M.D.C e Diofantinas

$a \frown b = c$, significa que c é o m.d.c. de a e b

$108x + 75y =\smartcolor{pink} 6$

$108 \frown 75 = \smartcolor{red}3 = 108 * \smartcolor{orange}{-9} + 75 * \smartcolor{yellow}{13}$

Multiplicar os valores por 2

$108 \frown 75 = \smartcolor{pink}6 = 108 * \smartcolor{orange}{-18} + 75 * \smartcolor{yellow}{26}$

Coeficientes de Bézout: $x_0 = \smartcolor{orange}{-18}, y_0 = \smartcolor{yellow}{26}$

• M.D.C. no WolframAlpha

• Diofantinas no WolframAlpha

Congruências

$16x {\equiv_{12}}10 \iff 16x - 12y = 10$ (Resolver por diofantinas para $x$)

• Congruências no WolframAlpha

Se os módulos forem primos entre si 2 a 2, há sempre solução única

Se não, temos de fazer o MDC de 2 módulos sucessivos e ver se a diferença dos $r_i$ respetivos, divide o tal MDC calculado.

$m_1 \frown m_2 = 4$
$a_1 - a_2 = 8$
8 é divisível por 4
$m_1 \frown m_3 = 1$
$a_1 - a_3 = 8$
8 é divisível por 1
$m_2 \frown m_3 = 1$
$a_2 - a_3 = 0$
0 é divisível por 1

Logo há solução (única).

$c_i =$ têm de ser primos entre si

$n_i =$ multiplicação dos elementos da coluna $c_i$ exceto o da própria linha

$ñ_i =$ congruência do $n_i$ pelo $c_i$da própria linha

$M =$ produto dos módulos

$x_0 =$ soma dos $rn_{i} ñ_{i}$ % $M$

Resposta $= x_0 +Mt$

• Sistemas de Congruências no WolframAplha