Introdução
No post 047 vimos o teorema de Euler que afirma que, se
, então temos a equivalência
(
), onde
é a quantidade de inteiros positivos menores que/ e primos com
(função de Euler).
Seja a seguinte equação em
no conjunto universo
:
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,
.
É importante observar que a equação (1) terá soluções se, e somente se,
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:
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 ![This is the rendered form of the equation. You can not edit this directly. Right click will give you the option to save the image, and in most browsers you can drag the image onto your desktop or another program.](http://latex.codecogs.com/gif.latex?m)
Dados
Teorema 1
Seja
Se
, então
de forma que
é múltiplo de
.
Demonstração
Seja
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
Demonstração
Fazendo
e tendo em vista que
, temos
Pelo teorema
,
é múltiplo de
.
Pelo mesmo teorema, de
, temos que
é múltiplo de
.
![This is the rendered form of the equation. You can not edit this directly. Right click will give you the option to save the image, and in most browsers you can drag the image onto your desktop or another program.](http://latex.codecogs.com/gif.latex?s=\frac{t}{d}%20\Rightarrow%20exp_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
Pelo mesmo teorema, 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
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
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:
ResponderExcluirUsando 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?
Oi, Daniel!
ResponderExcluirObrigado 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!