Teoria de números/Máximo divisor comum: diferenças entre revisões

|Se <math>m|ab\,\!</math> e <math>(a,m)=1\,\!</math> então <math>m|b\,\!</math>.

}}

:<math>1=ax+my\,\!</math>, com <math>x\,\!</math> e <math>y\,\!</math> inteiros.

 

|Se um número primo divide o produto de dois números inteiros, então ele é divisor de um dos dois.

}}

 

Será provado que se <math>p\,\!</math> não divide <math>a\,\!</math>, então deve necessariamente dividir <math>b\,\!</math>.

 

Por causa dela, pode ser suposto que <math>a\ge b\ge 0\,\!</math>, e obter a demonstração:

 

Obviamente, se <math>a+b = 0\,\!</math>, tem-se <math>a=b=0\,\!</math>, e a propriedade é válida pois sempre que <math>b=0\,\!</math> tem-se:

 

Portanto o valor fornecido pelo algoritmo corresponde a <math>(a,b)\,\!</math>, e foi obtido através de exatamente <math>k\,\!</math> divisões.

{{Demonstração/Fim}}

 

Segundo o comentário que precede esta definição, tem-se:

:<math>mmc(a,b) = \frac{ab}{(a,b)}\,\!</math>

 

==== Exemplificando ====

 

Além disso, são utilizados alguns conceitos que certamente são conhecidos por aqueles que possuem conhecimentos básicos de álgebra. Se este não for o seu caso, você poderá pular esta seção, e não haverá prejuizo na leitura do restante deste livro.

Então, <math>J\,\!</math> é um subgrupo aditivo de <math>\mathbb{Z}\,\!</math> (um ideal), ou seja, <math>J\,\!</math> possui as seguintes propriedades:

# <math>0 \in J\,\!</math>;