Artigos

5.5: Mais sobre GCD


Nesta seção, discutiremos alguns resultados técnicos sobre ( gcd (a, b) ).

Teorema ( PageIndex {1} label {thm: EA} )

Seja (d = gcd (a, b) ), onde (a, b in mathbb {N} ). Então [ {as + bt mid s, t in mathbb {Z} } = {nd mid n in mathbb {Z} }. nonumber ] Portanto, toda combinação linear de (a ) e (b ) é um múltiplo de ( gcd (a, b) ), e vice-versa, todo múltiplo de ( gcd (a , b) ) é expressado como uma combinação linear de (a ) e (b ).

Prova

Para resumir, deixe [S = {as + bt mid s, t in mathbb {Z} }, qquad mbox {e} qquad T = {nd mid n in mathbb { Z} }. nonumber ] Mostraremos que (S = T ) provando que (S subseteq T ) e (T subseteq S ).

Seja (x em S ). Para provar que (S subseteq T ), queremos mostrar que (x em T ) também. Estar em (S ) significa (x = as + bt ) para alguns inteiros (s ) e (t ). Como (d = gcd (a, b) ), sabemos que (d mid a ) e (d mid b ). Portanto, (a = da ') e (b = db' ) para alguns inteiros (a ') e (b' ). Então [x = as + bt = da's + db't = d (a's + b't), nonumber ] onde (a's + b't ) é um inteiro. Isso mostra que (x ) é um múltiplo de (d ). Portanto, (x em T ).

Para mostrar que (T subseteq S ), basta mostrar que (d in S ). A razão é, se (d = as + bt ) para alguns inteiros (s ) e (t ), então (nd = n (as + bt) = a (ns) + b (nt) ) implica que (nd in S ).

Para provar que (d in S ), considere (S ^ + ). Como (a = a cdot1 + b cdot0 ), temos (a in S ^ + ). Portanto, (S ^ + ) é um conjunto não vazio de inteiros positivos. O princípio da boa ordem implica que (S ^ + ) tem um elemento menor. Chame-o de (e ). Então [e = as ^ * + bt ^ * nonumber ] para alguns inteiros (s ^ * ) e (t ^ * ). Já sabemos que (a in S ^ + ). Sendo o menor elemento em (S ^ + ), devemos ter (e leq a ). Então (a = eq + r ) para alguns inteiros (q ) e (r ), onde (0 leq r 0 ), então [r = a-eq = a- (como ^ * + bt ^ *) q = a (1-s ^ * q) + b (-t ^ * q). nonumber ] Isso torna (r ) uma combinação linear de (a ) e (b ). Como (r> 0 ), encontramos (r em S ^ + ). Visto que (r

Seja (f ) qualquer divisor comum de (a ) e (b ). Então (f mid a ) e (f mid b ). Segue-se que (f mid (ax + by) ) para quaisquer inteiros (x ) e (y ). Em particular, (f mid (as ^ * + bt ^ *) = e ). Portanto, (f leq e ). Uma vez que (e ) é em si um divisor comum de (a ) e (b ), e acabamos de provar que (e ) é maior do que qualquer outro divisor comum de (a ) e (b ), o próprio inteiro (e ) deve ser o maior divisor comum. Segue-se que (d = gcd (a, b) = e in S ^ + ). A prova está concluída.

Corolário ( PageIndex {2} )

O maior divisor comum de dois inteiros diferentes de zero (a ) e (b ) é o menor inteiro positivo entre todas as suas combinações lineares. Em outras palavras, ( gcd (a, b) ) é o menor elemento positivo no conjunto ( {as + bt mid s, t in mathbb {Z} } ).

Corolário ( PageIndex {3} )

Para quaisquer inteiros diferentes de zero (a ) e (b ), existem inteiros (s ) e (t ) tais que ( gcd (a, b) = as + bt ).

Prova

O Teorema 5.5.1 sustenta que o conjunto de todas as combinações lineares de (a ) e (b ) é igual ao conjunto de todos os múltiplos de ( gcd (a, b) ). Como ( gcd (a, b) ) é um múltiplo de si mesmo, deve ser igual a uma dessas combinações lineares. Assim, ( gcd (a, b) = sa + tb ) para alguns inteiros (s ) e (t ).

Teorema ( PageIndex {4} )

Dois inteiros diferentes de zero (a ) e (b ) são relativamente primos se e somente se (as + bt = 1 ) para alguns inteiros (s ) e (t ).

Prova

O resultado é uma consequência direta da definição de que (a ) e (b ) são considerados relativamente primos se ( gcd (a, b) = 1 ).

Exemplo ( PageIndex {1} label {eg: moregcd-01} )

É claro que 5 e 7 são relativamente primos, assim como 14 e 27. Encontre a combinação linear desses dois pares de números que é igual a 1.

Solução

Por inspeção, ou usando o algoritmo euclidiano estendido, encontramos (3 cdot5-2 cdot7 = 1 ) e (2 cdot14-1 cdot27 = 1 ).

Exercício prático ( PageIndex {1} label {he: moregcd-01} )

Mostre que ( gcd (133,143) = 1 ) encontrando uma combinação linear apropriada.

Exercício prático ( PageIndex {2} label {he: moregcd-02} )

Mostre que 757 e 1215 são relativamente primos encontrando uma combinação linear apropriada.

Exemplo ( PageIndex {2} label {ex: moregcd-02} )

Segue de [(- 1) cdot n + 1 cdot (n + 1) = 1 não-número ] que ( gcd (n, n + 1) = 1 ). Assim, qualquer par de inteiros positivos consecutivos é relativamente primo.

Teorema ( PageIndex {5} ) (Lema de Euclides)

Seja (a, b, c in mathbb {Z} ). Se ( gcd (a, c) = 1 ) e (c mid ab ), então (c mid b ).

Discussão

Vamos escrever o que sabemos e o que queremos mostrar (WTS): [ begin {array} {ll} mbox {Know}: & as + ct = 1 mbox {para alguns inteiros $ s $ e $ t $}, & ab = cx mbox {para algum inteiro $ x $}, mbox {WTS}: & b = cq mbox {para algum inteiro $ q $}. end {array} nonumber ] Para poder mostrar que (b = cq ) para algum inteiro (q ), temos que encontrar algumas informações sobre (b ). Esta informação deve vir das duas equações (as + ct = 1 ) e (ab = cx ). Como (b = b cdot1 ), podemos multiplicar (b ) para ambos os lados de (as + ct = 1 ). Por convenção, não podemos escrever

((como + ct = 1) cdot b ).

Esta notação é inaceitável! O motivo é: não podemos multiplicar uma equação por um número. Em vez disso, temos que multiplicar ambos os lados de uma equação pelo número: [b = 1 cdot b = (as + ct) cdot b = asb + ctb. nonumber ] Obviamente, (ctb ) é um múltiplo de (c ); estamos um passo mais perto de nosso objetivo. Uma vez que (asb = ab cdot s ), e sabemos que (ab ) é de fato um múltiplo de (c ), então a prova pode ser completada. Agora estamos prontos para amarrar as pontas soltas e polir a prova.

Prova

Suponha que ( gcd (a, c) = 1 ) e (c mid ab ). Existem inteiros (s ) e (t ) tais que [as + ct = 1. nonumber ] Isso leva a [b = 1 cdot b = (as + ct) cdot b = asb + ctb. nonumber ] Desde (c mid ab ), existe um inteiro (x ) tal que (ab = cx ). Então [b = ab cdot s + ctb = cx cdot s + ctb = c (xs + tb), nonumber ] onde (xc + tb in mathbb {Z} ). Portanto, (c mid b ).

Corolário ( PageIndex {6} )

Se (a, b in mathbb {Z} ) e (p ) for um primo tal que (p mid ab ), então (p mid a ) ou (p mid b ).

Prova

Se (p mid a ), terminamos com a prova. Se (p nmid a ), então ( gcd (p, a) = 1 ), e o lema de Euclides implica que (p mid b ).

Não podemos aplicar o corolário se (p ) for composto. Por exemplo, (6 mid 4 cdot15 ), mas (6 nmid 4 ) e (6 nmid 15 ). Por outro lado, quando (p mid ab ), onde (p ) é primo, é possível ter tanto (p mid a ) e (p mid b ). Por exemplo, (5 mid 15 cdot 25 ), ainda temos (5 mid 15 ) e (5 mid 25 ).

Corolário ( PageIndex {7} )

Se (a_1, a_2, ldots, a_n in mathbb {Z} ) e (p ) é um primo tal que (p mid a_1 a_2 cdots a_n ), então (p mid a_i ) para algum (i ), onde (1 leq i leq n ). Conseqüentemente, se um primo (p ) divide um produto de (n ) fatores, então (p ) deve dividir pelo menos um desses (n ) fatores.

Prova

Deixamos a prova para você como um exercício.

Exemplo ( PageIndex {3} label {por exemplo: moregcd-03} )

Prove que ( sqrt {2} ) é irracional.

Observação

Provamos anteriormente que ( sqrt {2} ) é irracional em um exercício prático. A solução que apresentamos tem uma pequena falha. Um passo chave nessa prova afirma que [ mbox {O inteiro 2 divide $ m ^ 2 $, portanto 2 divide $ m $}. nonumber ] Esta afirmação é falsa em geral. Por exemplo, 4 divide (6 ^ 2 ), mas 4 não divide 6. Portanto, temos que justificar por que essa afirmação é válida para 2.

Solução

Suponha que ( sqrt {2} ) seja racional, então podemos escrever [ sqrt {2} = frac {m} {n} nonumber ] para alguns inteiros positivos (m ) e (n ) que não compartilham nenhum divisor comum, exceto 1. Quadrado de ambos os lados e multiplicação cruzada dá [2n ^ 2 = m ^ 2. nonumber ] Portanto, 2 divide (m ^ 2 ). Como 2 é primo, o lema de Euclides implica que 2 também deve dividir (m ). Então podemos escrever (m = 2s ) para algum inteiro (s ). A equação acima torna-se [2n ^ 2 = m ^ 2 = (2s) ^ 2 = 4s ^ 2. nonumber ] Portanto, [n ^ 2 = 2s ^ 2, nonumber ], o que implica que 2 se divide (n ^ 2 ). Novamente, uma vez que 2 é primo, o lema de Euclides implica que 2 também divide (n ). Provamos que (m ) e (n ) são divisíveis por 2. Isso contradiz a suposição de que (m ) e (n ) não compartilham nenhum divisor comum. Portanto, ( sqrt {2} ) deve ser irracional.

Exercício prático ( PageIndex {3} label {he: moregcd-03} )

Prove que ( sqrt {7} ) é irracional.

Fechamos esta seção com um resultado verdadeiramente fascinante.

Teorema ( PageIndex {8} )

Para quaisquer inteiros positivos (m ) e (n ), ( gcd (F_m, F_n) = F _ { gcd (m, n)} ).

Corolário ( PageIndex {9} )

Para qualquer número inteiro positivo (n ), (3 mid F_n Leftrightarrow 4 mid n ).

Prova

( ( Rightarrow )) Se (3 mid F_n ), então, porque (F_3 = 4 ), temos [3 = gcd (3, F_n) = gcd (F_4, F_n) = F _ { gcd (4, n)}. nonumber ] Segue-se que ( gcd (4, n) = 4 ), que por sua vez implica que (4 mid n ).

( ( Leftarrow )) Se (4 mid n ), então ( gcd (4, n) = 4 ), e [ gcd (3, F_n) = gcd (F_4, F_n ) = F _ { gcd (4, n)} = F_4 = 3; nonumber ] portanto, (3 mid F_n ).

Resumo e revisão

  • Dados quaisquer dois inteiros diferentes de zero, há apenas uma combinação linear especial que seria igual ao seu maior divisor comum.
  • Todas as outras combinações lineares são apenas múltiplos de seu maior divisor comum.
  • Se (a ) e (c ) são relativamente primos, então o lema de Euclides afirma que se (c ) divide (ab ), então (c ) deve dividir (b ).
  • Em particular, se (p ) é primo, e se (p mid ab ), então (p mid a ) ou (p mid b ).

Exercício ( PageIndex {1} label {ex: moregcd-01} )

Dado qualquer número inteiro positivo arbitrário (n ), prove que (2n + 1 ) e (3n + 2 ) são relativamente primos.

Exercício ( PageIndex {2} label {ex: moregcd-02} )

Use a indução para provar que para qualquer inteiro (n geq2 ), se (a_1, a_2, ldots, a_n in mathbb {Z} ) e (p ) é um primo tal que (p mid a_1 a_2 cdots a_n ), então (p mid a_i ) para algum (i ), onde (1 leq i leq n ).

Exercício ( PageIndex {3} label {ex: moregcd-03} )

Prove que ( sqrt {p} ) é irracional para qualquer número primo (p ).

Exercício ( PageIndex {4} label {ex: moregcd-04} )

Prove que ( sqrt [3] {2} ) é irracional.

Exercício ( PageIndex {5} label {ex: moregcd-05} )

Dados quaisquer números inteiros positivos arbitrários (a ), (b ) e (c ), mostre que se (a mid c ), (b mid c ) e ( gcd (a, b) = 1 ), então (ab mid c ).

Observação. Este resultado é muito importante. Lembre se!

Exercício ( PageIndex {6} label {ex: moregcd-06} )

Dados quaisquer inteiros positivos arbitrários (a ), (b ) e (c ), mostre que se (a mid c ) e (b mid c ), então (ab mid cd ), onde (d = gcd (a, b) ).

Exercício ( PageIndex {7} label {ex: moregcd-07} )

Use a indução para provar que (3 mid (2 ^ {4n} -1) ) e (5 mid (2 ^ {4n} -1) ) para qualquer inteiro (n geq1 ). Use estes resultados para provar que (15 mid (2 ^ {4n} -1) ) para qualquer inteiro (n geq1 ).

Exercício ( PageIndex {8} label {ex: moregcd-08} )

Prove que (2 mid F_n Leftrightarrow 3 mid n ) para qualquer número inteiro positivo (n ).


Assista o vídeo: Qual calibre escolher? ou Parte 1: Teoria e diferenças técnicas (Dezembro 2021).