Se
e
são números naturais primos entre si, prove que mdc (
,
.
Passo 1
O enunciado reclama que, para
com
, devemos provar
O conteúdo aqui é teoria de divisibilidade e uso de combinações lineares para o MDC.
Passo 2
Seja
Então
divide qualquer combinação linear dessas duas quantidades. Em particular, como
e
, temos
Logo
Passo 3
Como também
dmid(a+b) , segue
Mas qualquer divisor comum a
a^2 e a
a+b também divide
a . Logo
Portanto
dmid1 , o que implica
d=1 .