ELEMENTOS: 097-Expoente de A Módulo M

Introdução

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

Seja a seguinte equação em $x$ no conjunto universo $U=\mathbb{N}$ :

$a^x \equiv 1$ ( $[;mod;]$ $[;m;]$ ) (1)

No caso $(a,m)=1$ , o teorema de Euler já nos garante a solução $x=\varphi (m)$ , porém, ela não é única.

É importante observar que a equação (1) terá soluções se, e somente se, $(a,m)=1$ . De fato pois, sendo $a_x-1=\pm km$ ou $a^x+lm=1$ , temos que qualquer divisor comum de $a$ e $m$ divide $1$ . Consequentemente, $(a,m)=1$ .

O presente post tem, por intermédio da função expoente de $a$ módulo $m$ , 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 $a$ e $b$ , temos que se $a$ é múltiplo de $b$ e $b$ é múltiplo de $a$ , então $a=b$ .

Definição de expoente de $a$ módulo $m$

Dados $m \in \mathbb{N}$ e $a \in \mathbb{Z}$ , onde $(a,m)=1$ , chama-se expoente de $a$ módulo $m$ ao menor inteiro positivo $t$ tal que $a^t \equiv 1 \ (mod \ m)$ . Simbolicamente,

$t=exp_m(a)$

Teorema 1

Seja $m \in \mathbb{N}$ e $a \in \mathbb{Z}$ , onde $(a,m)=1$ . Considere o conjunto $E$ que contêm todas as soluções de $a^x \equiv 1 \ (mod \ m)$ :

$E=\left \{ x \in \mathbb{N} \ / \ a^x \equiv1 \ (mod \ m) \right \}$

Se $t=exp_m(a)$ , então

$E=\left \{ \alpha t \ / \ \alpha \in \mathbb \left { N \right \}}$

de forma que $x$ é múltiplo de $t$ .

Demonstração

Seja $u \in E$ . Assim, $a^u \equiv1 \ (mod \ m)$ . Pelo algoritmo de Euclides, existem inteiros $q$ e $r$ , tais que $u=qt+r$ , com $0\leq r<t$ . Mas vejam que

$a^u\equiv1 \ (mod \ m) \Rightarrow$

$a^{qt+r}\equiv1 \ (mod \ m) \Rightarrow$

$(a^{t})^{q}a^r\equiv1 \ (mod \ m)$ (i)

e como $t=exp_m(a)$ , por definição , é o menor elemento de $E$ , segue que

$a^t\equiv1 \ (mod \ m)\Rightarrow$

$(a^t)^q\equiv1 \ (mod \ m)$

de forma que, para sustentar a equivalência (i) , é necessário $a^r \equiv 1 \(mod \ m)$ . Portanto, $r \in E$$ . Lembrem-se que $0\leq r<t$ . Mas pelo princípio a) ,o conjunto $E$ tem um elemento mínimo e já sabemos que é $t=exp_m(a)$ . Logo, $r=0$ e $u=qt+r =qt+0=qt$ e está provado que qualquer solução de $a^x \equiv 1 \ (mod \ m)$ é múltiplo de $t=exp_m(a)$ .

Teorema 2

Dados $m,n,s \in \mathbb{N}$ ; $a \in \mathbb{Z}$ , com $(a,m)=1$ ; se $s$ é o menor expoente que verifica $(a^n)^s\equiv1 \ (mod \ m)$ , ou seja, $s=exp_m(a^n)$ , então

$s=exp_m(a^n)=\frac{t}{(n,t)}$ , com

$t=exp_m(a)$

Demonstração

Fazendo $d=(n,t)$ e tendo em vista que $a^t\equiv \ 1 \ (mod \ m)$ , temos

$(a^n)^{t/d}=(a^t)^{n/d}\equiv 1 \ (mod \ m)$

Pelo teorema $1$ , $t/d$ é múltiplo de $s$ .

Pelo mesmo teorema, de $(a^n)^s\equiv1 \ (mod \ m)$ , temos que $ns$ é múltiplo de $t$ .

Assim, para algum $\alpha \in \mathbb{Z}$ :

$ns=\alpha t \Rightarrow$

$\frac{n}{d}s=\frac{t}{d}\alpha$

e fica claro que $\frac{t}{d}$ divide $\frac{n}{d}s$ . Mas, como $d=(n,t)$ segue que $\left(\frac{t}{d},\frac{n}{d} \right )=1$ e, portanto, $\frac{t}{d}$ divide $s$ ou $s$ é múltiplo de $\frac{t}{d}$ . Ora, mas sabemos logo no início da demonstração que $t/d$ é múltiplo de $s$ . Logo, pelo princípio b) , concluimos que

$s=\frac{t}{d} \Rightarrow exp_m(a^n)=\frac{t}{(n,t)}$

Gostará de ler também:

048-Fundamentos de Congruência Modular
046-Critérios de Divisibilidade
055-Cálculo de Resto sem Dividir
047-Teoremas de Euler e Fermat
049-Equação de Congruência Linear
050-Equação de Congruência Polinomial
051-Teorema de Wilson-II

REFERÊNCIA BIBLIOGRÁFICA

2 comentários:

Daniel28 de dezembro de 2012 às 13:28
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
Respostas
Aloisio Teixeira28 de dezembro de 2012 às 16:06
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
Respostas

Adicionar comentário

Páginas

quinta-feira, 13 de dezembro de 2012

097-Expoente de A Módulo M

2 comentários:

V.O