[Aritmética: Teoria dos Números – Números naturais – Divisibilidade – Máximo Divisor Comum MDC – Relação de Bézout]
Sejam a, b naturais. Mostre que existem x, y inteiros, tais que ax + by = mdc(a, b).
─────
Obs.: Gentileza detalhar e justificar corretamente cada afirmação feita no decorrer da sua demonstração, caso contrário, a sua resposta não será considerada. [tex]\,[/tex]
Considere o conjunto S de todas as combinações lineares positivas de a e b, isto é:
S = {au + bv; au + bv > 0, u, v ∈ Z}.
Podemos notar que inicialmente S ≠ Ø. Se a ≠ Ø então |a| = au + b.0, onde u = 1 se a > 0 ou u = -1 se a < 0. Logo, |a| > 0 e portanto pertence a S. Pelo Princípio da Boa Ordenação S possui um menor elemento, o qual podemos chamar de d. Pela definição de S, existem inteiros x e y tal que d = ax + by. Podemos afirmar que d = mdc(a,b).
Pelo algoritmo da Divisão, existem q e r tal que a = qd + r, com 0≤r<d. Assim:
r = a - qd = a - q(ax + by) = a(1 - qx) + b(-qy) ⇒ r ∈ S
Como r < d, isso contradiz o fato de d ser o menor elemento de S. Dessa maneira r = 0 o que dá a = qd ou equivalentemente d|a. De modo similar, segue-se que d|b. Assim, temos que d é um divisor comum entre a e b.
Tomando c um outro divisor comum de a e b. Temos que c|(ax + by) = d e c = |c| ≤|ax + by| = |d| = d. Por fim d = mdc(a,b)
Saiba mais sobre Relação de Bézout: https://brainly.com.br/tarefa/54807012
Lista de comentários
Verified answer
Foi possível mostrar que ax + by = mdc(a, b).
Relação de Bézout
Considere o conjunto S de todas as combinações lineares positivas de a e b, isto é:
Podemos notar que inicialmente S ≠ Ø. Se a ≠ Ø então |a| = au + b.0, onde u = 1 se a > 0 ou u = -1 se a < 0. Logo, |a| > 0 e portanto pertence a S. Pelo Princípio da Boa Ordenação S possui um menor elemento, o qual podemos chamar de d. Pela definição de S, existem inteiros x e y tal que d = ax + by. Podemos afirmar que d = mdc(a,b).
Pelo algoritmo da Divisão, existem q e r tal que a = qd + r, com 0≤r<d. Assim:
Como r < d, isso contradiz o fato de d ser o menor elemento de S. Dessa maneira r = 0 o que dá a = qd ou equivalentemente d|a. De modo similar, segue-se que d|b. Assim, temos que d é um divisor comum entre a e b.
Tomando c um outro divisor comum de a e b. Temos que c|(ax + by) = d e c = |c| ≤|ax + by| = |d| = d. Por fim d = mdc(a,b)
Saiba mais sobre Relação de Bézout: https://brainly.com.br/tarefa/54807012