INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA
DE GOIÁS - CÂMPUS GOIÂNIA
DEPARTAMENTO DE ÁREAS ACADÊMICAS 2
Polinômios sobre corpos finitos
Por
Mailine Martins Moraes
ORIENTADORA:
Profa . Ms. Aline Mota de Mesquita Assis
Monografia de Especialização em Matemática
GOIÂNIA, GOIÁS
2014
INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA
DE GOIÁS - CÂMPUS GOIÂNIA
Polinômios sobre corpos finitos
Por
Mailine Martins Moraes
Área de concentração: Álgebra
Orientadora: Profa . Ms. Aline Mota de Mesquita Assis
GOIÂNIA, GOIÁS
2014
A minha famı́lia: Maria Zilmar, Rodimar, Iana e Pablo.
DEDICO
Agradecimentos
A Deus, por ter me dado força para continuar e superar os obstáculos da vida e
chegar até aqui.
À Professora Mestre Aline Mota de Mesquita Assis pela grande atenção, paciência,
dedicação que teve comigo durante as orientações e pela amizade que proporcionou
que nossos momentos juntas fossem tão divertidos e prazerosos. Seu apoio foi fundamental no meu desenvolvimento. Muito obrigada!
À minha famlia, em especial aos meus pais Maria Zilmar e Rodimar que sempre
me apoiaram incondicionalmente, me incentivando a cada dia. À minha irmã, Iana,
pelos momentos de risada, descontração e apoio. Eu os amo muito. Obrigada!
E ao meu namorado, Pablo, por sempre ter estado ao meu lado, ter me incetivado
a continuar, não me deixando desanimar, me deu apoio, amor e carinho em todos
os momentos e por ter sempre me auxiliado mesmo não sendo da mesma área. Eu
te amo muito. Obrigada!
Aos meus amigos, Ana Lúcia, Brunna Brito, Kamila Andrade, Gabriella Barros,
Pedro Rezende, Nara Reges, Igor Maciel que me apoiaram e me ampararam direta
ou indiretamente e a todos os outros que se não citados aqui também estão sendo
lembrados no coração. Muito obrigada!
Aos professores do Corpo Docente da Especialização em especial aqueles com
quem cursei alguma disciplina.
Aos meus colegas que, durante o perı́odo de aula, tanto contribuı́ram para a
minha formação em momentos de estudo e nas conversas divertidas durantes os
lanches da tarde.
A Banca Examinadora pela disponibilidade e atenção dispensada ao meu trabalho.
Resumo
Este trabalho tem por objetivo estudar polinômios sobre corpos finitos, classificá-los
e, de acordo com a ordem, descobrir a quantidade de polinômios mônicos irredutı́veis
em um corpo finito. Sendo ele uma pesquisa bibliográfica, inicia-se relembrando
conceitos básicos de álgebra necessários para seu desenvolvimento, como anéis, polinômios, grupos cı́clicos, entre outros. Inicialmente, é apresentado o conceito de
polinômios com coeficientes em um anel, como esses elementos se comportam e quais
suas propriedades. Depois passa-se para uma estrutura mais completa, o corpo, mais
especificamente, corpo finito. Nessa nova estrutura os polinômios continuam sendo
o foco. Verifica-se a existência de raı́zes desses polinômios, bem como sua ordem,
caracterizando-os em irredutı́veis ou redutı́veis. Por fim, é analisada a possibilidade
de estender um corpo adjuntando novos elementos, a saber as raı́zes de polinômios
irredutı́veis sobre este corpo, para ser possı́vel obter fatores dos polinômios antes
irredutı́veis que passam a ser redutı́ves na extensão do corpo.
Palavras-chave: Extensões de Corpos Finitos, Ordem de Polinômios, Polinômios
Primitivos.
vii
Abstract
This work aims to study polynomials over finite fields, rank them, and, according to
their order, find the amount of monic irreducible polynomials in a finite field. Since
it is a literature review, we begin by recalling basic concepts of algebra necessary for
its development, such as rings, polynomials, cyclic groups, among others. Initially,
we present the concept of polynomials with coefficients in a ring, how these elements
behave and what their properties are. After that, we go to a more complete structure, the field, more specifically, the finite field. In this new structure, polynomials
remain as the focus. We verify the existence of these polynomials’ roots as well
as their order, characterizing them as irreducible or reducible. Finally, we examine
the possibility of extending the field by adding new elements, namely the roots of
irreducible polynomials over this field, in order to make it possible to obtain prior
irreducible factors of polynomials which become reducible in the extension of the
field.
Keywords: Extensions of Finite Fields, Order Polynomials, Primitive Polynomials.
viii
Sumário
Introdução
1
1 Polinômios com Coeficientes em um Anel
3
1.1
Anéis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Anel de Polinômio . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
Classes Residuais de Polinômios . . . . . . . . . . . . . . . . . . . . . 10
2 Corpos Finitos e Extensões de Corpos
12
2.1
Introdução a Corpos Finitos . . . . . . . . . . . . . . . . . . . . . . . 12
2.2
Tipos de Extensões . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Ordem de Polinômios e Polinômios Primitivos
23
Conclusão
35
Referências Bibliográficas
36
i
Introdução
A Teoria dos corpos é um ramo da álgebra abstrata que estuda as propriedades
dos corpos. Um corpo é uma estrutura algébrica em que a adição, a subtração, a
multiplicação e a divisão são bem-definidas.
Os corpos são importantes objetos de estudo na álgebra visto constituı́rem uma
generalização útil de muitos sistemas de números, como os números racionais, os
números reais e os números complexos. Em particular, as regras usuais de associatividade, comutatividade e distributividade valem.
O conceito de corpo foi usado implicitamente por Niels Henrik Abel e Évariste
Galois em seus trabalhos sobre solubilidade de equações.
De acordo com a história, temos:
• 1871: Richard Dedekind deu o nome de corpo a um conjunto de números reais
ou complexos que são fechados para as quatro operações aritméticas.
• 1881: Leopold Kronecker definiu aquilo a que chamou domı́nio de racionalidade e que hoje é geralmente conhecido como corpo de polinômios.
• 1893: Heinrich Weber deu a primeira definição clara de um corpo abstrato.
• 1910: Ernst Steinitz publicou o influente artigo Algebraische Theorie der
Körper (alemão: Teoria Algébrica dos Corpos). Neste artigo ele estuda axiomaticamente as propriedades dos corpos e define conceitos importantes da
teoria dos corpos, como corpo primo, corpo perfeito e o grau de transcendência
de uma extensão de corpo.
1
2
Galois é reconhecido como o primeiro matemático a unificar a teoria dos grupos
e a teoria dos corpos, originando a designação teoria de Galois. No entanto, foi Emil
Artin quem primeiro desenvolveu a relação entre grupos e corpos de forma mais
aprofundada 1928 - 1942.
O presente trabalho aborda, usando conceitos e propriedades da álgebra de anéis
de polinômios e corpos finitos, o estudo de polinômios sobre corpos finitos, classificando e quantificando os polinômios em cada corpo. Sendo este uma revisão
bibliográfica de [4], o trabalho está organizado da seguinte forma. No Capı́tulo 1
é feito uma breve revisão sobre a estrutura de anéis, polinômios e suas principais
propriedades que serão usados ao longo do trabalho. No Capı́tulo 2, apresentamos
uma introdução a corpos finitos, verifica-se a existência de raı́zes de polinômios e a
possibilidade de extender um corpo adjuntando novos elementos. E no Capı́tulo 3
damos inicio ao estudo de polinômios sobre corpos finitos, classificando - os e, de
acordo com a ordem, descobrindo a quantidade de polinômios mônicos irredutı́veis
em um corpo finito.
Capı́tulo 1
Polinômios com Coeficientes em
um Anel
1.1
Anéis
Em matemática, um anel é uma estrutura algébrica que consiste num conjunto munido de duas operações binárias (normalmente chamadas adição e multiplicação,
como veremos a seguir), onde cada operação combina dois elementos para formar
um terceiro. Neste capı́tulo, apresentaremos, em especial, os anéis de polinômios,
cujos elementos são polinômios na forma usual com coeficientes no anel dado. Apresentaremos também as propriedades e operações de tais elementos, formando assim
resultados que serão utilizados ao longo do trabalho.
Definição 1.1. Um conjunto não vazio A é dito um anel se em A estão definidas
duas operações, indicadas por + (chamada adição) e · (chamada multiplicação),
denotado por (A, +, ·), tais que para todo a, b, c ∈ A tem-se:
i) a + b ∈ A (A é fechado para a adição)
ii) a + b = b + a (Comutatividade da adição)
iii) (a + b) + c = a + (b + c) (Associatividade da adição)
iv) Existe 0 ∈ A tal que a + 0 = a, para todo a ∈ A (Elemento neutro da adição)
3
4
v) Existe −a ∈ A tal que a + (−a) = 0 (Elemento inverso da adição)
vi) a · b ∈ A (A é fechado para a multiplicação)
vii) a · (b · c) = (a · b) · c (Associatividade da multiplicação)
viii) a · (b + c) = a · b + a · c e (b + c) · a = b · a + c · a (Leis distributivas)
Da definição temos que A é um grupo abeliano com relação a adição (itens i
ao v) e é um conjunto fechado com relação à multiplicação (itens vi e vii). Se em
relação à multiplicação de A temos que a · b = b · a, para todo a, b ∈ A, então A é
um anel comutativo e se existe 1 ∈ A tal que a · 1 = 1 · a = a, para todo a ∈ A,
então A é um anel com elemento unidade.
Observação 1.2. No que segue denotaremos a · b por ab, com a e b elementos de
um anel.
Exemplo 1.3. A = Z é um anel comutativo com elemento unidade, com as operações
usuais de adição e multiplicação dos inteiros, pois para todo a, b ∈ Z temos ab = ba
e o número 1, sendo o elemento neutro da multiplicação, é o elemento unidade de
Z.
Exemplo 1.4. A = {x; x = 2a, ∀a ∈ Z} é um anel comutativo mas não unitário,
pois para todo x, y ∈ A, x = 2a e y = 2b com a, b ∈ Z, temos que
xy = (2a)(2b) = (2a)(b2) = 2(ab)2 = 2(ba)2 = (2b)(2a) = yx,
uma vez que o anel dos inteiros é comutativo.
Definição 1.5. Se A é um anel comutativo, então a ∈ A, com a 6= 0, é dito um
divisor de zero se existe b ∈ A, tal que ab = 0.
Exemplo 1.6. O anel comutativo Z6 = 0, 1, 2, 3, 4, 5 tem o divisor de zero a = 2,
pois para b = 3 ∈ Z temos ab = 6 = 0 em Z6 .
Definição 1.7. Um anel comutativo é um domı́nio de integridade se não possui
divisores de zero.
5
Exemplo 1.8. O anel dos inteiros Z é um domı́nio de integridade, pois é comutativo
e não existem a, b ∈ Z∗ tal que ab = 0.
Definição 1.9. Um anel A tal que A∗ é um grupo multiplicativo é dito anel de
divisão.
Exemplo 1.10. O anel dos racionais Q é um anel de divisão, pois todo número
racional não nulo possui o inverso em relação à multiplicação. Deste modo, Q∗ é um
grupo multiplicativo.
Definição 1.11. Seja (A, +, ·) um anel de divisão comutativo, dizemos que este anel
é um corpo se, (A, +) e (A∗ , ·) são grupos abelianos. Denotaremos por K um corpo.
Exemplo 1.12. São exemplos de corpos:
i) R, o corpo dos reais com as operações usuais de adição e multiplicação.
ii) Q = { ab ; a, b ∈ Z, b 6= 0} é o corpo dos racionais com as operações usuais de
adição e multiplicação.
Definição 1.13. Seja (A, +, ·) um anel e I um subconjunto não vazio de A. Dizemos
que I é um ideal de A se:
i) x + y ∈ I, para todo x, y ∈ I
ii) ax ∈ I, para todo x ∈ I e para todo a ∈ A.
Se além do item (ii) da Definição 1.13, também for satisfeito xa ∈ I, para todo
x ∈ I e para todo a ∈ A, dizemos que I é um ideal bilateral.
Exemplo 1.14. Seja n ≥ 0 um inteiro. Então o subconjunto
nZ = {nz; z ∈ Z}
é um ideal do anel dos inteiros Z, pois para quaisquer na, nb ∈ nZ e x ∈ Z temos,
na + nb = n(a + b) ∈ nZ
e
(na)x = n(ax) ∈ nZ.
Dizemos que nZ é o ideal principal gerado por n.
6
1.2
Anel de Polinômio
Sabe-se que um monômio em uma variável é da forma axn , com a ∈ A e n ∈ Z+ ,
sendo x a variável e A um anel. É através deste que é definido, a seguir, polinômio
sobre uma variável e logo depois anel de polinômios.
Definição 1.15. Um polinômio em uma variável x é uma série finita de monômios
em uma variável da forma
p(x) = an xn + · · · + a1 x + a0 ,
onde ai ∈ A, sendo A um anel.
Exemplo 1.16. Exemplos de polinômios em uma variável sobre o anel dos inteiros:
1) p(x) = 3x4 + x5 + x2 + x + 1
2) p(y) = 7y 3 + 2y 2 + 4y + 5.
Sejam A um anel e x uma variável. Um polinômio p(x) com coeficientes em A
na variável x é uma expressão do tipo
p(x) =
n
X
ai x i = a0 + a1 x + · · · + an x n ,
i=0
onde n é um inteiro não negativo e os ai são elementos de A.
O conjunto de todos os polinômios na variável x com coeficientes em A será
denotado por A[x]. Note que A ⊂ A[x].
n
m
P
P
Se p(x) =
ai xi , q(x) =
bj xj ∈ A[x], definem-se as operações de adição e
i=0
j=0
multiplicação em A[x], como se segue:
max{n,m}
p(x) + q(x) =
X
(ai + bi )xi ,
i=0
p(x) · q(x) =
n+m
X
i=0
ci x i ,
7
onde
c 0 = a0 b 0 ,
c 1 = a0 b 1 + a1 b 0 ,
..
.
i
X
ci =
aj bi−j = a0 bi + a1 bi−1 + · · · + ai b0 ,
j=0
..
.
cn+m = an bm .
O polinômio p(x) + q(x) é chamado de soma de p(x) e q(x), enquanto que o
polinômio p(x) · q(x), também denotado por p(x)q(x), é o seu produto. Note que
essas operações, quando restritas a A, coincidem com a adição e multiplicação em
A. Então, é fácil ver que, com essas operações assim definidas, A[x] é um anel,
chamado anel de polinômios.
Definição 1.17. Seja A um anel e f (x) = an xn + · · · + a1 x + a0 ∈ A[x] com an 6= 0.
O inteiro n se chama o grau de f (x) e denotaremos por gr(f (x)). O coeficiente
an se chama o coeficiente lı́der de f (x). Quando o coeficiente lı́der for igual a 1, o
polinômio é dito mônico.
Exemplo 1.18. p(x) = x3 + 2x2 + x + 1 é um polinômio mônico de grau 3 em Z[x].
Proposição 1.19. (Algoritmo da Divisão) Considere dois polinômios f (x), g(x) ∈
A[x], com g(x) 6= 0. Então existem dois únicos polinômios t(x), r(x) ∈ A[x] tais que
f (x) = t(x)g(x) + r(x),
onde r(x) = 0 ou gr(r(x)) < gr(g(x)).
Demonstração: Ver página 20 de [4].
Exemplo 1.20. Considere f (x) = 2x5 + x4 + 4x + 3 ∈ Z5 [x], g(x) = 3x2 + 1 ∈ Z5 [x].
Vamos calcular os polinômios q, r ∈ Z5 [x] usando a divisão usual de polinômios, de
8
modo que f = qg + r. Assim, divindo f por g encontramos q(x) = 4x3 + 2x2 + 2x + 1
e r(x) = 2x + 2, e obviamente gr(r(x)) < gr(g(x)).
Definição 1.21. Um polinômio p(x) ∈ K[x] é dito irredutı́vel sobre K (ou irredutı́vel
em K[x]) se p tem grau positivo e
p(x) = b(x)c(x)
com b, c ∈ K[x], implica que b ou c é um polinômio constante.
Observação 1.22. Para que um polinômio (de grau > 1) seja irredutı́vel sobre um
corpo K não é suficiente mas é necessário que ele não admita raı́zes em K. Em
linguagem simbólica:
irredutibilidade sobre K ⇒ não existência de raı́zes em K.
A recı́proca não é verdadeira. Considere dois polinômios quadráticos f (x), g(x) ∈
R[x] sem raı́zes em R, onde
f (x) = x2 + 2 e g(x) = x2 + 1.
Então,
h(x) = f (x)g(x) = (x2 + 2)(x2 + 1) = x4 + 3x2 + 2
não admite raı́zes reais e, no entanto, é redutı́vel. A não equivalência da implicação
acima não a desfavorece teoricamente. É importante também ressaltar que para
polinômios de grau 2 e 3 a implicação acima torna-se uma equivalência, ou seja,
irredutibilidade sobre K ⇔ não existência de raı́zes em K.
Exemplo 1.23. O polinômio p(x) = x2 + x + 1 é irredutı́vel em Z2 [x], pois não
possui raı́zes em Z2 [x]. Com feito, p(0) = p(1) = 0.
Teorema 1.24. (Teorema da Fatoração Única Para polinômios) Todo polinômio
mônico em K[x], não constante e não irredutı́vel, se escreve como produto de polinômios de K[x] irredutı́veis e mônicos. Essa escrita é única a menos da ordem dos
fatores.
9
Demonstração: Ver página 42 de [2].
Corolário 1.25. Para todo polinômio f (x) ∈ K[x]\K existem n ≥ 1 polinômios
mônicos irredutı́veis distintos p1 (x), . . . , pn (x), inteiros positivos α1 , . . . , αn e a ∈ K∗
tais que
f (x) = p1 (x)α1 · · · pn (x)αn .
Essa escrita é única a menos da ordem dos fatores.
Definição 1.26. Dois ou mais polinômios são relativamente primos se, quando
fatorados, não possuem nenhum fator em comum.
Exemplo 1.27. Os polinômios
p(x) = 3x2 + 21x + 18
e
q(x) = 5x + 10
pertencentes a R[x], podem ser fatorados como
p(x) = 3(x + 1)(x + 6)
e
q(x) = 5(x + 2),
assim p(x) e q(x) são relativamente primos, pois não possuem nenhum fator em
comum quando fatorados. Já os polinômios
f (x) = x2 − x − 2 e h(x) = 7x + 14
pertencentes a R[x], podem ser fatorados como
f (x) = (x + 1)(x − 2)
e
h(x) = 7(x + 1),
assim f (x) e h(x) não são relativamente primos, pois possuem o fator (x + 1) em
comum quando são fatorados.
Proposição 1.28. Sejam A um anel, f (x) ∈ A[x] e α ∈ A. Então f (α) = 0, se e
somente se, existe um polinômio t(x) ∈ A[x] tal que f (x) = (x − α)t(x).
Demonstração: Pela Proposição 1.19, sabemos que existem t(x), r(x) ∈ A[x] tais
que f (x) = (x − α)t(x) + r(x) com grr(x) < gr(x − α) = 1 ou r(x) = 0, isto é, com
r(x) uma constante. Então f (α) = (α − α)t(α) + r(α) = r(α) = r(x). Portanto
f (α) = 0 se e somente se r(x) = 0 se e somente se f (x) = (x − α)t(x).
10
Definição 1.29. Sejam A um anel, f (x) ∈ A[x], α ∈ A, e um inteiro s ≥ 1. Dizemos
que α é uma raiz de f (x) de multiplicidade s se (x − α)s divide f (x) mas (x − α)s+1
não divide f (x). Quando s = 1 dizemos que α é uma raiz simples de f (x).
Exemplo 1.30. Seja p(x) = x2 + 2x + 1 ∈ R[x]. Temos que α = −1 é raı́z de
multiplicidade s = 2 de p(x), pois (x − (−1))2 = (x + 1)2 divide p(x), mas (x + 1)3
não divide p(x).
1.3
Classes Residuais de Polinômios
Definição 1.31. Definimos a classe residual de um polinômio mônico p(x) de grau
n em K[x] por:
Kp(x) [x] = {r(x) : r(x) ∈ K[x], com r(x) = 0 ou gr(r(x)) < n}.
Teorema 1.32. O anel Kp(x) [x] é um corpo se, e somente se, o polinômio p(x) é
irredutı́vel.
Demonstração: Ver página 9 de [6].
Seja dado K = Zp , onde p é um número primo positivo. Se p(x) ∈ K[x] é um
polinômio irredutı́vel de grau n, então como Kp(x) [x] é formado pelas classes de
i−1
P
polinômios
ai xi ∈ K[x] e dois polinômios de graus menores do que n dão origem
i=0
a classes distintas, temos que o corpo Kp(x) [x] tem pn elementos.
Exemplo 1.33. Se K = Z2 , então p(x) = x3 + x + 1 é um polinômio irredutı́vel em
K[x]. Logo, podemos construir um corpo com 8 elementos, a saber:
Kp(x) [x] = {0, 1, x, x2 , 1 + x, 1 + x2 , x + x2 , 1 + x + x2 }.
Nesse caso, temos que
0 = x3 + x + 1 = x3 + x + 1.
Assim, x3 = x + 1. As tabelas de operações deste corpo são dadas por:
11
Tabela 1.1: Tabela da adição
+
0
1
x
x2
1+x
1 + x2
x + x2
1 + x + x2
0
0
1
x
x2
1+x
1 + x2
x + x2
1 + x + x2
1
1
0
1+x
1 + x2
x
x2
1 + x + x2
x + x2
x2
1 + x2
x
1+x
x
x
1+x
0
x2
x2
1 + x2
x + x2
1+x
1+x
x
1 + x2
1 + x2
x2
x2
x2
x+
1+x+
x2
x+
1+x+
x+
1
1+x+
1 + x + x2
0
1
1+x+
x2
x+
x2
1+x+
x2
0
x2
1
x+
x2
1+
x2
x2
1 + x + x2
1
x + x2
0
1+x
x
x2
x
1 + x2
1+x
0
1
1+x
x2
x
1
0
x2
x2
1+
x2
Tabela 1.2: Tabela da multiplicação
•
0
1
x
x2
1+x
1 + x2
x + x2
1 + x + x2
0
0
0
0
0
0
0
0
0
1
0
1
x
x2
1+x
1 + x2
x + x2
1 + x + x2
x
0
x
x2
1+x
x + x2
1
1 + x + x2
1 + x2
x2
0
x2
1+x
x + x2
1 + x + x2
x
1 + x2
1
1
x
2
1+x+x
2
1+x
2
x
2
1+x
0
1+x
x+x
1 + x2
0
1 + x2
1
x
x2
1 + x + x2
1+x
x + x2
x + x2
0
x + x2
1 + x + x2
1 + x2
1
1+x
x
x2
1 + x + x2
0
1 + x + x2
1 + x2
1
x
x + x2
x2
1+x
Capı́tulo 2
Corpos Finitos e Extensões de
Corpos
Um corpo é uma estrutura algébrica em que a adição, a subtração, a multiplicação e a divisão são bem definidas. Neste capı́tulo apresentaremos os corpos
finitos, que são corpos cujo conjunto dos seus elementos é finito; e também corpo
de decomposição de um polinômio, que é uma extensão do corpo que contém os
coeficientes do polinômio e é onde este polinômio se decompõe, ou seja, é fatorado.
2.1
Introdução a Corpos Finitos
Lembremos que um anel A é um corpo se (A, ∗) e (A, +) são grupos abelianos.
Definição 2.1. Um corpo K é dito de caracterı́stica 0 se pa 6= 0, onde a ∈ K∗ e
p ∈ Z∗+ . E K tem caracterı́stica finita p ∈ Z∗+ se pa = 0, ∀a ∈ K, onde p é o menor
inteiro tal que isso acontece.
Exemplo 2.2. Q é um corpo de caracterı́stica 0, pois não existe um elemento a ∈ Q∗
e algum p ∈ Z∗+ tal que pa = 0.
Exemplo 2.3. Zp é um corpo finito com caracterı́stica p, onde
Zp = {0, 1, 2, 3, . . . , p − 1} .
12
13
Tome a = 1 ∈ Zp , então pa = p1 = 0.
Teorema 2.4. Seja A um anel comutativo com caracterı́stica prima p. Então:
n
n
(a ± b)p = ap ± bp
n
para todo a, b ∈ A e n ∈ N.
Demonstração: Ver página 16 de [4].
Proposição 2.5. Todo corpo finito tem caracterı́stica p, para algum p primo.
Demonstração: Seja m 6= 0 a caracterı́stica de um corpo finito e 1 a unidade
desse corpo. Suponha que m = pq, com p e q inteiros, onde 1 < p ≤ q < m. Então
m1 = 0, desenvolvendo o produto temos
m1 = p1 · q1 = 0,
assim p1 = 0 ou q1 = 0, o que é um absurdo, pois m é o menor valor tal que isso
acontece. Então m não pode ser fatorado, ou seja, m é um número primo.
Lema 2.6. Seja K um corpo finito qualquer. Para cada número natural n, existe
pelo menos um polinômio irredutı́vel de grau n em K[x].
Demonstração: A demonstração deste Lema é feita por indução sobre n, e pode
ser encontrada em [2] página 70.
Proposição 2.7. Para cada primo p e um inteiro positivo n, existe um corpo de
ordem pn .
Demonstração: Para todo primo positivo p e todo inteiro positivo n, existe,
pelo Lema 2.6, um polinômio irredutı́vel f (x) ∈ Zp [x] de grau n; logo, o corpo
K = Zp [x]f (x) é um dos corpos procurados, pois tem pn elementos.
Proposição 2.8. Dois corpos finitos de mesma ordem são isomorfos.
Demonstração: Ver página 72 de [2].
14
Definição 2.9. Fq [x] é um corpo finito de polinômios em uma variável, onde q = pn ,
p é um número primo, e denotamos por:
Fq [x] = {αn xn + αn−1 xn−1 + · · · + α1 x + α0 / αi ∈ Fq , 0 ≤ i ≤ n}.
Exemplo 2.10. O corpo finito construı́do em 1.33 é o corpo F8 [x].
Teorema 2.11. Para cada corpo finito Fq o grupo multiplicativo F∗q de elementos
não nulos de Fq é cı́clico.
Demonstração: Ver página 42 de [4].
Observação 2.12. Se um corpo é cı́clico então ele é gerado por algum elemento,
denotaremos por F∗q = hαi o corpo cı́clico gerado por α.
Definição 2.13. Seja K um corpo, F ⊆ K é um subcorpo de K quando F é um
subconjunto não vazio de K, tal que, (F, +) é um subgrupo de (K, +) e (F∗ , ·) é um
subgrupo de (K∗ , ·).
Definição 2.14. Um corpo K é chamado uma extensão de F se F é um subcorpo de
K. E se um polinômio f (x) ∈ F[x] pode ser fatorado em produtos de fatores lineares
em K, ou seja, se f (x) tem todas as raı́zes em K, então dizemos que K é um corpo
de decomposição de f (x) sobre F.
Seja K uma extensão de F e seja S um subconjunto de K. Denonte por K(S) o
menor subcorpo de K que contém F e S. Esta é, evidentemente, a intersecção de
todos os subcorpos de K que contém F e S. O corpo F(S) é uma extensão de F e
dizemos que ele é obtido pela adjunção de S a F.
Sejam S e T subconjuntos de K. Então:
F(S ∪ T ) = F(S)(T ) = F(T )(S).
Se S é um cojunto finito, digamos S = {a1 , . . . , an }, denotaremos F(S) por F(a1 , . . . , an ).
Se K é uma extensão de F, então ele é um espaço vetorial sobre F. Este tem uma
dimensão sobre F, que pode ser infinita. Tal dimensão é chamada grau de K sobre
F e denotada por [K : F].
15
Teorema 2.15. Se L é uma extensão de F e K é uma extensão de L, então
[K : F] = [L : F][K : L].
Demonstração: Sejam a1 , . . . , am elementos de K linearmente independentes sobre L e sejam b1 , . . . , bn elementos de L linearmente independentes sobre F. Devemos
mostrar que os mn produtos ai bj , i = 1, . . . , m, j = 1, . . . , n são linearmente independentes sobre F. Suponha que
m X
n
X
cij ai bj = 0,
i=1 j=1
onde cada cij ∈ F. Então
m
n
X
X
i=1
!
cij bj
ai = 0
j=1
e assim para cada i,
n
X
cij bj ∈ L,
j=1
logo,
n
X
cij bj = 0,
i = 1, . . . , m.
j=1
Portanto, cij = 0 para cada i e cada j. Foi provado que a fórmula do Teorema vale
sempre que [K : L] e [L : F] são infinitos. Suponha que ambos são finitos e que
m = [K : L] e n = [L : F]. Então {a1 , . . . , am } é a base de K sobre L e {b1 , . . . , bn }
é a base de L sobre F. Seja d ∈ K. Então
d=
m
X
µ i ai ,
i=1
onde cada µi ∈ L e para i = 1, . . . , m,
ei =
n
X
ξij bj ,
j=1
onde cada ξij ∈ F. Portanto,
d=
m X
n
X
i=1 j=1
ξij ai bj ,
16
e assim os mn produtos de ai bi geram K como um espaço vetorial sobre F. Uma vez
que já foi mostrado que eles são linearmente independentes sobre F, eles formam
uma base de K sobre F.
Lema 2.16. Seja f (x) ∈ Fq [x] um polinômio irredutı́vel sobre o corpo finito Fq e seja
α uma raiz de f na extensão do corpo Fq . Então para um polinômio h(x) ∈ Fq [x],
temos h(α) = 0, se e somente se, f divide h.
Demonstração: Ver página 47 de [4].
Lema 2.17. Seja f (x) ∈ Fq [x] um polinômio irredutı́vel sobre Fq de grau m. Então
n
f (x) divide xq − x, se e somente se, m divide n.
n
Demonstração: Suponha que f (x) divide xq − x. Seja α uma raiz de f no corpo
n
de decomposição de f sobre Fq . Então αq = α, de modo que α ∈ Fqn . Segue-se que
Fq (α) é um subcorpo de Fqn . Mas, uma vez que [Fq (α) : Fq ] = m e [Fqn : Fq ] = n,
pelo Teorema 2.15 temos que m divide n. Reciprocamente, se m divide n, então Fqn
contém Fqm como um subcorpo. Se α é uma raı́z de f no corpo de decomposição de
f sobre Fq , então [Fq (α) : Fq ] = m, de modo que Fq (α) = Fqm . Consequentemente,
n
n
temos α ∈ Fqn , por isso αq = α, e assim α é uma raiz de xq −x ∈ Fq (x). Deduzimos
n
do Lema 2.16 que f (x) divide xq − x.
Teorema 2.18. Se K é um corpo finito com p elementos, então qualquer a ∈ K
satisfaz ap = a.
Demonstração: A identidade ap = a é trivial para a = 0. Por outro lado,
elementos não nulos de K formam um grupo em relação à multiplicação, de ordem
p − 1. Assim ap−1 = 1, para todo a ∈ K com a 6= 0, e multiplicando por a ambos os
lados da igualdade obtém-se ap = a.
Teorema 2.19. Se f (x) é um polinômio irredutı́vel em Fq [x] de grau m, então f
tem uma raiz α em Fqm . Além disso, todas as raı́zes de f são simples e são dadas
2
por m elementos distintos α, αq , αq , . . . , αq
m−1
de Fqm .
17
Demonstração: Seja α uma raiz de f em Fq (α), o corpo de decomposição de f
sobre Fq . Então [Fq (α) : Fq ] = m, assim Fq (α) = Fqm , e em particular α ∈ Fqm . A
seguir mostramos que se β ∈ Fqm é uma raiz de f , então β q é também uma raiz de
f . Escreva f (x) = am xm + · · · + a1 x + a0 com ai ∈ Fq para 0 ≤ i ≤ m. Então,
usando Teorema 2.18 e Teorema 2.4 temos:
f (β q ) = am β qm + · · · + a1 β q + a0
= aqm β qm + · · · + aq1 β q + aq0
= (am β m + · · · + a1 β + a0 )q
= f (β)q
= 0.
2
Deste modo, os elementos α, αq , αq , . . . , αq
m−1
são raı́zes de f . Resta provar que
j
k
esses elementos são distintos. Suponha, por contradição, que αq = αq para alguns
inteiros j e k com 0 ≤ j < k ≤ m − 1. Elevando esta identidade a potência q m−k ,
temos:
αq
m−k+j
m
= αq = α.
Segue então, a partir do Lema 2.16, que f (x) divide xq
m−k+j
− x. Pelo Lema 2.17
isso só é possı́vel se m divide m − k + j. Mas temos 0 < m − k + j < m, o que resulta
2
em uma contradição. Portanto, as raı́zes α, αq , αq , . . . , αq
m−1
são distintas.
Corolário 2.20. Seja f (x) um polinômio irredutı́vel em Fq [x] com grau m. Então
o corpo de decomposição de f sobre Fq é dado por Fqm .
Demonstração: Pelo Teorema 2.19 temos que f decompõe-se em Fqm . Além
2
disso, Fq (α, αq , αq , . . . , αq
m−1
) = Fq (α) = Fqm para uma raiz α de f em Fqm , onde
a segunda identidade é feita a partir do Teorema 2.19.
Definição 2.21. Seja Fqm uma extensão de Fq e seja α ∈ Fqm . Então os elementos
2
α, αq , αq , . . . , αq
m−1
são chamados os conjugados de α com relação a Fq .
18
Teorema 2.22. Os conjugados de α ∈ F∗q com relação a qualquer subcorpo de Fq
tem a mesma ordem no grupo F∗q .
Demonstração: Primeiramente notemos que: em um grupo cı́clico finito hai de
ordem m, o elemento ak gera um subgrupo de ordem m/mdc(k, m). De fato, seja
d = mdc(k, m). A ordem de ak é o menor inteiro positivo n tal que akn = e,
sendo e o elemento neutro do grupo. A última identidade é válida, se e somente
se, m divide kn, ou equivalentemente, se e somente se, m/d divide n. Então o
menor inteiro positivo n com essa propriedade é n = m/d. Visto que pelo Teorema
2.11, F∗q é um grupo cı́clico , pela afirmação acima e o fato de que toda potência
da caracterı́stica de Fq é relativamente prima com a ordem q − 1 de F∗q , temos que
α, αq , . . . , αq
m −1
tem ordem q − 1.
Definição 2.23. Sejam K uma extensão de F e a ∈ K. Dizemos que a é algébrico
sobre F se existe um polinômio não-nulo f (x) ∈ F[x] talque, f (a) = 0.
Definição 2.24. Se θ ∈ K é algébrico sobre F, então o polinômio mônico unicamente
determinado g(x) ∈ K[x] que gera o ideal J = {f ∈ K[x]; f (θ) = 0} de K[x] é
chamado de polinômio minimal ou polinômio irredutı́vel de θ sobre K. Pelo grau de
θ sobre K temos o grau de g(x).
Definição 2.25. O gerador do grupo cı́clico F∗q é chamado elemento primitivo de
Fq .
Definição 2.26. Para α ∈ F = Fqm e K = Fq , a norma, NF/K (α), e o traço,
T rF/K (α), de α sobre K são definidos, respectivamente, por:
i) NF/K (α) = ααq · · · αq
m−1
= α(q
ii) T rF/K (α) = α + αq + · · · + αq
m −1)/(q−1)
m−1
;
.
Definição 2.27. Sejam K corpo finito e F uma extensão finita de K. Então as
duas bases {α1 , . . . , αm } e {β1 , . . . , βm } de F sobre K são ditas bases duais (ou
19
complementares) se para 1 ≤ i, j ≤ m, temos

 0, se i 6= j
T rF/K (αi βj ) =
 1, se i = j
2.2
Tipos de Extensões
Definição 2.28. Uma extensão K de F é chamada extensão finita de F se [K : F] é
finito.
Se K é uma extensão finita de F e se {a1 , . . . , an } é uma base de K sobre F, então
todo elemento de K pode ser escrito na forma
n
X
b i ai ,
b1 , . . . , bn ∈ F.
i=1
Uma vez que essa soma está em F(a1 , . . . , an ) temos K = F(a1 , . . . , an ).
Definição 2.29. Uma extensão K de F é chamada uma extensão simples de F se
K = F(a) para algum a ∈ K.
Definição 2.30. Uma extensão K de F é chamada extensão algébrica de F se cada
elemento de K é algébrico sobre F.
Teorema 2.31. Se K é uma extensão finita de F então K é uma extensão algébrica
de F.
Demonstração: Seja [K : F] = n. Se a ∈ K então os n+1 elementos 1, a, a2 , . . . , an
de K são linearmente independentes sobre F. Portanto há elementos c0 , c1 , . . . , cn ∈
F tal que c0 + c1 a + · · · + cn an = 0 e pelo menos um dos ci é não-nulo. Então
f (x) = c0 + c1 x + · · · + cn xn é um polinômio não-nulo em F[x] tal que f (a) = 0.
Teorema 2.32. Seja K uma extensão de F e seja a ∈ K algébrico sobre F. Então
existe um único polinômio mônico irredutı́vel p(x) ∈ F tal que p(a) = 0. Se g(x)
é um polinômio qualquer em F[x] tal que g(a) = 0, então p(x) divide g(x). Além
disso, F(a) = F[a] e, de fato, todo elemento de F(a) pode ser escrito unicamente na
forma r(a) onde r(x) ∈ F[x] e r(x) = 0 ou gr(r(x)) < gr(p(x)).
20
Demonstração: Defina a apliação ψ de K[x] em K[a] por ψ(f (x)) = f (a). É fácil
ver que ψ é um homomorfismo de K[x] em K[a]. Como a é algébrico sobre K, o
núcleo de ψ é um ideal não nulo de K[x]. Todo ideal de K[x] é um ideal principal,
portanto o núcleo de ψ é gerado por p(x), onde podemos supor que p(x) é mônico.
Como K[x]/ hp(x)i é isomorfo a K[a], então ele é um domı́nio de integridade. Por isso
hp(x)i é um ideal primo, o que implica que p(x) é irredutı́vel em K[x]; na verdade,
p(x) é o único polinômio mônico irredutı́vel no ideal hp(x)i. Uma vez que cada
ideal primo diferente de zero de K[x] é maximal, K[x]/ hp(x)i é um corpo e o mesmo
é verdadeiro para K[a]. Assim, K(a) = K[a]. Para completar a prova, basta ver
que todas as classes de resı́duos h(x) + hp(x)i de (p(x)) em K[x] contém um único
representante r(x) onde r(x) = 0 ou gr(r(x)) < gr(p(x)).
Corolário 2.33. Seja K uma extensão de F e seja a ∈ K. Se a é algébrico sobre F
então F(a)/F é finita e consequentemente algébrica.
Demonstração: Seja n o grau do polinômio irredutı́vel sobre F que tem a como
raı́z. Então pelo Teorema 2.32, 1, a, a2 , . . . , an−1 formam uma base finita de F(a)
sobre F. Portanto, F(a)/F é finita e pelo Teorema 2.31, é também algébrica.
Corolário 2.34. Seja K uma extensão de F e suponha que a1 , . . . , an ∈ K são
algébricos sobre F. Então F(a1 , . . . , an )/F é finita e consequentemente algébrica.
Demonstração: Por indução sobre n. Pelo Corolário 2.33 o resultado é verdadeiro
quando n = 1. Suponha que n > 1 e que o Corolário é verdadeiro quando n é
substituı́do por n − 1. Então [F(a1 , . . . , an−1 ) : F] é finita. Como an é algébrico sobre
F, e como F[x] ⊆ F(a1 , . . . , an−1 )[x], an é algébrico sobre F(a1 , . . . , an−1 ). Assim,
pelo Corolário 2.33, [F(a1 , . . . , an−1 , an ) : F(a1 , . . . , an−1 )] é finita. Mas usando o
Teorema 2.15, [F(a1 , . . . , an ) : F] = [F(a1 , . . . , an ) : F(a1 , . . . , an−1 )][F(a1 , . . . , an−1 ) :
F]. Portanto, F(a1 , . . . , an )/F é finita e algébrica.
Definição 2.35. Seja K um corpo de caracterı́stica p, n um inteiro positivo não
21
divisı́vel por p e ξ uma raiz n-ésima primitiva da unidade sobre K. Então o polinômio
n
Y
Qn (x) =
(x − ξ s )
s=1
é chamado o n-ésimo polinômio ciclotômico sobre K, onde o mdc(s, n) = 1.
Definição 2.36. Seja n um inteiro positivo. O corpo de decomposição de xn − 1
sobre um corpo K é chamado n-ésimo corpo ciclotômico sobre K e é denotado por
Kn . As raı́zes de xn − 1 em Kn são chamadas raı́zes n-ésimas da unidade sobre K.
Definição 2.37. Seja n ∈ Z∗+ , a Função ϕ de Euler, denotada por ϕ(n), é definida
como sendo o número de inteiros positivos menores do que n que são relativamente
primos com n, ou seja,
ϕ(n) = |{1 ≤ k < n; mdc(n, k) = 1}| .
Teorema 2.38. O corpo ciclotômico Kn é uma extensão algébrica simples de K.
Além disso:
i) Se K = Q, então o polinômio ciclotômico Qn é irredutı́vel sobre K e
[Kn : K] = ϕ(n),
onde ϕ(n) é a Função de Euler.
ii)Se K = Fq com mdc(q, n) = 1,então Qn é fatorado em ϕ(n)/d polinômios mônicos
irredutı́veis distintos em K[x] de mesmo grau d, Kn é um corpo de decomposição de
fator irredutı́vel sobre K e [Kn : K] = d, quando d é o menor inteiro positivo tal que
q d ≡ 1 mod n.
Demonstração: i) Ver página 61 de [4].
ii) Este é o item mais importante para os nossos propósitos, por isso ele será demonstrado. Seja η uma raiz n-ésima primitiva da unidade sobre Fq . Então η ∈ Fqk ,
k
se e somente se, η q = η, e a última identidade é equivalente a q k ≡ 1mod n. O
menor inteiro positivo tal que isso acontece é k = d, e assim η está em Fqd e não está
em nenhum subcorpo adequado do mesmo. Assim, o polinômio minimal de η sobre
22
Fq tem grau d, desde que η seja uma raiz arbitrária de Qn , daı́ segue os resultados
desejados.
Capı́tulo 3
Ordem de Polinômios e
Polinômios Primitivos
A teoria de polinômios sobre corpos finitos é importante para a investigação da
estrutura algébrica sobre corpos finitos, assim como para muitas aplicações. Sobretudo, polinômios irredutı́veis - os elementos principais do anel de polinômios sobre
um corpo finito - são indispensáveis para construção de corpos finitos e avaliação
dos elementos de um corpo finito. Apresentaremos a noção de ordem de um polinômio. E um importante fato é a ligação entre polinômios minimais de elementos
primitivos (chamado polinômios primitivos) e polinômios de maior ordem possı́vel
para um determinado grau.
Lema 3.1. Seja f (x) ∈ Fq [x] um polinômio de grau m ≥ 1 com f (0) 6= 0. Então
existe um inteiro positivo e ≤ q m − 1 tal que f (x) divide xe − 1.
Demonstração: O anel da classe de resı́duos
Fq [x] = {r + (f ); r ∈ F[x] e gr(r) < gr(f )}
contém q m − 1 resı́duos não nulos. As q m classes de resı́duos
xj + (f ), j = 0, 1, . . . , q m − 1
23
24
são não nulas e assim existem inteiros r e s com 0 ≤ r < s ≤ q m − 1 tal que
xs ≡ xr mod f (x). Visto que x e f (x) são relativamente primos, temos que xs−r ≡
1 mod f (x), então f (x) divide xs−r − 1 e 0 < s − r ≤ q m − 1. Portanto, e = s − r.
Uma vez que um polinômio constante não nulo divide x − 1, este polinômio pode
ser incluido na seguinte definição:
Definição 3.2. Seja f ∈ Fq [x] um polinômio não nulo.
i) Se f (0) 6= 0, então o menor inteiro positivo e para o qual f (x) divide xe − 1 é
chamado a ordem de f e denotado por ord(f ) = ord(f (x)).
ii) Se f (0) = 0, então f (x) = xh g(x), onde h ∈ Z∗+ e g ∈ Fq [x] com g(0) 6= 0 são
unicamente determinados e ord(f ) é definida como sendo a ord(g).
A ordem de um polinômio é algumas vezes chamada de perı́odo ou expoente de
f (x) e pode ser caracterizada seguindo maneiras alternativas.
Teorema 3.3. Seja f ∈ Fq [x] um polinômio irredutı́vel sobre Fq de grau m e com
f (0) 6= 0. Então ord(f ) é igual a ordem de uma raiz de f (x) no grupo multiplicativo
F∗qm .
Demonstração: De acordo com o Corolário 2.20, Fqm é o corpo de decomposição
de f (x) sobre Fq . As raı́zes de f (x) tem a mesma ordem no grupo F∗qm pelo Teorema
2.22. Seja α ∈ F∗qm uma raiz qualquer de f (x). Então obtemos pelo Lema 2.16
αe = 1, se e somente se, f (x) divide xe − 1. Os resultados seguem a partir da
definição da ord(f ) e da ordem de α no grupo F∗qm .
Corolário 3.4. Se f (x) ∈ Fq [x] é um polinômio irredutı́vel sobre Fq de grau m,
então ord(f ) divide q m − 1.
Demonstração: Se f (x) = cx com c ∈ F∗q , então ord(f ) = 1, pois pela Definição
3.2 f (0) = 0, assim g(x) = c, g(0) 6= 0 e g(x) divide xe − 1, onde e é o menor inteiro
tal que isso acontece. Caso contrário, o resultado segue do Teorema 3.3, pelo fato
de que F∗q é um grupo de ordem q m − 1, sendo α ∈ F∗qm , ord(α) divide q m − 1 e
ord(α) = ord(f ). Portanto, ord(f ) divide q m − 1.
25
Para polinômios redutı́veis o Corolário 3.4 não é válido (veja o exemplo 3.10). O
Teorema 3.3 leva a uma fórmula para o número de polinômios mônico irredutı́veis
de dado grau e dada ordem. Vamos usar ϕ para denotar a função de Euler. A
terminologia seguinte será conveniente: se n ∈ Z+ é relativamente primo com b ∈
Z, então o menor inteiro positivo k para o qual bk ≡ 1 mod n é chamado ordem
multiplicativa de b módulo n.
Teorema 3.5. O número de polinômios mônico irredutı́veis de grau m em Fq [x] e
ordem e é igual a:
i) ϕ(e)/m se e ≥ 2 e m é a ordem multiplicativa de q módulo e;
ii) 2 se m = e = 1;
iii) 0 em todos os outros casos.
Em particular, o grau de um polinômio irredutı́vel em Fq [x] de ordem e deve ser
igual a ordem multiplicativa de q módulo e.
Demonstração: Seja f (x) um polinômio irredutı́vel em Fq [x] com f (0) 6= 0.
Então de acordo com o Teorema 3.3 temos ord(f ) = e, se e somente se, todas
as raı́zes de f (x) são raı́zes primitivas da unidade sobre Fq . Em outras palavras,
temos ord(f ) = e, se e somente se, f (x) divide o polinômio ciclotômico Qe . Pelo
Teorema 2.38 qualquer fator mônico irredutı́vel de Qe tem o mesmo grau m, o menor
inteiro positivo tal que q m ≡ 1 mod e, e o número destes fatores é dado por ϕ(e)/m.
Para m = e = 1, considerando o polinômio mônico irredutı́vel f (x) = x obtemos o
resultado.
Os valores da ord(f (x)) estão disponı́veis na forma de tabelas, pelo menos para
polinômios irredutı́veis. Uma vez que qualquer polinômio de grau positivo pode
ser escrito como um produto de polinômios irredutı́veis, o cálculo das ordens dos
polinômios pode ser feito quando souber determinar como a ordem de uma potência
de um polinômio irredutı́vel e a ordem do produto de polinômios relativamente
primos dois a dois. A discussão seguinte é dedicada a estas questões.
26
Lema 3.6. Seja c ∈ Z+ . Então o polinômio f (x) ∈ Fq [x] com f (0) 6= 0 divide
xc − 1, se e somente se, ord(f ) divide c.
Demonstração: Se e = ord(f ) divide c, então f (x) divide xe − 1 e xe − 1 divide
xc − 1, logo f (x) divide xc − 1. Inversamente, se f (x) divide xc − 1, temos c ≥ e,
logo podemos escrever c = me + r, com m ∈ N e 0 ≤ r < e. Como
xc − 1 = (xme − 1)xr + (xr − 1),
segue-se que f (x) divide xr − 1, que só é possı́vel para r = 0. Portanto, e divide
c.
Corolário 3.7. Se e1 e e2 são inteiros positivos, então o máximo divisor comum
entre xe1 − 1 e xe2 − 1 em Fq [x] é xd − 1, onde d é o máximo divisor comum de e1
e e2 .
Demonstração: Seja f (x) (mônico) o máximo divisor comum de xe1 − 1 e xe2 − 1.
Como xd − 1 é um divisor comum de xe1 − 1 e xe2 − 1, segue que xd − 1 divide f (x).
Por outro lado, f (x) é um divisor comum de xe1 − 1 e xe2 − 1, e pelo Lema 3.6 temos
que a ord(f ) divide e1 e e2 . Consequentemente, ord(f ) divide d e, portanto, f (x)
divide xd − 1 pelo Lema 3.6. Deste modo, só podemos ter f (x) = xd − 1.
Já que as potências de x são obtidas com antecedência ao determinar a ordem
de um polinômio, não precisamos considerar as potências de polinômios irredutı́veis
g(x) com g(0) = 0.
Teorema 3.8. Seja g(x) ∈ Fq [x] irredutı́vel sobre Fq com g(0) 6= 0 e ord(g) = e e
seja f (x) = g b (x) com b ∈ Z+ . Seja t o menor inteiro positivo tal que pt ≥ b, onde
p é a caracterı́stica de Fq . Então ord(f ) = ept .
Demonstração: Assumindo c = ord(f ), note que a divisibilidade de xc − 1 por
f (x) implica na divisibilidade de xc − 1 por g(x), obtemos assim que e divide c pelo
Lema 3.6. Além disso, g(x) divide xe − 1, assim, f (x) divide (xe − 1)b e, a fortiori 1 ,
1
com mais razão, para uma razão mais forte ou firme
27
t
divide (xe − 1)p = xe pt − 1. De acordo com Lema 3.6, c divide ept . Segue, a partir
do que foi mostrado até aqui, que c = epu com 0 ≤ u ≤ t. Nota-se que xe − 1
tem apenas raı́zes simples, uma vez que e não é múltiplo de p pelo Corolário 3.4.
Portanto, todas as raı́zes de
xe pu − 1 = (xe − 1)pu
tem multiplicidade pu . Mas g b (x) divide xe pu − 1, por isso comparando as multiplicidades das raı́zes pu ≥ b, e u ≥ t. Deste modo tempos u = t e c = ept .
Teorema 3.9. Sejam g1 (x), . . . , gk (x) polinômios não nulos dois a dois relativamente primos sobre Fq e seja f (x) = (g1 · · · gk )(x). Então ord(f ) é igual ao mı́nimo
múltiplo comum de ord(g1 ), . . . , ord(gk ).
Demonstração: É fácil ver que, é suficiente considerar o caso quando g(0) 6= 0
para 1 ≤ i ≤ k.
Faça e = ord(f ) e ei = ord(gi ) para 1 ≤ i ≤ k, e seja
c = mmc(e1 , . . . , ek ). Então cada gi (x), 1 ≤ i ≤ k, divide xei − 1, e então gi (x)
divide xc − 1. Por g1 , . . . , gk serem dois a dois relativamente primos, temos que f (x)
divide xc − 1. Uma aplicação do Lema 3.6 mostra que e divide c. Por outro lado,
f (x) divide xe − 1, e assim cada gi (x), 1 ≤ i ≤ k, divide xe − 1. Novamente pelo
Lema 3.6, segue-se que cada ei , 1 ≤ i ≤ k, divide e e assim c divide e. Deste modo,
concluimos que e = c.
Usando o mesmo argumento que anteriormente, nós conseguimos, de fato, mostrar que a ordem do mı́nimo múltiplo comum de alguns polinômios não nulos é igual
ao mı́nimo múltiplo comum das ordens desses polinômios.
Exemplo 3.10. Vamos calcular a ordem do polinômio
f (x) = x10 + x9 + x3 + x2 + 1 ∈ F2 [x].
Fatorando f (x) sobre F2 temos:
f (x) = (x4 + x + 1)(x6 + x5 + x3 + x + 1)
28
que nos dá
f (x) = (x2 + x + 1)3 (x4 + x + 1).
Denote g1 (x) = x2 + x + 1 e g2 (x) = x4 + x + 1. Primeiramente será determinado a
ordem de g13 . Note que ord(x2 + x + 1) = 3 e como a caracterı́stica de F2 é dois,
temos pelo Teorema 3.8 que 2t ≥ 3 o que resulta em t = 2. Deste modo,
ord((x2 + x + 1)3 ) = 3 · 22 = 12.
Além disso, ord(x4 + x + 1) = 15 pela Definição 3.2. Sendo f = g13 g2 , pelo Teorema
3.9 temos que f = g13 g2 , então
ord(f ) = mmc(ord(g1 ), ord(g2 )),
isto é, ord(f ) = mmc(12, 15) = 60. Temos que ord(f ) não divide 210 − 1,
isso nos dá um contra-exemplo para o Corolário 3.4, no qual o polinômio precisa
ser irredutı́vel.
Com base nas informações fornecidas acima, chegamos a seguinte fórmula geral
para a ordem de um polinômio. Basta considerar polinômios de grau positivo e com
termo constante não nulo.
Teorema 3.11. Seja Fq um corpo finito com caracterı́stica p e seja f ∈ Fq [x] um
k
polinômio de grau positivo e com f (0) 6= 0. Seja f = af1b1 · · · fkb uma fatoração
canônica de f em Fq [x], onde a ∈ Fq , b1 , . . . , bk ∈ N e f1 , . . . , fk polinômios mônico
irredutı́veis em Fq [x]. Então ord(f ) = ept , onde e é o mı́nimo múltiplo comum de
ord(f1 ), . . . , ord(fk ) e t é o menor inteiro tal que pt ≥ max{b1 , . . . , bk }.
Demonstração: Ver página 78 de [4].
Há uma relação ı́ntima entre as ordens de f (x) e f (−x). Desde que f (x) = f (−x)
para um corpo de caracterı́stica dois, basta considerar corpos finitos de caracterı́stica
ı́mpar.
29
Teorema 3.12. Para q ı́mpar, seja f ∈ Fq [x] um polinômio de grau positivo com
f (0) 6= 0. Sejam e e E as ordens dos polinômios f (x) e f (−x) respectivamente.
Então E = e se e é múltiplo de 4 e E = 2e se e é ı́mpar. Se e é duas vezes um
número ı́mpar, então E = e/2 se todo fator irredutı́vel de f tem mesma ordem e
E = e caso contrário.
Demonstração: Como ord(f (x)) = e, f (x) divide x2e − 1 e f (−x) divide
(−x)2e − 1 = x2e − 1. Assim E divide 2e pelo Lema 3.6. Pelo mesmo argumento, e
divide 2E, e assim E só pode ser 2e, e ou e/2. Se e é múltiplo de 4, então e e E são
pares. Como f (x) divide xe − 1, f (−x) divide (−x)e − 1 = xe − 1 e então E divide
e. Analogamente, e divide E e isso nos dá E = e. Se e é ı́mpar, então f (−x) divide
(−x)e − 1 = −xe − 1 e também xe + 1. Então f (−x) não pode dividir xe − 1, e por
isso devemos ter E = 2e. No restante dos casos temos e = 2h, com h um inteiro
ı́mpar. Seja f uma potência de polinômio irredutı́vel em Fq [x]. Então f (x) divide
(xh − 1)(xh + 1) e f (x) não divide xh − 1 com ord(f ) = 2h. Mas xh − 1 e xh + 1
são relativamente primos e isso implica que f (x) divde xh + 1. Consequentemente,
f (−x) divide (−x)h + 1 = −xh + 1 e também xh − 1. Segue que E = e/2. Note
que pelo Teorema 3.8 a potência de um polinômio irredutı́vel tem ordem ı́mpar se e
somente se o polinômio irredutı́vel próprio tem ordem ı́mpar. Para f (x) geral, temos
a fatoração f = g1 · · · gk , onde cada gi é uma potência de um polinômio irredutı́vel
e g1 , . . . , gk são dois a dois primos entre si. Além disso,
2h = mmc{ord(g1 ), . . . , ord(gk )}
de acordo com o Teorema 3.9. Organizamos os gi de tal forma que ord(gi ) = 2hi ,
para 1 ≤ i ≤ m e ord(gi ) = hi para m + 1 ≤ i ≤ k, onde hi são inteiros ı́mpares com
mmc{h1 , . . . , hk } = h. Pelo que já foi demonstrado, temos que ord(gi (−x)) = hi
para 1 ≤ i ≤ m e ord(gi (−x)) = 2hi para m + 1 ≤ i ≤ k. Então pelo Teorema 3.9
temos
E = mmc {h1 , . . . , hm , 2hm+1 , . . . , 2hk } ,
30
e assim E = h = e/2 se m = k e E = 2h = e se m < k. Essas fórmulas são
equivalentes às dadas na última parte do enunciado.
Segue, a partir do Lema 3.1 e da Definição 3.2, que a ordem do polinômio de
grau m ≥ 1 sobre Fq é no máximo q m − 1. Essa cota é atingida para uma classe
importante de polinômios, a saber, os chamados polinômios primitivos. A definição
de polinômio primitivo é baseada na noção de elemento primitivo introduzida na
Definição 2.25.
Definição 3.13. Um polinômio f (x) ∈ Fq [x] de grau m ≥ 1 é chamado polinômio
primitivo sobre Fq se for o polinômio minimal sobre Fq de um elemento primitivo
de Fqm .
Um polinômio primitivo sobre Fq de grau m pode ser descrito como um polinômio
mônico que é irredutı́vel sobre Fq e tem uma raiz α ∈ Fqm que gera o grupo multiplicativo de Fqm . Polinômios primitivos também podem ser caracterizados como se
segue.
Teorema 3.14. Um polinômio f (x) ∈ Fq [x] de grau m é um polinômio primitivo
sobre Fq se, e somente se, f (x) é mônico, f (0) 6= 0, e ord(f ) = q m − 1.
Demonstração: Se f (x) é primitivo sobre Fq , então f é mônico e f (0) 6= 0. Como
f é irredutı́vel sobre Fq , temos ord(f ) = q m − 1 pelo Teorema 3.3 e, de fato, f
tem um elemento primitivo de Fqm que é uma raiz. Reciprocamente, a propriedade
ord(f ) = q m − 1 implica que m ≥ 1. Logo, temos que f é irredutı́vel sobre Fq .
Então f é uma potência de um polinômio ou ele pode ser escrito como produto de
dois polinômios relativamente primos de grau positivo. No primeiro caso, temos
f = g b , com g ∈ Fq [x] irredutı́vel sobre Fq , g(0) 6= 0 e b ≥ 2. Então, de acordo
com o Teorema 3.8, ord(f ) é divisı́vel pela caracterı́stica de Fq , mas q m − 1 não é,
contradição! No segundo caso, temos f = g1 g2 onde g1 , g2 ∈ Fq [x] são polinômios
mônicos relativamente primos e de grau positivo m1 e m2 , respectivamente. Se
e1 = ord(g1 ) e e2 = ord(g2 ), então ord(f ) ≤ e1 e2 pelo Teorema 3.9. Além disso,
31
ei ≤ q mi − 1, i = 1, 2, pelo Lema 3.1, consequentemente
ord(f ) ≤ (q m1 − 1)(q m2 − 1) < q m1 +m2 − 1 = q m − 1,
contradição! Portanto, f é irredutı́vel sobre Fq e, pelo que diz o Teorema 3.3, f é
um polinômio primitivo sobre Fq .
Exemplo 3.15. Tome o corpo finito
F8 [x] = {0, 1, x, x2 , 1 + x, 1 + x2 , x + x2 , 1 + x + x2 }.
Pelo Teorema 3.14 temos que o polinômio mônico p(x) = x3 + x + 1 é o polinômio
primitivo do corpo F8 [x], pois p(0) = 1 6= 0 e ord(p(x)) = 23 − 1 = 7 pela Definição
3.2.
Observamos que a condição f (0) 6= 0 no Teorema 3.14 só é necessária para excluir
o polinômio não-primitivo f (x) = x no caso q = 2 e m = 1. Outra caracterı́stica do
polinômio primitivo é baseado no seguinte resultado auxiliar:
Lema 3.16. Seja f ∈ Fq [x] um polinômio de grau positivo com f (0) 6= 0. Seja r o
menor inteiro positivo para o qual xr é congruente a algum elemento de Fq módulo
f (x), de modo que xr ≡ a mod f (x), sendo a ∈ F∗q unicamente determinado. Então
ord(f (x)) = hr, onde h é a ordem de a no grupo multiplicativo F∗q .
Demonstração: Coloque e = ord(f ). Como xe ≡ 1 mod f (x), devemos ter e ≥ r.
Então podemos escrever e = sr + t, com s ∈ N e 0 ≤ t ≤ r. Agora
1 ≡ xe ≡ xsr+t ≡ as xt mod f (x),
(3.1)
logo xt ≡ a−s mod f (x) e por causa da definição de r, isso só é possı́vel se t = 0. A
congruência (3.1) nos dá, em seguida, as ≡ 1 mod f (x), então as = 1 e assim s ≥ h
e e ≥ hr. Por outro lado,
xhr ≡ ah ≡ 1 mod f (x),
e assim, e = hr.
32
Teorema 3.17. O polinômio mônico f ∈ Fq [x] de grau m ≥ 1 é um polinômio
primitivo sobre Fq se, e somente se, (−1)m f (0) é um elemento primitivo de Fq e o
menor inteiro positivo r para o qual xr é congruente a algum elemento de Fq módulo
f (x) é
r = (q m − 1)/(q − 1).
No caso em que f (x) é primitivo sobre Fq temos
xr ≡ (−1)m f (0) mod f (x).
Demonstração: Se f (x) é primitivo sobre Fq , então f tem uma raiz α ∈ Fqm que
é um elemento primitivo de Fqm . Calculando a norma NFqm /Fq (α), pelas Definições
2.26 e 2.27, e observando que f é carcaterı́stica polinomial de α sobre Fq , chegamos
a identidade
(−1)m f (0) = α(q
m −1)/(q−1)
.
(3.2)
Segue que a ordem de (−1)m f (0) em F∗q é q − 1, logo, (−1)m f (0) é um elemento
primitivo de Fq . Uma vez que f é o polinômio minimal de α sobre Fq , a identidade
(3.2) implica que
x(q
m −1)/(q−1)
≡ (−1)m f (0)mod f (x)
e assim, r ≤ (q m −1)/(q−1). Mas pelo Teorema 3.14 e Lema 3.16 temos que q m −1 =
ord(f (x)) ≤ (q − 1)r, logo r ≥ (q m − 1)/(q − 1). Portanto, r = (q m − 1)/(q − 1).
Reciprocamente, suponha que as condições do Teorema sejam satisfeitas. Segue que
r = (q m − 1)/(q − 1)
e pelo Lema 3.16 temos que a ord(f )é relativamente prima com q. Então o Teorema
3.11 mostra que f pode ser fatorado na forma f = f1 · · · fk , onde os fi são polinômios
mônicos distintos irredutı́veis sobre Fq se mi = gr(fi ), logo ord(fi ) divide q mi − 1,
para 1 ≤ i ≤ k de acordo com o Corolário 3.4. Agora, q mi − 1 divide
d = (q m1 − 1) · · · (q mk − 1)/(q − 1)k−1 ,
33
então ord(fi ) divide d para 1 ≤ i ≤ k. E assim, pelo Lema 3.6 tem-se f (x) divide
xd − 1 para 1 ≤ i ≤ k e assim f (x) divide xd − 1. Se k ≥ 2, então
d < (q m1 +···+mk − 1)/(q − 1) = (q m − 1)/(q − 1) = r,
contradizendo a definição de r. Portanto, k = 1 e f é irredutı́vel sobre Fq . Se β ∈ Fqm
é uma raiz de f , segue, pelo argumento principal (3.2) que β r = (−1)m f (0), e assim
xr ≡ (−1)m f (0)mod f (x).
Uma vez que a ordem de (−1)m f (0) em Fq∗ é q − 1, resulta pelo Lema 3.16 que
ord(f ) = q m − 1, deste modo, f é primitivo sobre Fq pelo Teorema 3.14.
Observação 3.18. Nos Teoremas a seguir serão omitidas as demonstrações, pois
são demasiadamente longas. Tais demonstrações podem ser encontradas em [4] nas
páginas 87 e 88, respectivamente.
Teorema 3.19. Seja α um elemento da extensão do corpo Fqm de Fq . Suponha que
o grau de α sobre Fq é d e que g(x) ∈ Fq [x] é o polinômio minimal de α sobre Fq .
Então:
i) g(x) é irredutı́vel sobre Fq e o grau d divide m
ii) Um polinômio f (x) ∈ Fq [x] satisfaz f (α) = 0 se, e somente se, g divide f .
iii) Se f (x) ∈ Fq [x] é um polinômio mônico irredutı́vel com f (α) = 0, então f = g.
d
m
iv) g(x) divide xq − x e xq − x.
v) As raı́zes de g(x) são α, αq , . . . , αq
d −1
, e g é o polinômio minimal sobre Fq de
todos esses elementos.
vi) Se α 6= 0, então ord(g) é igual a ordem de α no grupo multiplicativo F∗qm .
vii) g(x) é um polinômio primitivo sobre Fq se, e somente se, α é a ordem de q d − 1
em F∗qm .
Vamos descrever o princı́pio geral para obter um novo polinômio a partir dos
primeiros conhecidos. Ele depende de um resultado auxiliar da teoria de números.
Lembramos que se n é um inteiro positivo e um inteiro b é relativamente primo
34
com n, então o menor inteiro positivo k para o qual bk ≡ 1 mod n é chamado ordem
multiplicativa de b módulo n. Notamos que essa ordem multiplicativa divide qualquer
outro inteiro positivo h para o qual bh ≡ 1 mod n.
Lema 3.20. Seja s ≥ 2 e e ≥ 2 inteiros relativamente primos e seja m a ordem
multiplicativa de s módulo e. Seja t ≥ 2 um inteiro cujo fatores primos divide e
mas não divide (sm − 1)/e. Admita que sm ≡ 1 mod 4 se t ≡ 0 mod 4. Então a
ordem multiplicativa de s módulo et é igual a mt.
Teorema 3.21. Seja f1 (x), . . . , fn (x) polinômios mônicos irredutı́veis em Fq [x] de
grau m e ordem e e seja t ≥ 2 um inteiro cujos fatores primos divide e mas não
divide (q m − 1)/e. Admita q m ≡ 1 mod 4 se t ≡ 0 mod 4. Então f1 (xt ), . . . , fn (xt )
são polinômios mônicos irredutı́veis distintos em Fq [x] de grau mt e ordem et.
Conclusão
Apresentamos, neste trabalho, como definir a ordem de um polinômio e a ligação
enre polinômios primitivos e polinômios de maior ordem possı́vel para um determinado grau. Vimos que a ordem de um polinômio pode ser caracterizada como a
ordem de uma raı́z deste polinômio. Aprendemos a quantificar polinômios mônico
irredutı́veis usando a Função de Euler, calculamos a ordem de uma potência de um
polinômio irredutı́vel e a ordem do produto de polinômios relativamente primos dois
a dois. Mostramos também que a ordem de um polinômio mônico escrito como produto de polinômios irredutı́veis é dada pelo minimo múltiplo comum das ordens dos
polinômios irredutiveis. E por fim vimos que a ordem de um polinômio primitivo é
no máximo q m − 1, onde m é o grau do polinômio e q a caracterı́stica do corpo.
35
Referências Bibliográficas
[1] GARCIA, Arnaldo; LEQUAIN, Yves. Elementos de Álgebra. Rio de Janeiro:
IMPA, 2008.
[2] HEFEZ, Abramo; VILLELA, Maria Lucia T. Códigos Corretores de erros.
Rio de Janeiro: IMPA, 2008.
[3] HERSTEIN, I. N. Topics in Algebra. New Jersey: Prentice-Hall, 1996.
[4] LIDL, Rudolf; NIEDERREITER, Harald., Introduction to finite fields and
their applications. Cambridge: Cambridge University Press, 1986.
[5] McCarthy, Paul; Algebraic Extensions of Fields. New York, 1976.
[6] MESQUITA, Aline Mota; Teoria dos Códigos Corretores de Erros. Monografia Especialização em Matemática. UFG, 2005.
36