quinta-feira, 13 de dezembro de 2012

097-Expoente de A Módulo M



Introdução
 
No post 047  vimos o teorema de Euler que afirma que, se , então temos a equivalência  [;a^{\varphi(m)} \equiv 1;] ([;mod;] [;m;] ), onde é a quantidade de inteiros positivos menores que/ e primos com (função de Euler).

Seja a seguinte equação em no conjunto universo :

([;mod;] [;m;] ) (1)

No caso , o teorema de Euler já nos garante a solução , porém, ela não é  única.

É importante observar que a equação (1) terá soluções se, e somente se,  . De fato pois, sendo ou , temos que qualquer divisor comum de e divide . Consequentemente, .

O presente post tem, por intermédio da função expoente de módulo , o objetivo de elucidar a característica principal de todas as soluções de (1).

Nas demonstrações dos dois belos teoremas, nos apoiaremos também  nos seguintes princípios:

a) Todo subconjunto não vazio de inteiros não negativos possui um elemento mínimo ( Princípio da boa ordenação );

b) Dados os inteiros não nulos e , temos que se é múltiplo de e é múltiplo de , então .


Definição de expoente de módulo


Dados e , onde , chama-se expoente de módulo ao menor inteiro positivo tal que .   Simbolicamente,

 


Teorema 1

Seja e , onde . Considere o conjunto que contêm todas as soluções de :

  

Se, então 

  de forma que é múltiplo de .



Demonstração

Seja . Assim, . Pelo algoritmo de Euclides, existem inteiros e , tais que , com . Mas vejam que

 
 
(i)
e como , por definição , é o menor elemento de , segue que 

 
de forma que, para sustentar a equivalência  (i) , é necessário . Portanto, .  Lembrem-se que . Mas pelo princípio a) ,o conjunto tem um elemento mínimo e já sabemos que é Logo, e e está provado que qualquer solução de é múltiplo de


Teorema 2

Dados ; , com ; se é o menor expoente que verifica , ou seja, , então

, com

Demonstração

Fazendo e tendo em vista que , temos

 
Pelo teorema , é múltiplo de .

Pelo mesmo teorema, de, temos que é múltiplo de .

Assim, para algum

 
 
 e fica claro que divide . Mas, como segue que e, portanto, divide ou é múltiplo de . Ora, mas sabemos logo no início da demonstração que é múltiplo de . Logo, pelo princípio b) , concluimos que




REFERÊNCIA BIBLIOGRÁFICA


2 comentários:

  1. Olá Aloisio, gostaria de parabenizar pela qualidade do seu blog! Você aborda temas interessantes com clareza... Quanto a este post, particularmente, estive pensando sobre ele e gostaria que você considerasse o seguinte:

    Usando a notação "a -= b(mod c)" para "a congruente b módulo c", "\in" para pertinência, o conjunto E como você definiu no Teorema 1 e N o conjunto dos Naturais.

    P1. Se existe t \in N, tal que t é uma solução particular de a^x -= 1(mod m), então E = N.

    Prova:

    Se t = 1, então, pelo Teorema 1, não há o que ser provado. Vamos assumir t <> 1, assim,

    a -= r(mod m), r \in Z\{1} e a^t -= 1(mod m).

    Seja a^(t-1) -= s(mod m), s \in Z, temos que

    a -= r(mod m)

    a^(t-1) -= s(mod m)

    a * a^(t-1) -= r*s(mod m)

    a^t -= r*s(mod m)

    Desse modo,

    r*s = 1

    Como r e s são números inteiros,logo r = s = 1, mostrando que x = 1 também é solução de a^x -= 1(mod m) e E = N. QED

    Você concorda?

    ResponderExcluir
  2. Oi, Daniel!

    Obrigado pelo demonstração de apreço.

    Sobre sua prova, acho que cometeu um pequeno deslize, mas acredite, é muito comum.

    A propriedade transitiva da aritmética modular diz que se A -=B e B-=C, então A-=C (tudo mod m), mas não necessáriamente A=C.

    Vc fez o seguinte, pelo que entendi:

    Se r*s-=a^t e a^t-=1, então r*s=1 (tudo mod m)

    Mas o correto é apenas concluir que r*s-=1(mod m).

    Valeu, um grande abraço!

    ResponderExcluir