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

M.D.C e Diofantinas

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

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

aiqixiyi108107510133211932361710329130\begin{array}{c|c|c|c} a_i & q_i & x_i & y_i \\ 108 & - & 1 & 0 \\ 75 & 1 & 0 & 1 \\ 33 & 2 & 1 & -1 \\ 9 & 3 & -2 & 3 \\ 6 & 1 & 7 & -10 \\ \smartcolor{red}3 & 2 & \smartcolor{orange}{-9} & \smartcolor{yellow}{13} \\ 0 & - & - & - \\ \end{array}

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

Multiplicar os valores por 2

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

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

{x=x0+babty=y0aabt\left\{ \begin{aligned} x = x_0 + \frac {b} {a \frown b} t\\ y = y_0 - \frac a {a \frown b} t \end{aligned} \right.
{x=18+25ty=2636t\left\{ \begin{aligned} x = -18 + 25t\\ y = 26 - 36t \end{aligned} \right.

Congruências

16x1210    16x12y=1016x {\equiv_{12}}10 \iff 16x - 12y = 10 (Resolver por diofantinas para xx)

warning

Obrigatório justificar no teste que existe solução única

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 rir_i respetivos, divide o tal MDC calculado.

{x1210x82x52\begin{cases} x {\equiv_{12}}10\\ x {\equiv_8}2\\ x {\equiv_5}2 \end{cases}

m1m2=4m_1 \frown m_2 = 4
a1a2=8a_1 - a_2 = 8
8 é divisível por 4
m1m3=1m_1 \frown m_3 = 1
a1a3=8a_1 - a_3 = 8
8 é divisível por 1
m2m3=1m_2 \frown m_3 = 1
a2a3=0a_2 - a_3 = 0
0 é divisível por 1

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

{x51x73x95\left\{ \begin{aligned} x \smartcolor{orange}{\equiv_5} \smartcolor{red}1\\ x \smartcolor{orange}{\equiv_7}\smartcolor{red}3\\ x \smartcolor{orange}{\equiv_9} \smartcolor{red}5\\ \end{aligned} \right.
rimoˊduloscinin~irnin~iResultados155637441M = 3153774556755993581400x0 = 311\begin{array}{ c|c|c|c|c|c|c } r_{i} & módulos & c_{i} & n_{i} & ñ_{i} & rn_{i} ñ_{i} & Resultados\\ \hline \smartcolor{red}1 & \smartcolor{orange}5 & 5 & 63 & 7 & 441 & M\ =\ 315\\ \smartcolor{red}3 & \smartcolor{orange}7 & 7 & 45 & 5 & 675 & \\ \smartcolor{red}5 & \smartcolor{orange}9 & 9 & 35 & 8 & 1400 & x_{0} \ =\ 311 \end{array}

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

ni=n_i = multiplicação dos elementos da coluna cic_i exceto o da própria linha

n~i=ñ_i = congruência do nin_i pelo cic_ida própria linha

M=M = produto dos módulos

x0=x_0 = soma dos rnin~irn_{i} ñ_{i} % MM

Resposta =x0+Mt= x_0 +Mt

warning

No caso de os módulos não serem primos entre si

Temos de achar o m.m.c. deles
E dispor nas suas filas respetivas onde o módulo tem de dividir o cic_i

desISTo2