FANDOM


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? Editar

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?Editar

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çãoEditar

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? Editar

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)Editar

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 \geq 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.

Bibliografia Editar