Propriedade Importante

Outra propriedade importante da aritmética modular.

Se a ≡ a’ (mod n ) e b = b’ (mod n) então a.b = a’.b’ (mod n)


Primeiro temos que:

a – a’ = n . k

b – b’ = n.d

Reescrevendo de outra forma teremos:

a = n.k + a’

b = n.d + b’

Efetuando a multiplicação:

a . b = (nk + a’)(nd + b’)

a.b = n²k.d + nkb’ + nda’ + a’.b’

a.b – a’.b’ = n²kd + nkb’ +nda’

a.b – a’.b’ = n(nkd + kb’ + da’) que é condição necessaria para afirmar que n | a.b – a’.b’ e concluirmos que a.b = a’.b’ (mod n).

E resta uma propriedade particular:

a^(k) = a’^(k) (mod n)

Vamos tentar demonstrar isso:
Sendo a – a’ = n.k  –>

a = n.k + a’

Elevando ambos os lados ao quadrado.

a² = (nk + a’)²

a² = (nk)² + 2a’nk + a’²

a² – a’² = n(nk² + 2a’k) Com isso mostramos um caso particular, para quando o expoente é 2.

vamos tentar generalizar:

a = nd + a’

elevando tudo ao expoente k.

a^(k) = (nd + a’)^(k)

Olhamos que o segundo termo é o desenvolvimento do binomio de newton, então:

a^(k) = nd^(k) + a’nd^(k-1) + a’²nd^(k-2) +……….+a’^(k-1)nd + a’^(k)

a^(k) – a’^(k) = nd^(k) + a’nd^(k-1) + a’²nd^(k-2) +……….+a’^(k-1)nd

colocando n em evidencia.

a^(k) – a’^(k) = n(d^(k) + a’d^(k-1)+ ……….+a’^(k-1)d) com isso concluimos que n | a^(k) – a’^(k) então a propriedade particular é válida.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: