Ordem e Lema de Hensel

INTRODUÇÃO

Problemas que envolvem divisibilidade ou restos são muito recorrentes em olimpíadas, principalmente quando se trata de um problema de Teoria dos Números. Geralmente encontramos as variáveis na base dos números, mas ainda sim ocorre bastante de encontrarmos-nas no expoente de números. Em problemas assim geralmente usamos algumas ferramentas matemáticas muito poderosas, dentre elas, lhes apresento: Ordem!

DEFINIÇÃO

Sejam $a$ e $n$ números primos entre si. Definimos $d=\mbox{ord}_na$ como sendo o menor $d$ inteiro positivo tal que $a^d\equiv1\pmod{n}$ .

FATOS ÚTEIS

Teorema 1. Temos que $a^x\equiv1\pmod{n}\iff d\mid x$ , onde $d=\mbox{ord}_na$ .

Demonstração

Existem $q,r\in\mathbb{Z}$ , $x=qd+r$ com $0\leq r<d$ . Assim:

$a^x=a^{qd}a^r\equiv1\pmod{n}\implies 1^qa^r\equiv a^r\equiv1\pmod{n}$

Porém como $r<d$ e $d$ é o menor inteiro positivo que satisfaz $a^d\equiv1\pmod{n}$ então devemos ter $r=0$ e portanto $x=qd\implies d\mid x$ . A volta segue diretamente disso. $\blacksquare$

Teorema 2. Vale que $a^x\equiv a^y\pmod{n}\iff x\equiv y\pmod{d}$ , onde $d=\mbox{ord}_na$

Demonstração

Temos que $a^{x-y}\equiv1\pmod{n}\iff d\mid{x-y}\iff x\equiv y\pmod{d}$ . $\blacksquare$

Teorema 3. $d=\mbox{ord}_na\mid\phi(n)$ , e mais particularmente $d\mid n-1$ se $n$ é primo.

Demonstração

Pelo Teorema de Euler-Fermat temos que $a^{\phi(n)}\equiv1\pmod{n}$ . Assim de $i$ temos que $d\mid\phi(n)$ . O caso particular vem do fato de $\phi(n)=n-1$ quando $n$ é primo. $\blacksquare$

EXERCÍCIOS RESOLVIDOS

Obs: Tentem resolver estes antes de ler as soluções!

$1.$ Mostre que não existe $n>1$ inteiro tal que $n\mid2^n-1$ .

Clique para revelar a solução

Solução: Seja $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ a fatoração em primos de $n$ e $d=\mbox{ord}_{p_1}2$ . Assim, pelo enunciado temos que $2^n\equiv1\pmod{n}\implies2^n\equiv1\pmod{p_1}$ . Assim, $d\mid n$ e de $iii$ temos que $d\mid\phi(p_1)=p_1-1\implies d\mid mdc(n,p_1-1)$ . Porém $p_1-1$ é menor que qualquer fator de $n$ diferente de $1$ $\implies mdc(n,p_1-1)=1\implies d\mid1$ o que é um absurdo pois implica que $2\equiv1\pmod{p_1}\implies p_1\mid1$ , absurdo. $\blacksquare$

Comentários: Note que nesse problema usamos o fato da ordem dividir o expoente pra chegar num absurdo. Essa técnica é muito utilizada em problemas com ordem, já que conseguimos forçar um número a ser divisível por um outro número menor que seus divisores próprios.

$2.$ Mostre que para $n$ e $a>1$ inteiros, $n\mid\phi(a^n-1)$ sempre ocorre.

Clique para revelar a solução

Solução: Note que $mdc(a, a^n-1)=mdc(a^n,a^n-1)=1$ e logo pelo Teorema de Euler-Fermat temos: $a^{\phi(a^n-1)}\equiv1\pmod{a^n-1}$ . Além disso note que $a^n\equiv1\pmod{a^n-1}$ . Perceba que $n=\mbox{ord}_{a^n-1}a$ , pois suponha que exista $0<m<n$ tal que $m=\mbox{ord}_{a^n-1}a$ . Veja que como $0<m<n\implies0<a^m-1<a^n-1$ o que implica que $a^m-1\not\equiv0\pmod{a^n-1}$ . Logo $n=\mbox{ord}_{a^n-1}a$ . Assim de $i$ , $n\mid\phi(a^n-1)$ . $\blacksquare$

Comentários: Nesse problema a ideia foi de forçar os números do enunciado aparecerem em expoentes usando uma congruência "esperta" para podermos usar a ordem ao nosso favor. Essa é outra técnica muito utilizada em problemas que as vezes não nos "gritam" para usarmos ordem mas que se pensarmos um pouco ficam bem mais simples quando usamos.

Hora de treinar! Agora, usando o que aprendeu, resolva o exercício abaixo:

$3.$ Sejam $a$ , $m$ e $n$ inteiros positivos, $mdc(m,n)=d$ e $m'=\dfrac{m}{d}$ e $n'$ definido de forma análoga. Mostre que:

$mdc(a^m+1,a^n+1)=\begin{cases} a^d+1\mbox{ se }m'\mbox{ e }n'\mbox{ impares.} \\ 2\mbox{ se }m'+n'\mbox{ e }a\mbox{ impares.} \\ 1\mbox{ se }m'+n'\mbox{ impar e }a\mbox{ par.}\end{cases}$

$4.$ Ache todos os $n\in\mathbb{Z}^+$ tais que $n^2\mid2^n+1$ . (esse problema talvez exija um pouco mais de seu conhecimento sobre expoentes, mas mesmo assim é um ótimo treino)

REFERÊNCIAS:

Livro "Introdução à Teoria dos Números" do autor José Plínio

Material do Poti: Ordem e Raízes Primitivas