Raízes Primitivas

Sejam $n$ inteiro positivo e $a$ inteiro, com $\operatorname{mdc}(a,n)=1$. Dizemos que $a$ é raiz primitiva módulo $n$ quando

$\operatorname{ord}_n a = \varphi(n).$

Qual a Vantagem de Usarmos Raízes Primitivas?

O número $a$ é raiz primitiva módulo $n$ se, e somente se, para todo inteiro $b$ primo com $n$ podemos tomar um inteiro positivo $x$ tal que

$a^x \equiv b \pmod{n}.$

Ou seja, potências de $a$ podem ter todos os resíduos possíveis módulo $n$.

Como Provar que Alguém é Raiz Primitiva Módulo $n$ Conhecendo Outra Raiz Primitiva?

Considere $a$ uma raiz primitiva módulo $n$, $b$ um número primo com $n$ e $x$ é um inteiro tal que $a^x \equiv b \pmod{m}$. Então $b$ é raiz primitiva módulo $n$ se, e somente se, $\operatorname{mdc}(x,\varphi(n))=1$.

Prova: ($\Rightarrow$) Considere $d=\operatorname{mdc}(x,\varphi(n))$ e suponha, por absurdo, que $d$ é diferente de $1$. Iremos cair em uma contradição: veremos que $b$ não é raiz primitiva módulo $n$. Como fazer isto? Basta encontrarmos algum $k$ tal que $0<k<\varphi(n)$ e $b^k \equiv 1 \pmod{n}$.

Pela definição de máximo divisor comum, existem inteiros $r$ e $s$ tais que $x=dr$ e $\varphi(n)=ds$.

Com isso,

$a^x \equiv b \pmod{n} \Leftrightarrow a^{dr} \equiv b \pmod{n}.$

Façamos $\varphi(n)$ aparecer nas nossas contas. Para isso, elevemos ambos os lados da congruência a $s$ e usarmos o teorema de Euler,

$(a^{ds})^r \equiv b^s \pmod{n} \Leftrightarrow (a^{\varphi(n)})^r \equiv b^s \pmod{n} \Leftrightarrow b^s \equiv 1 \pmod{n}.$

Onde $0<s<\varphi(n)$, pois $d > 1$, o que contradiz a minimalidade de $\varphi(n)$ e assim $b$ não é raiz primitiva. Contradição. Logo, $\operatorname{mdc}(x,\varphi(n))=1$.

($\Leftarrow$) Provaremos que $\operatorname{ord}_n b = \varphi (n)$. Sabemos que $\operatorname{ord}_n b \mid \varphi(n)$. Resta mostrarmos que $\varphi(n) \mid \operatorname{ord}_n b$.

Com efeito, pela definição de ordem

$b^{\operatorname{ord}_n b} \equiv 1 \pmod{n}.$

Desta maneira,

$a^{x\operatorname{ord}_n b} \equiv b^{\operatorname{ord}_n b} \equiv 1 \pmod{n}.$

Com isso, $\varphi(n)=\operatorname{ord}_n a \mid x\operatorname{ord}_n b$. Mas $\operatorname{mdc}(x,\varphi(n))=1$ e pelo lema de Euclides, $\varphi(n) \mid \operatorname{ord}_n b$, de onde segue que $\varphi(n) = \operatorname{ord}_n b$ e assim $b$ é raiz primitiva módulo $n$.

Proposição

Se $m \mid n$ e $a$ é raiz primitiva módulo $n$, então $a$ é raiz primitiva módulo $m$.

Quando um Número possui Raízes Primitivas?

Os únicos números que possuem raízes primitivas são $2,4,p^k$ e $2p^k$, onde $p$ é um primo ímpar e $k$ é um inteiro positivo.

Exemplo (Cone Sul 2000)

Existe um inteiro positivo divisível pelo produto de seus algarismos e tal que esse produto é maior que $10^{2000}$?

Solução: Precisamos apenas exibir algum inteiro com essa propriedade. Uma estratégia interessante é pegar algum inteiro que possui vários algarismos algarismos iguais, pois assim fica fácil fazermos o produto deles.

Mas na hora de reescrevermos os números, precisamos que as potências de $10$ sejam iguais a quaisquer resíduos possíveis algum módulo. Isto equivale a perguntar qual o número tal que $10$ raiz primitiva dele. Além disso, $10$ deve ser equivalente a potências deste número.

De todos os algarismos, o único em que $10$ é raiz primitiva módulo ele é o $7$. Vejamos que é melhor ainda: $10$ é raiz primitiva módulo $7^n$, para todo $n$ inteiro positivo. Usemos indução em $n$ para provar isso.

O caso em que $n=1$ é imediato. Vejamos o caso $n=2$. Queremos mostrar que $\operatorname{ord}_{7^2} 10 = \varphi(7^2) = 7^2-7=42$. Observe que $\operatorname{ord}_{7^2} 10 | 42$. O número $\operatorname{ord}_{7^2} 10$ não pode ser $1,2,3,6,7,14$ e nem $21$. Logo, $\operatorname{ord}_{49} 10 = 42$, de onde segue que $10$ é raiz primitiva módulo $7^2$.

Vamos supor que $10$ é raiz primitiva módulo $7^n$, para $n\ge 2$ e mostrar que $10$ é raiz primitiva módulo $7^{n+1}$.

Considere $a$ uma raiz primitiva módulo $7^{n+1}$. Como $\operatorname{mdc}(7^{n+1},10)=1$, existe $y$ inteiro tal que

$a^y \equiv 10 \pmod{7^{n+1}}.$

Para mostrarmos que $10$ é raiz primitiva módulo $7^{n+1}$, é suficiente mostrarmos que $\operatorname{mdc}(y,\varphi(7^{n+1}))=1$.

Vamos aproveitar analisar módulo $7^n$ já sabemos algo sobre ele. Como $a$ é raiz primitiva módulo $7^{n+1}$ e $7^n \mid 7^{n+1}$, segue que $a$ é raiz primitiva módulo $7^n$. Precisamos combinar isto com o fato de que $10$ é raiz primitiva módulo $7^n$. Observe que, como $\operatorname{mdc}(10,7)=1$, existe $x$ inteiro tal que

$a^x \equiv 10 \pmod{7^n}. (*)$

Como $10$ é raiz primitiva módulo $7^n$, segue que $\operatorname{mdc}(x,\varphi(7^n))=1$.

Já que sabemos que $\operatorname{mdc}(x,\varphi(7^n))=1$ vejamos uma maneira de relacionarmos $x$ e $y$.

Como $7^n|7^{n+1}$ e $a^y \equiv 10 \pmod{7^{n+1}}$, segue que $a^y \equiv 10 \pmod{7^n}$. Mas por $(*)$,

$a^x \equiv a^y \pmod{7^n} \Leftrightarrow x \equiv y \pmod{\operatorname{ord}_{7^n} a}.$

Mas $a$ é raiz primitiva módulo $7^n$, de onde segue que $\operatorname{ord}_{7^n} a = \varphi(7^n)$ e assim

$x \equiv y \pmod{\varphi(7^n)}.$

Mas $x$ e $\varphi(7^n)$ são primos entre si, de onde segue que $y$ e $\varphi(7^n)$ também são. Observe que

$\varphi(7^n)=7^n-7^{n-1}=6.7^{n-1}$

$\varphi(7^{n+1})=7^{n+1}-7^n=6.7^n.$

Em outras sabemos que $\operatorname{mdc}(y,6.7^{n-1})=1$ e $\operatorname{mdc}(y,6.7^n)=d$. Observe que $6 \nmid y$, pois, caso contrário, $6 \mid \operatorname{mdc}(y,6.7^{n-1})=1$. Analogamente $7 \nmid y$. Logo, $\operatorname{mdc}(y,6.7^n)=1$. Assim $10$ é raiz primitiva módulo $7^{n+1}$.

Isto finaliza a prova por indução de que $10$ é raiz primitiva módulo $n$ para todo $n$ natural.

Falta agora encontrar algum $x$ que satisfaças as condições do enunciado. Seria interessante que ele tivesse vários algarismos iguais a $7$. Observe, porém, que o número

$x=\underbrace {77\dots 7} _{a \text{ vezes}}$

não funciona, pois ele não é divisível por $7^a$. E o que podemos colocar no nosso número para consertar isto? Alguns algarismos iguais a $1$, já que eles não alteram o produto.

Tomemos então o número

$x=\underbrace {11\dots 1} _{b-a \text{ vezes}}\underbrace {77\dots 7} _{a \text{ vezes}}=\frac{10^a-1}{9}.7+\frac{10^b-10^a}{9}.$

Como fazemos o produto dos algarismos ser maior que $10^{2000}$? Basta tomarmos $a$ de tal maneira que $7^a>10^{2000}$ (já que o produto dos algarismos de $x$ é $7^a$).

Qual $b$ devemos escolher para $x$ cumprir as condições do enunciado? Observe que

$x \equiv 0 \pmod{7^a} \Leftrightarrow 10^b \equiv 7-6.10^a \pmod{7^a}. (*)$

E existe $b$ que satisfaz $(*)$, pois $10$ é raiz primitiva módulo $7^a$.

Portanto, este valor de $x$ é divisível pelo produto de seus dígitos.

Lugares Para Estudar

• Ordem e Raízes Primitivas (POTI - Nível 3)

Vídeos

• Ordem e Raízes Primitivas (POTI - Nível 3)
• Ordem e Raízes Primitivas: Continuação (POTI - Nível 3)
• Ordem e Raízes Primitivas (POTI - Nível 3)

Bibliografia

• CARLOS GUSTAVO, Moreira. Divisibilidade, Congruências e Aritmética Módulo n. Revista Eureka, Rio de Janeiro, n. 2, p. 41-52, 1998. Disponível em: <https://www.obm.org.br/content/uploads/2017/01/eureka2.pdf>. Acesso em: 06 ago. 2018.