Sumário - univasf.edu.brfelipe.wergete/ensino/profmat_arit/aritmetica... · Aritmética à Álgebra, que essencialmente foi desenvolvida com o ob-jetivo de resolver equações. A

ii

�aritmetica_linear� � 2012/10/1 � 15:22 � page V � #1 ii

ii

ii

Sumário

Prefácio VII

1 Sistemas de Equações Lineares 5

1.1 Sistemas de Equações Lineares em R . . . . . . . . . . 5

1.1.1 Revisão . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Classi�cação dos Sistemas . . . . . . . . . . . . 8

1.1.3 Interpretação Geométrica . . . . . . . . . . . . 9

1.1.4 Eliminação Gaussiana . . . . . . . . . . . . . . 11

1.1.5 Matriz Escalonada por Linhas . . . . . . . . . 11

1.1.6 Complemento . . . . . . . . . . . . . . . . . . . 15

1.2 Sistemas de Equações Lineares em Z . . . . . . . . . . 15

1.2.1 Um Pouco de Aritmética dos Inteiros . . . . . . 16

1.2.2 A Forma Algoritmica . . . . . . . . . . . . . . . 21

1.3 Interpretação geométrica . . . . . . . . . . . . . . . . . 27

V

ii

�aritmetica_linear� � 2012/10/1 � 15:22 � page VI � #2 ii

ii

ii

VI SUMÁRIO

2 O Problema do Troco de Frobênius 31

2.1 Introdução. . . . . . . . . . . . . . . . . . . . . . . . . 31

2.1.1 Boa Posição. . . . . . . . . . . . . . . . . . . . . 32

2.2 O Caso Bidimensional. . . . . . . . . . . . . . . . . . . 34

2.2.1 Corolário Sobre o Caso Geral. . . . . . . . . . . 35

2.3 O Caso Tridimensional. . . . . . . . . . . . . . . . . . . 38

2.3.1 Corolário Sobre o Caso Tridimensional. . . . . . 38

2.3.2 Solução Algorítmica. . . . . . . . . . . . . . . . 40

2.3.3 Comentários e Casos Especiais. . . . . . . . . . 41

3 Pontos Inteiros em Regiões Poligonais 45

3.1 O Teorema de Pick . . . . . . . . . . . . . . . . . . . . 46

3.1.1 Teorema de Pick e a fórmula de Euler . . . . . . 51

3.1.2 Área de Polígonos no Plano . . . . . . . . . . . 53

3.1.3 Teorema de Pick Generalizado e Estimativas de

Plantação . . . . . . . . . . . . . . . . . . . . . 56

3.2 O tetraedro de Reeve . . . . . . . . . . . . . . . . . . . 59

4 Apêndice-Reticulados 63

4.1 Reticulados e seus Domínios Fundamentais . . . . . . . 63

Referências 68

ii

�aritmetica_linear� � 2012/10/1 � 15:22 � page VII � #3 ii

ii

ii

Prefácio

As notas que serão utilizadas no mini-curso Aritmética Linear na VI

Bienal da SBM foram escritas para o evento e representam mais um

fruto dos seminários informais da UFRPE, designado (também in-

formalmente) Especulatione Arithmeticae. O nome, bem sugestivo, é

uma clara alusão ao clássico do Gauss Disquisitione Arithmeticae.

O Seminário Especculatione Arithmeticae tem aproximadamente um

ano de existência e os três primeiros autores dessas notas alguns dos

fundadores. Nesse espaço discutimos questões ligadas a Teoria dos

Números e Álgebra ainda que a abordagem muitas vezes pode ser Ge-

ométrica, Combinatória e/ou Analítica. O principal fator para tanta

diversidade é a heterogêneidade do grupo - composto por alguns jovens

(alguns nem tanto) professores da UFRPE e da UFPE, com formação

diversi�cada. Além de temas de pesquisa nos interessamos também

por temas relacionados a divulgação Matemática e escolhemos a Teo-

ria dos Números por ser uma paixão comum que nos une e inspira,

VII

ii

�aritmetica_linear� � 2012/10/1 � 15:22 � page VIII � #4 ii

ii

ii

VIII SUMÁRIO

embora não haja entre nós nenhum especialista na área.

A quarta autora foi estudante de graduação da UFRPE e sua

monogra�a inspirou completamente o terceiro capítulo dessas notas.

Recife, Setembro de 2012

Rodrigo Gondim

Gabriel Guedes

Eudes Naziazeno

Brianne Mourão

ii

�aritmetica_linear� � 2012/10/1 � 15:22 � page 1 � #5 ii

ii

ii

Introdução

A Aritmética é uma área milenar da Matemática que ocupa-se, prin-

cipalmente, dos números inteiros; suas propriedades e das soluções

de equações com coe�cientes inteiros das quais buscam-se soluções in-

teiras. Estas equações são chamadas Equações Diofantinas (em home-

nagem ao Matemático Grego Diofanto), e a própria obra do Diofantus

- A Aritmética - inicia o longo processo de associação e in�uência da

Aritmética à Álgebra, que essencialmente foi desenvolvida com o ob-

jetivo de resolver equações.

A Aritmética de Diofanto (250) é um interessante registro histórico

que diferencia-se das principais obras gregas da época, que tinham

uma postura mais teórico-axiomática, e se assemelha a antigos textos

babilônicos, no sentido que a mesma é um compêndio de problemas

e suas soluções, demonstrações aparecem em casos particulares no in-

tuito de resolver um problema concreto. A Aritmética de Diofanto

1

ii


ii

ii

2 SUMÁRIO

foi um texto de valor inestimável tendo sido utilizado por mais de mil

anos, em particular foi numa cópia de tal livro que Fermat cunhou o

enunciado do que foi conhecido como o Último Teorema de Fermat.

Grande parte dos problemas de Diofanto podem ser formulados em ter-

mos de Equações lineares - determinadas ou indeterminadas - e isso

in�uencia o nome do curso - Aritmética Linear . Gauss, em seu mem-

orável Disquisitiones Arithmeticae (1801) escreve sobre o Diofanto:

�The celebrated work of Diophantus, dedicated to the problem of inde-

terminateness, contains many results which excite a more than ordi-

nary regard for the ingenuity and pro�ciency of the author, because of

their di�culty and the subtle devices he uses, especially if we consider

the few tools that he had at hand for his work�.

Aritmética Linear é portanto o estudo de equações, inequações e sis-

temas de equações lineares, com coe�cientes inteiros, dos quais bus-

camos soluções inteiras. Assim sendo estamos realmente interessados

em generalizações dos problemas considerados por Diofanto. Entre-

tanto a palavra linear em nosso contexto tem ainda outro signi�cado,

não apenas de primeiro grau, e este é de caráter geométrico. A maio-

ria dos problemas que descreveremos tem uma formulação geométrica

interessante e muitas vezes nos utilizamos da mesma para estudar o

problema.

Foi o Filósofo e Matemático Francês Descartes o idealizador da fusão

entre a Álgebra e a Geometria no clássico La Geometrie, no qual o au-

tor lança as sólidas bases para o que chamamos Geometria Analítica.

Em seu Discurso do Método (inicialmente concebido como prefácio de

suas 3 obras cientí�cas - Dioptrica, Geometria e Meteoros) Descartes

explica sua motivação ao estudo da geometria por meio de equações

inicialmente notando os defeitos da Geometria Euclidiana clássica e

ii


ii

ii

0.0 SUMÁRIO 3

da Álgebra Árabe.

no que se refere a geometria dos antigos e a álgebra dos modernos,

além de só se aplicarem a matérias muito abstratas e que parecem

sem nenhuma utilidade , a primeira é sempre tão restrita à consider-

ação de �guras, que não se pode exercitar o entendimento sem muito

cançar a imaginação; e os cultores da última tanto se sujeitaram a

certas regras e a certos símbolos, que a transformaram em uma arte

confusa e obscura...

A partir daqui o autor revela o que fez para agrupar as vantagens da

Álgebra, da Geometria e da Lògica sem seus defeitos.

para melhor considerá-las em particular, devia supô-las em linhas, pois

não achava nada de mais simples nem que eu pudesse representar mais

distintamente para a minha imaginação; para compreender várias de-

las juntas, era preciso que eu as explicasse por símbolos os mais curtos

possíveis; e com isso tomaria o melhor da geometria e da álgebra e cor-

rigiria todos os defeitos de uma pela outra.

No primeiro capítulo destas notas trataremos de Equações e sis-

temas Diofantinos Lineares, geometricamente estes correspondem ao

problema de determinar pontos inteiros em interseção de hiperplanos.

Utilizaremos as vantagens da álgebra, explicitamente de uma versão

�inteira� do método de eliminação de Gauss (chamado eliminação uni-

modular) para resolver os sistemas e interpretaremos geometricamente

o resultado pela teoria geométrica dos reticulados.

no segundo capítulo trataremos do famoso problema do troco de

Frobênius que geometricamente consiste em determinar condiçoes para

que certos hiperplanos possuam pontos inteiros não-negativos. Aqui

ii


ii

ii

4 SUMÁRIO

damos uma abordagem geométrica e algoritma para um problema que

em geral é NP-completo, tendo solução apenas em casos particulares,

mais precisamente, em dimensão baixa.

No último capítulo consideramos o problema de contar a quanti-

dade de pontos inteiros em um polígono plano, esse problema é con-

hecido como problema inverso de Pick e tem um ijnteressante apelo

geométrico e algumas aplicações; ele pode ser interpretado como o

problema de contar o número de soluções de certos sistemas de in-

equações lineares.

ii


ii

ii

CAPÍTULO 1

Sistemas de Equações Lineares

1.1 Sistemas de Equações Lineares em R

Logo nas séries iniciais aprendemos a resolver problemas como estes:

Exemplo 1.1.1. Após percorrer 27de um percurso, e caminhado 5

11

do mesmo, um atleta percebeu que ainda faltavam 600 metros para

completar o percurso. Qual o comprimento total do percurso?

Exemplo 1.1.2. Em um cassino, uma pessoa introduz numa máquina

um determinado número de �chas e recebe dela o dobro da quan-

tia original, decrescido de 10 unidades. Em uma segunda máquina,

coloca essa nova quantidade e recebe novamente o dobro, mas agora

decrescida de 30 unidades. Finalmente numa terceira máquina, coloca

a nova quantidade obtida e recebe mais uma vez o dobro, menos 40

5

ii


ii

ii

6 Sistemas de Equações Lineares

unidades. Coincidentemente, o valor �nal é o mesmo que a quanti-

dade introduzida na primera máquina. Qual a quantidade original de

�chas?

Esses são exemplos de problemas de equação do 1o grau em uma

variável. Quando vamos crescendo, aprendemos a resolver problemas

como:

Exemplo 1.1.3. Tenho dois �lhos. A soma de suas idades é 18 anos.

E a diferença entre suas idades é de 4 anos. Quais as idades dos meus

�lhos?

Exemplo 1.1.4. Um par de tênis, duas bermudas e três camisas cus-

tam juntos R$ 100,00. Dois pares de tênis, cinco bermudas e oito

camisas custam juntos R$ 235,00. Quanto custam juntos um ar de

tênis , uma bermuda e uma camisa?

Esses são exemplos de problemas envolvendo sistemas de equações

lineares. Nas próximas seções iremos fazer uma breve revisão de vários

resultados sobre sistemas lineares em R dos quais todo aluno nos

semestres iniciais de um curso de exatas aprende a maioria dos re-

sultados que seguem nesse texto. Após isso, iremos fazer uma revisão

de aritmética e concluiremos com um estudo dos sistemas lineares em

Z.

1.1.1 Revisão

Mas o que é mesmo um sistema de equações lineares?

Chamamos de sistema com m ≥ 1 equações lineares a n variáveis o

ii


ii

ii

1.1 Sistemas de Equações Lineares em R 7

conjunto:

S

a11x1 +a12x2 + · · · +a1nxn = b1

a21x1 +a22x2 + · · · +a2nxn = b2...

.... . .

...

am1x1 +am2x2 + · · · +amnxn = bm

(1.1)

Os termos aij são ditos coe�centes. Os xi são chamados de variáveis.

E os bj são os termos independentes. Observe que podemos escrever

o sistema na sua forma matricial:

AX = B

Onde

Am×n =

a11 a12 · · · a1n

a21 a22 · · · a2n...

.... . .

...

am1 am2 · · · amn

, Xn×1 =

x1

x2...

xn

, Bn×1 =

b1

b2...

bn

Exemplo 1.1.5. Dado o sistema:

x + y + 2z = 5

x − y + 3z = 6

2x + y − z = 7

(1.2)

temos para esse sistema

A3×3 =

1 1 2

1 −1 3

2 1 −1

, X3×1 =

x

y

z

, B3×1 =

5

6

7

Diremos que a n-upla (r1, r2, · · · , rn) é solução do sistema 1.1, se

ela é solução de cada uma das equações do sistema. O conjunto de

todas as soluções é chamado conjunto-solução. Podemos classis�car

os sistemas a partir das suas soluções.

ii


ii

ii


1.1.2 Classi�cação dos Sistemas

Sistemas Impossíveis

Nem todo sistema pode ser resolvido em R. Um sistema que não

possui solução real, ou seja, seu conjunto-solução é o φ, será chamado

sistema impossível.

Exemplo 1.1.6. Os seguintes sistemas são impossíveis:

S1 :

{x+ y = 1

2x+ 2y = 7S2 :

2x+ 3y = 2

5x− 3y = 5

3x+ 2y = 4

Sistemas Possíveis e Determinados

Um sistema é chamado de possível e determinado se possui solução e

essa solução é única.

Exercício 1. Veri�que que o sistema abaixo tem como única solução

(0,−3,−4): x + y − z = 1

2x − y + z = −1

2x + 2y + z = 2

(1.3)

Sistema Possível e Indeterminado

Dizemos que um sistema é possível e indeterminado se ele possui in-

�nitas soluções.

ii


ii

ii


Exemplo 1.1.7. O seguinte sistema é possível e indeterminado:2x+ 7w = −2

4y − 3w = 4

6z + 5w = 48

(1.4)

Observe que podemos colocar todas as outras variáveis em função da

variável w, logo o conjunto solução seria dado pela quádrupla

(−2−7w2

, 4+3w4, 48−5w

6, w) ∈ R4. Para tudo �car bonitinho poderíamos

colocar w = 12t e o nosso conjunto solução (continua o mesmo, só

que agora com uma nova parametrização) é dado por

(−1− 42t, 1 + 9t, 8− 10t, 12t) ∈ R4. Neste caso, como existe uma

única variável livre -que é a variavel w, dizemos que este sistema pos-

sui grau de liberdade igual a 1. Num sistema possível e indeterminado

de m equações, se conseguirmos colocar todas as equações em função

de r variáveis, dizemos que esse sistema possui, r graus de liberdade.

1.1.3 Interpretação Geométrica

Sabemos da geometria analítica que uma equação r1 : ax+ by+ c = 0

representa um reta no plano cartesiano. Portanto estudar a solução de

um sistema de duas equações e duas variáveis é o mesmo que estudar

as possíveis interseções de duas retas no plano. Dado o sistema:

S1 :

{r1 : a1x+ b1y = c1

r2 : a2x+ b2y = c2(1.5)

1. Temos duas retas no plano cartesiano. Assim o sistemas S1 é

impossível se, e só se, as retas r1 e r2 são paralelas.

ii


ii

ii


2. S1 ser possível e determinado quer dizer que ele tem uma única

solução, ou seja, as retas r1 e r2 se encontram num único ponto.

Isto é, as retas são transversais.

3. S1 é possível e indeterminado se, e só se, possui in�nitas soluções,

se e só se, as retas se intersectam ini�nitas vezes. Mas se duas

retas possuem dois pontos em comum, elas são coincidentes. Por-

tanto neste caso r1 e r2 são coincidentes.

Observação 1.1.8. Portanto estudar o sistema:

S

a11x1 +a12x2 + · · · +a1nxn = b1

a21x1 +a22x2 + · · · +a2nxn = b2...

.... . .

...


É o mesmo que estudar a interseção de m hiperplanos no espaço Rn.

Exercício 2. Faça um estudo geométrico das interseções para o sis-

tema:

S

a11x1 +a12x2 +a13x3 = b1

a21x1 +a22x2 +a23x3 = b2

a31x1 +a32x2 +a33x3 = b3

(1.6)

(Dica: Não desanime são de fato 8 casos.)

Geometricamente um sistema indeterminado em Rn, AX = B rep-

resenta uma in�nidade de pontos na interseção de um conjunto de

hiperplanos. suponhamos que é conhecido um ponto da interseção,

X0. Então A(X −X0) = 0 representa um subespaço vetorial de modo

que todos os vetores são combinação linear de um certo número de ve-

tores v1, v2, . . . , vk e, portanto, a solução geral do sistema é da forma

X = X0 + a1v1 + a2v2 + · · ·+ akvk

ii


ii

ii


1.1.4 Eliminação Gaussiana

Até agora �zemos um estudo qualitativo dos sistemas lineares, quanto

as suas soluções. Mas não aprendemos ainda a resolver de fato um

sistema. Poderíamos nos perguntar antes disso se é factível resolver o

sistema.

1.1.5 Matriz Escalonada por Linhas

Novamente consideremos o sistema S:

S

a11x1 +a12x2 + · · · +a1nxn = b1

a21x1 +a22x2 + · · · +a2nxn = b2...

.... . .

...


Chamamos de matriz aumentada relativa ao sistema S a matriz dada

por:

Am×n =

a11 a12 · · · a1n b1

a21 a22 · · · a2n b2...

.... . .

...

am1 am2 · · · amn bm

,

Exercício 3. Escreva a matriz aumentada dos exemplos 1.1.6, 1.1.7

e do exercício 1.

Vamos agora fazer uma pequena digressão. Quando aprendemos

a resolver sistemas lá no colegial, nos é ensinado dois métodos: elim-

inação e susbstituição. Que na verdade são duas faces do mesmo

método. Assim, no método da eliminação tentamos fazer uma série

ii


ii

ii


de operações de tal forma a "nos livrarmos"de um certo número de

variáveis, chegando assim num sistema novo. E de maneira tal que

seja fácil encontrar as soluções do novo sistema.

Existem três operações permitidas, que usamos para resolver um sis-

tema:

1. multiplicar toda uma equação por uma constante real não nula;

2. trocar duas equações de posição;

3. substituir a equação que está na posição r, pela equação de

posição r mais c vezes a linha s, com c uma constante real não

nula e r 6= s.

Essas operações são chamadas de operações elementares. Dois sis-

temas são equivalentes se podemos transformar um no outro através

de operações elementares.

Exercício 4. Mostre que dois sistemas equivalentes possuem o mesmo

conjunto solução.

Note que as linhas da matriz correspondem as equações de um

sistema, portanto podemos por analogia de�nir operações elementares

para uma matriz da seguinte forma:

1. multiplicar toda uma linha por um constantereal não nula;

2. trocar duas linhas de posição;

3. substituir a linha r, pela linha r mais c vezes a linha s,com c

uma constante real não nula.

Dizemos que uma matriz está na forma escalonada por linhas se:

ii


ii

ii


1. o primeiro elemento não nulo de uma linha qualquer( que não

seja nula) é 1. Este termo é chamado de lider ou pivô;

2. o pivô de uma linha inferior �ca estritamente a direita do pivô

da linha superior;

3. as linha formadas só de zeros serão agrupadas nas linhas inferi-

ores da matriz.

Observe que no exemplo anterior o que �zemos foi justamente colocá-la

na forma escalonada. E do que consiste o método da eliminação Gaus-

siana? O método da eliminação Gaussiana para resolver um sistema,

consiste de um processo algoritmico para colocar a matriz aumentada

na sua forma escalonada e após isso utilizarmos substituição reversa

para encontrar as suas soluções.

Podemos resumir o algoritmo da seguinte maneira:

1. se todos os elementos da 1a coluna são nulos passaremos para a

próxima coluna que possui pelo menos um elemento não nulo. E

cosideraremos essa a nossa primeira coluna;

2. se a11 = 0, troque a primeira linha com alguma linha cujo o

primeiro elemento é não nulo;

3. se a11 6= 0 multipleque toda a linha por 1a11

, para obter um termo

lider (ou pivô);

4. elimine todos os termos não nulos da 1a coluna, usando operações

elementares;

5. ignore a primeira linha e a primeira coluna e repita o processo

para a submatriz obtida.

ii


ii

ii


Exemplo 1.1.9. Resolva o seguinte sistema utilizando eliminação

Gaussiana: x+ 2y + 3z = 1

4x+ 5y + 7z = 2

5x+ 3y + 2z = 3

(1.7)

Seguindo os passos do algoritmo temos que: 1 2 3 1

4 5 7 2

5 3 2 3

L2−4L1=

1 2 3 1

0 −3 −5 −6

5 3 2 3

L3−5L1=

1 2 3 1

0 −3 −5 −6

0 −7 −13 −2

−13·L2

=

1 2 3 1

0 1 53

2

0 −7 −13 −2

7L2+L3=

1 2 3 1

0 1 53

2

0 0 −43

12

− 43L3

=

1 2 3 1

0 1 53

2

0 0 1 −9

Portanto temos o sistemas equivalente:

x+ 2y + 3z = 1

y + 53z = 2

z = −9

(1.8)

Agora fazendo substituição reversa, da terceira equação temos que z =

−9, e pela segunda equação, y − 15 = 2 ⇒ y = 17 . E da primeira,

x + 2 · 17 + 3 · −9 = 1 ⇒ x = −6. Ou seja, o sistema tem solução

(−6, 17,−9).

Exercício 5. Utilizando eliminação Gaussiana; resolva os sistemas

dos exemplos 1.1.5, 1.1.7 e do exercício 1.

ii


ii

ii

1.2 Sistemas de Equações Lineares em Z 15

1.1.6 Complemento

Chamamos Eim×mde matriz elementar se ela foi obtida da matriz

identidade Im, onde aplicamos uma única operação elementar. As-

sim, realizar uma operação elementar numa matriz Am×n é o mesmo

que multiplicar A por Ei onde Ei é a matriz elementar apropriada.

Portanto se S e S ′ são dois sistemas equivalentes, A e A′ suas ma-

trizes aumentadas, respectivamente. Então segue que A = P ·A′ ondeP = E1 · E2 · E3 · · ·Er e Ei é elementar para todo i.

Exercício 6. Mostre que Det(P ) 6= 0.

1.2 Sistemas de Equações Lineares em Z

Até o momento desenvolvemos a teoria de sistemas lineares para coe-

�cientes e soluções reais. Mas como bem ilustram os exemplos 1.1.3 e

1.1.4 no começo desse capítulo e tantos outros nas situações da vida

real, queremos que os coe�cientes, bem como as suas soluções sejam

inteiras. Isto é, consideraremos o sistema

S

a11x1 +a12x2 + · · · +a1nxn = b1

a21x1 +a22x2 + · · · +a2nxn = b2...

.... . .

...


(1.9)

Só que agora faremos uma hipótese adcional de que todos os coe-

�cientes sejam inteiros, ou seja, aij ∈ Z. E se a n-upla (r1, r2, · · · , rn)

é solução de S, então (r1, r2, · · · , rn) ∈ Zn.

Observação 1.2.1. Agora pare e pense comigo: se S é um sistema

possível e determinado ; logo terá uma única solução. Mesmo que

ii


ii

ii


S tenha todos os coe�cientes inteiros, qual a "chance"dessa única

solução ser inteira? Provavelmente sua intuição dirá que é muito pe-

quena. Pois estamos fazendo uma restrição muito forte no espaço das

possíveis soluções. Por este motivo, estudaremos aqui os sistemas in-

determinados. Pois esses, quando possuem uma in�nidade de soluções

reais e destas queremos determinar quais são as inteiras.

Antes de tentar resolver um sistema, vamos resolver a equação:

ax+ by = c com a, b, c ∈ Z. (1.10)

1.2.1 Um Pouco de Aritmética dos Inteiros

Dizemos que a divide b ou a é um divisor de b em Z, se existe c ∈ Ztal que b = a · c, denotamos a | b. Dados a, b, d ∈ Z, diremos que d é

um divisor comum de a e b se d | a e d | b. Chamamos d de máximo

divisor comum se:

1. d | a e d | b;

2. Para todo c tal que c | a e c | b, então c | d.

E denotaremos d = mdc(a, b).

Teorema 1.2.2 (Divisão Euclidiana). Dados a, b inteiros positivos,

b > 0 existem dois únicos q e r inteiros tais que

a = bq + r com 0 ≤ r < b (r = 0⇔ b | a). (1.11)

Chamamos q de quociente e r de resto.

ii


ii

ii


Demonstração. Existência

Considere C o conjunto formado pelos números inteiros positivos da

forma a, a − b, a − 2b, a − 3b, ..., pelo princípio da boa ordenação C

possui um menor elemento. Denotemos r = a− qb o menor elemento

de C. Observe que 0 ≤ r e r < b, pois se r > b teríamos que a−qb > b

e então a− (q+1)b > 0 e de�nindo r′ = a− (q+1)b seria um elemento

de C e menor do que r, contrariando a minimalidade desse elemento.

Unicidade

Suponha que existam q1, r1 e q2, r2 tais que a = bq1 + r1 e a = bq2 + r2,

com 0 ≤ r1 < b e 0 ≤ r2 < b. Assim temos bq1 + r1 = bq2 + r2 ⇒(q1 − q2)b = r2 − r1 ⇒ b | r2 − r1 ⇒ b < r2 − r1, mas isso é absurdo a

menos que r2 − r1 = 0 o que implica que r2 = r1.

Consequentemente (q1 − q2)b = 0 e como estamos supondo b > 0,

obtemos que q1 = q2. E portanto a unicidade.

Exercício 7. Veri�que que a | b e b | a se, e só se, |a| = |b|. Esse

é um fato muito útil quando queremos mostrar que dois números são

iguais a menos do sinal.

Lema 1.2.3 (Lema de Euclides). Se a, b, n ∈ Z, então mdc(a, b) =

mdc(a, b− na).

Demonstração. Denotaremos d = mdc(a, b) e e = mdc(a, b − na). E

para mostrar a igualdade usaremos o exercício 7. Por de�nição d | ae d | b, logo d | a e d | b − na, então d | e. Por outro lado e | a e

e | b− na o que implica que e | a e e | b, ou seja, e | d. Pelo exercício

7 temos que d = e.

Teorema 1.2.4 (Bachet-Bezout). Sejam a, b ∈ Z. Se d = mdc(a, b)

então existem m,n ∈ Z tais que am+ bn = d.

ii


ii

ii


Demonstração. Considere o conjunto I(a, b) = {ax + by | x, y ∈ Z}das conbinações lineares inteiras de a e b. Seja u = ax0 + by0 o

menor elemento positivo de I(a, b). A�rmamos que u divide todos os

elementos de I(a, b). Dado um elemento qualquer v = ax1 + by1 ∈I(a, b). Pela divisão Euclidiana temos que existem q e r tais que

v = uq + r com 0 ≤ r < d. Pelas hipóteses feitas

r = v−uq = ax1+by1−q(ax0+by0) = a(x1−qx0)+b(y1−qy0) ∈ I(a, b).

Nesse caso teríamos que r < u, contrariando a minimalidade de u.

Assim r = 0 e u | v. Observe que a, b ∈ I(a, b), logo u | a e u | b epela de�nição u | mdc(a, b). E como mdc(a, b) | a, mdc(a, b) | b entãomdc(a, b) | ax0 + by0 para quaisquer x0, y0, ou seja, mdc(a, b) | u. E

pelo exercício 7, mdc(a, b) = u. Mais explicitamente, d = mdc(a, b) =

u = ax0 + by0 com x0, y0 ∈ Z.

Corolário 1.2.5. Sejam a, b ∈ Z. A equação

ax+ by = c (1.12)

admite solução inteira se, e só se, mdc(a, b) | c.

Teorema 1.2.6 (Algoritmo de Euclides). Sejam a, b inteiros positivos,

com b 6= 0 podemos aplicar a divisão euclidiana sucessivamente

a = bq1 + r1, 0 ≤ r1 < b

b = r1q2 + r2, 0 ≤ r2 < r1

r1 = r2q3 + r3, 0 ≤ r3 < r2

r2 = r3q4 + r4, 0 ≤ r4 < r3...

rn−2 = qnrn−1 + rn

rn−1 = qn+1rn + 0

(1.13)

E o mdc(a, b) = rn o último resto não nulo.

ii


ii

ii


Demonstração. Observe que pela divisão euclidiana esses restos vão

�cando cada vez menores, como estamos trantado com inteiros pos-

itivos,esse conjunto de restos possui um menor elementor. Ou seja,

o algoritmo vai parar em algum momento. Pelo lema de Euclides

temos que mdc(a, b) = mdc(b, a − bq1) que podemos reescrever como

mdc(b, r1). Novamente pelo Lema de Euclidesmdc(b, r1) = mdc(r1, b−r1q2) = mdc(r1, r2) e assim sucessivamente até mdc(a, b) = mdc(b, r1)

= mdc(r1, r2) = . . . = mdc(rn−1, rn) = mdc(rn, 0) = rn

Exemplo 1.2.7. Encontre o mdc(372, 162) = d utilizando o algoritmo

de Euclides e depois encontre m,n ∈ Z tais que d = 772m+ 162n.

Resolução:Aplicando o algoritmo temos que:

372 = 162 · 2 + 48

162 = 48 · 3 + 18

48 = 18 · 2 + 12

18 = 12 · 1 + 6

12 = 6 · 2 + 0

Portanto mdc(372, 162) = 6. E das igualdades acima podemos, obter

os inteiros m,n:

6 = 18 − 12 · 16 = 18 − (48− 18 · 2) = 3 · 18 − 48

6 = 3 · (162 − 48 · 3)− 48 = 3 · 162 − 48 · 10

6 = 3 · 162 − 10(372− 2 · 162) = 23 · 162 − 10 · 372

Da última linha vimos que 6 = 23 · 162− 10 · 372.

ii


ii

ii


Exercício 8. Faça o mesmo para os pares:

a) 542, 234 e) 48762, 176

b) 9652, 252 f) 42516, 97421

c) 24573, 1387 g) 8374, 24517

d) 4276, 1234 h) 35262, 12753

Do corolário 1.2.5 aprendemos que a equação ax + by = c possui

solução se, e só se, mdc(a, b) | c. Do Algoritmo de Euclides 1.2.6

aprendemos a encontrar pelo menos uma solução para essa equação.

Vamos agora determinar todas.

Teorema 1.2.8. Dada a equação ax + by = c com mdc(a, b) | ce (x0, y0) uma solução particular, então toda solução inteira é dada

parametricamente por:

x = x0 +(bd

)t

y = y0 −(ad

)t

(1.14)

Demonstração. Seja (x, y) uma solução inteira de ax+by = c diferente

de (x0, y0) então temos que

ax+ by = c

ax0 + by0 = c(1.15)

subtraindo uma equação da outra e reagrupando os termos a(x−x0) =

b(y0− y). Agora dividimos toda a equação por d = mdc(a, b). E assim

a

d(x− x0) =

b

d(y0 − y) (1.16)

Lembre que mdc(ad, bd) = 1, portanto b

d| x − x0 por de�nição existe

t ∈ Z tal que x− x0 = bdt⇒ x = x0 + b

dt.

ii


ii

ii


Substituindo em ax+ by = c encontramos que a(x0 + bdt) + by = c⇒

ax0 + abdt + by = c. Como ax0 = c − by0 e c − by0 + ab

dt + by = c,

simpli�cando por b e arrumando os termos y = y0 − adt.

Exercício 9. Para todas as equações abaixo determine quais têm solu-

ções nos inteiros. E nas que possuem, exiba a sua forma paramétrica:

a) 2x− 3y = 7 c) 372x+ 162y = 24

b) 22x− 55y = 13 d) 437x− 281y = 17

e) 6x− 10y + 15z = 7

(Dica: Faça w = 2y − 3z e resolva 6x − 5w = 7 achando as soluções

em termos de um parâmetro t, após isso resolva em relação a y, z. E

em função de um outro novo parâmetro s.)

1.2.2 A Forma Algoritmica

Nesta seção pretendemos juntar o que já foi feito nas outra seções

isto é, sistemas de equações lineares reais e aritmética, para resolver

um sistema de equações lineares nos inteiros. Como vimos; o método

adotado para resolver os sistemas nos reais foi a eliminação Gaussiana.

Mostraremos aqui um método análogo à eliminação Gaussiana, mas

com as devidas restrições para permanecermos com nossas soluções

nos inteiros. Chamaremos o método de eliminação inteira.

Para explicar o método da eliminação Gaussiana �zemos os seguinte

passos: associamos ao sistema sua forma matricial, de�nimos o que

é uma matriz escalonada, de�nimos o que são operações elementares.

Por �m mostramos um algoritmo de como colocar a matriz do sistema

na forma escalonada por linhas. E que é razoavelmente fácil obter

as soluções desse novo sistema( que é equivalente ao primeiro) por

ii


ii

ii


substituição reversa.

Seguiremos os mesmo passos aqui. A forma de associar a um sistema

sua versão matricial é a mesma feita em R. Agora vamos de�nir o que

é uma matriz estar na forma inteira escalonada por linhas. Vamos

supor que Am×n é uma matriz com todas as entradas em Z.

De�nição 1.2.9. Diremos que Am×n está na forma inteira escalonada

por linhas se:

1. as linhas formadas só de zeros serão agrupadas nas linhas infe-

riores da matriz;

2. o primeiro elemento não nulo de cada linha estará estritamente

à direita do primeiro elemento não nulo da linha superior.

Observação: Este primeiro elemento não nulo de cada linha também

será chamado de termo líder ou pivô, como no caso anterior, com a

única diferença que não exigeremos que este seja igual a 1. Poderá

ser qualquer inteiro positivo. E esta será a única diferença entre uma

matriz escalonada por linha e uma matriz na forma inteira escalonada

por linha.

Diremos que uma operação numa dada matriz é unimodular se ela

é da seguinte forma:

1. trocamos duas linhas da matriz de posição;

2. multiplicamos uma linha por −1;

3. somamos duas linhas.

Se uma matriz está associada a uma operação unimodular, essa matriz

será dita matriz unimodular.

ii


ii

ii


Exercício 10. Mostre que o determinante de qualquer operação uni-

modular é ±1.(Dica: por de�nição, uma matriz unimodular é o mesmo

que aplicar a operação unimodular associada a matriz identidade. Uti-

lize a de�nição de determinantes).

Exercício 11. Mostre que é possível trocar duas linhas de posição uti-

lizando apenas as operações 2 e 3 repetidas vezes.( Ou seja, poderíamos

desconsiderar a primeira operação, mas a adotamos por �ns práticos.)

Assim o nosso método da eliminação inteira consiste em realizar

numa matriz A de entradas inteiras os mesmos passos que descrevemos

em ??, mas agora com as operações unimodulares e o pivô de cada

linha não precisa ser um, pode ser qualquer inteiro positvo.

Proposição 1.2.10. É sempre possível através de operações unimod-

ulares transformar a matriza1

a2...

an

na matriz

d

0...

0

(1.17)

onde d é o mdc(a1, a2, · · · , an).

Demonstração. Façamos o seguinte processo:

1. seja aj o elemento de menor valor absoluto não nulo dentre

a1, a2, · · · , an.

2. Para cada i 6= j, aplique o algoritmo da dvisão para obter

ai = kiaj + ri com o ≤ |ri| < |aj|.

ii


ii

ii


3. Para cada i 6= j, faça ki vezes a coluna j e subtraia do coluna i.

Observe que do algoritmo de Euclidesmdc(a1, a2) = mdc(a1−a2q1, a2)= mdc(r1, a2) = mdc(r1, a2−r1q2) = mdc(r1, r2) = . . . = mdc(rn−1, rn)

= mdc(rn, 0) = rn ou seja, d = mdc(a, b) é justamente o último resto

não nulo. Agora de�na o

mdc(a1, a2, . . . , an−1, an) = mdc(a1, a2, . . . , an−2,mdc(an−1, an))

Assim temos que

mdc(a1, a2, . . . , an−1, an) = mdc(a1, a2, . . . , an−2,mdc(dn, 0))

= mdc(a1, a2, . . . , an−2, rn, 0)

Agora escolha qualquer outro par e repita. A o �m so restará um

único elemento não nulo, e este pelo Algoritmo de Euclides é o mdc

dos elementos a1, a2, . . . , an. Perceba que os passos feitos no processo

descrito acima são os mesmos do Algoritmo de Euclides, portanto esse

último elemento nulo também é mdc dos termos a1, a2, . . . , an.

Observação 1.2.11. O leitor perceberá que em vez de manejar com

a matriz associada ao sistema, terá que manejar com a matriz trans-

posta. Isto se deve ao fato de termos construido toda a nossa teoria

para matrizes escalonadas por linhas. Poderíamos ter desenvolvido

toda a teoria para matrizes escalonadas por colunas, por ser bastante

popular, pelo hábito e gosto, preferimos manter a teoria para matrizes

escalonadas por linhas.

Pelo processo de eliminação inteira, podemos colocar a matriz At

na sua forma inteira escalonada por linhas que denotaremos por S.

Colocar A na sua forma escalonada é o mesmo que multiplicá-la pela

ii


ii

ii


esquerda por matrizes unimodulares. Denotaremos por U a matriz

dada pelo produto dessa matrizes. Portanto U ·At = S ⇒ A ·U t = St

e denote Z = (U t)−1 ·X.

Note que

A ·X = B ⇔ A(U t)(U t)−1X = B ⇔ St · Z = B.

Lembre que U é um produto de matrizes unimodulares, as quais têm

determinantes iguais a ±1. Logo o determinate de U também será

±1.

A�rmação 1.2.12. A matriz (U t)−1 tem todas as entradas inteiras.

Demonstração. Sabemos da teoria dos determinates que a inversa de

uma matriz quadrada qualquer M é dada por M−1 =adj(M)

det(M). Na

qual adj(M) é a matriz adjunta de M .

Consequentemente

(U t)−1 =adj(U t)

det(U t)= ±adj(U t).

A matriz adjunta tem como cada uma das suas entradas um subdeter-

minate. Determinantes são polinômios a coe�cientes inteiros. Assim,

se cada entrada da matriz é inteira, cada subdeterminante também

será inteiro. Ou seja, adj(ut) é uma matriz em que uij ∈ Z. Isso im-

plica que (U t)−1 = ±adj(U t) é uma matriz de entradas inteiras.

A�rmação 1.2.13. O Sistema St ·Z = B tem soluções inteiras se, e

somente se, A ·X = B tem soluções inteiras.

Demonstração. Pois Z0 é solução do sistema St · Z = B se, e só se,

X0 = U t · Z0. x0j =∑uijz0i e como a soma e o produto de números

inteiros é ainda inteiro, e os uij são inteiro. Z0 tem todas as entradas

inteiras se, e so se, X0 tem todas as entradas inteiras.

ii


ii

ii


O que acabamos de explanar e provar pode ser sumarizado no

seguinte teorema:

Teorema 1.2.14. Para resolver o sistema A ·X = B, usamos oper-

ações unimodulares em A para transformá-lo na sua forma escalonada

por linhas St. Assim AX = B tem solução em Z se, e somente se,

StZ = B tem solução em Z. E as soluções de AX = B, são da forma

X = U tZ.

Exemplo 1.2.15. Encontre todas as soluções inteiras do sistema

5x+ 6y + 8z = 1

6x− 11y + 7z = 9

Utilizando o método da eliminação inteira 5 6

6 11

8 7

∣∣∣∣∣∣∣1 0 0

0 1 0

0 0 1

→ 5 6

1 −17

3 1

∣∣∣∣∣∣∣1 0 0

−1 1 0

−1 0 1

→

1 −17

0 91

0 52

∣∣∣∣∣∣∣−1 1 0

6 −5 0

2 −3 1

→ 1 −17

0 −13

0 52

∣∣∣∣∣∣∣−1 1 0

2 1 −2

2 −3 1

→

1 −17

0 13

0 0

∣∣∣∣∣∣∣−1 1 0

−2 −1 2

10 1 −7

A equação St · Z = B é

[1 0 0

−17 13 0

] z1

z2

z3

=

[1

9

]

ii


ii

ii

1.3 Interpretação geométrica 27

ou seja, z1 = 1 e −17z1 + 13z2 = 9 ⇐ z2 = 2 e z3 pode ser qualquer

valor inteiro o qual denotaresmos por z3 = t ∈ Z. Por conseguinte,

Z0 =

1

2

t

e

x

y

z

= St · Z =

−1 −2 10

1 −1 1

0 2 −7

· 1

2

t

=

−5 + 10t

−1 + t

4− 7tt

Isto é, todas as soluções paramétricas são dadas por

x = −5 + 10t

y = −1 + t

z = 4− 7t

e t ∈ Z

1.3 Interpretação geométrica

Um sistema de equações diofantinas lineares, bem como um sistema

linear, possuindo k equações em n incógnitas pode ser representado

matricialmente da seguinte forma:

AX = B

Em que A = (aij)k×n é a matriz dos coe�cientes das equações, X =

(x1, . . . , xn)t é a matriz das incógnitas e B = (b1, . . . , bk)t a matriz dos

termos independentes.

Claramente, se X0 é uma solução particular do sistema, isto é, um

vetor tal que AX0 = B, podemos subtrair as equações e obter:

A(X −X0) = 0

ii


ii

ii


que, a menos de mudança de variáveis é um reticulado em Rn. De

fato, considere Y = X − X0, o sistema AY = 0 tem como solução

um reticulado (de posto r = posto(A) ≤ k) e portanto possui uma

base v1, v2, . . . , vn−r. Assim, a solução geral do sistema de equações

diofantinas é

X = X0 + a1v1 + a2v2 = · · ·+ an−rvn−r.

Esta observação generaliza a ideia de que numa reta conhecido um

ponto inteiro encontramos todos os outros usando um vetor diretor

primitivo (base do reticulado). Nesse capítulo temos discutido quando

o sistema possui ou não solução inteira e como determiná-las algorit-

mamente.

Problemas

1. Você possui muitos palitos com 6cm e 7cm de comprimento.

Qual o número mínimo de palitos que você precisa utilizar para

fazer uma �la de palitos com comprimento total de 2 metros?

2. (Problema proposto por Mahavira, 850) 5 pilhas de frutas mais

duas frutas foram divididas (igualmente) entre 9 viajantes; seis

pilhas mais quatro foram divididas por 8; quatro pilhas mais 1

foram divididas por 7. Determine o menor número possível de

frutas em cada pilha.

3. (Problema proposto por Bhaskara 1; Século VI) Encontre o

menor número natural que deixa resto 1 quando dividido por

2,3,4,5,6 mas é exatamente divisível por 7.

ii


ii

ii

1.3 Interpretação geométrica 29

4. (Proposto por Euler) Uma pessoa comprou cavalos e bois. Foram

pagos 31 escudos por cavalo e 20 escudos por boi e sabe-se que

todos os cavalos custaram 7 escudos a mais do que todos os

bois.Quantos cavalos e quantos bois foram comprados?

5. (Problema do século XVI) Um total de 41 pessoas entre homens,

mulheres e crianças foram a um banquete e juntos gastaram 40

patacas. Cada homem pagou 4 patacas, cada mulher 3 patacas

e cada criança um terço de pataca. Quantos homens, quantas

mulheres e quantas crianças havia no banquete?

6. Refaça o exercício 9 utilizando o algoritmo aprendido nesta seção.

7. Encontre as soluções inteiras das equações:

(a) 16x+ 12y − 27z = 37

(b) 3x+ 5y + 7z = 11

(c) −2x+ 17y − 19z = −1

8. Encontre as soluções inteiras dos sistemas:

(a)2x+ y − z = 1

3x− y + z = 4

(b)5x+ 3y − 2z + 4w = 5

2x− 4y + 3z − 5w = −9

ii


ii

ii


ii


ii

ii

CAPÍTULO 2

O Problema do Troco de Frobênius

2.1 Introdução.

Imagine que nós temos um caixa eletrônico que só tem cédulas de 2

reais e de 5 reais, e dispõe de in�nitas notas desses valores. Então,

naturalmente já sabemos que existem quantias inteiras que não po-

dem ser sacados nessa máquina. Por exemplo, não se consegue sacar 1

real, nem 3 reais. Daí poderíamos pensar na questão �será que existe

um valor inteiro tal que a partir dele todo saque de valores inteiros

pode ser realizado?�. Note que podemos sacar 4 reais, 5, 6 e várias

outras quantias. Mas, quantos mais podemos sacar? Será que de fato

existe esse valor inteiro mínimo de saque? Eis o Problema do Troco de

Frobênius.

31

ii


ii

ii

32 O Problema do Troco de Frobênius

O problema do troco de Frobênius, ou simplesmente problema de

Frobênius, em sua formulação geral é o seguinte: Considere que exis-

tem cédulas das seguintes denominações: a1, a2, ..., an, com

mdc(a1, a2, · · · , a0) = 1. Qual o menor valor que não pode ser pago

utilizando tais cédulas? Matematicamente, podemos traduzí-lo da

seguinte forma:

Sejam a1, a2, · · · , an inteiros positivos com mdc(a1, a2, · · · , an) = 1.

Determinar o menor inteiro positivo g = g(a1, a2, ..., an) tal que todo

inteiro positivo d ≥ g pode ser reescrito como combinação inteira pos-

itiva de a1, a2, ..., an, isto é, a equação

a1x1 + a2x2 + · · ·+ anxn = d (2.1)

possui solução não negativa, isto é, xi ≥ 0 para i = 1, 2, ..., n.

Nesses termos, a pergunta que tínhamos feito anteriormente se traduz

da seguinte maneira: será que existe tal g? Frobênius (1849-1917)

discutiu esse problema em suas exposições no �m do século 19, mas

não chegou a publicar algum resultado sobre isso. A seção seguinte

expõe um resultado que legitimiza o sentido de procurar por tal g.

2.1.1 Boa Posição.

A próxima proposição atesta que o conjunto dos naturais que não

podem ser representados como combinação linear de uma lista �nita e

pré-de�nida de números naturais é �nito, isto é, o problema do troco

de Frobênius está bem posto.

Proposição 2.1.1. Se mdc(a1, · · · , an) = 1, então existe um inteiro

N tal que todo inteiro s ≥ N pode ser escrito da forma a1x1+· · ·+anxncom xi's não-negativos para todo i ∈ {1, · · · , n}.

ii


ii

ii

2.1 Introdução. 33

Demonstração. Podemos provar por indução em n (com ajuda do

Lema de Bezout) que se mdc(a1, · · · , an) = 1, então existemm1, · · · ,mn

tais que m1a1 + · · · + mnan = 1. Sem perda de generalidade, pode-

mos supor que os l primeiros inteiros mi são não-negativos e os n− lrestantes são negativos. Considere P :=

∑li=1miai e −Q := 1 − P .

Então, P e Q pertencem ao conjunto W := {s | ∃r1, · · · , rn ≥ 0 s =

a1r1 + · · · + anrn} (note que de�nimos W como sendo o conjunto de

inteiros que podem ser escritos na forma que nos interessa). Usando

o algoritmo de Euclides da divisão, temos que todo k ≥ 0 pode ser

escrito da forma ha1 + k′ com 0 ≤ k′ < a1. Portanto,

(a1 − 1)Q+ k = (a1 − 1)Q+ ha1 + k′

= (a1 − 1)Q+ ha1 + k′(P −Q) = (a1 − 1)Q+ ha1 + k′P − k′Q

= (a1 − k′ − 1)Q+ ha1 + k′P com a1 − k′ − 1 ≥ 0, h ≥ 0, k′ ≥ 0.

Como a1, P e Q pertencem a W , então para quaisquer c, d, e ≥ 0

temos que ca1 + dP + eQ ∈ W . Logo, provamos anteriormente que

para todo k ≥ 0 temos que (a1−1)Q+k ∈ W , isto é, qualquer número

maior ou igual a (a1−1)Q pode ser escrito da forma a1x1 + · · ·+anxn

com xi's não-negativos.

Este último resultado atesta que sempre existe uma cota que a par-

tir da qual sempre temos solução inteira não-negativa para a equação.

Porém, esta cota (que era (a1 − 1)Q no caso da demonstração acima)

nem sempre é ótima. Portanto, apesar de sempre existir uma cota,

muitas vezes não é simples encontrar a cota ótima g. Em vários proble-

mas, encontramos cotas que, apesar de não serem ótimas, são bastante

satisfatórias num certo sentido. Por exemplo, dizemos que r é uma

cota relativamente ótima para o problema de Frobênius a1x1 + · · · +

ii


ii

ii


anxn = d se r é uma cota e existe uma classe de problemas sobre a

qual r é ótima. Apesar de não resolvermos o problema de Frobênius

geral, apresentaremos uma cota relativamente ótima para o mesmo.

2.2 O Caso Bidimensional.

Vamos mostrar nesta seção que para todo a e b inteiros positivos co-

primos, então g(a, b) = ab− a− b+ 1.

Teorema 2.2.1. Sejam a, b, c ∈ Z números inteiros positivos, com

mdc(b, c) = 1, e suponha que a > bc− b− c. Então a equação

bx+ cy = a

possui (pelo menos) uma solução inteira não negativa. Ou seja, (m,n) ∈Z e m,n ≥ 0. Além disso, bx + cy = bc − b − c não possui solução

inteira não negativa. Ou seja,

g(b, c) = bc− b− c+ 1

Demonstração. Observe que a condição da existência de solução em

inteiros não negativos é equivalente a existência de solução (m,n) ∈ Z2

satisfazendo m + 1 > 0 e n + 1 > 0. Se somamos b + c em ambos os

lados da equação original obtemos:

b(x+ 1) + c(y + 1) = a+ b+ c

e agora exigimos que x = x+ 1 > 0 e y = y + 1 > 0 na equação

bx+ cy = d (2.2)

na qual d = a+ b+ c.

Como mdc(b, c) = 1, o vetor diretor v = (c,−b) é um vetor diretor

ii


ii

ii

2.2 O Caso Bidimensional. 35

inteiro primitivo da reta 2.2. Assim, pelo Teorema 1.2.8, a distância

entre dois pontos inteiros consecutivos na reta 2.2 é ||v|| =√b2 + c2.

Observamos que os pontos de interseção da reta com os eixos coordena-

dos x e y são (0, dc) e (d

b, 0) respectivamente, e os mesmos encontram-se

a uma distância√

d2

c2+ d2

b2= d

bc

√b2 + c2.

Claramente, se

√b2 + c2 >

√d2

c2+d2

b2=

d

bc

√b2 + c2 (2.3)

então a equação 2.2 possuirá algum ponto com x > 0 e y > 0.

Mas a desigualdade citada é equivalente a

d > bc⇒ a > bc− b− c.

Agora só nos resta mostrar que não se pode escrever ab−a−b da forma

ax+by com x e y não-negativos, segue então que g(a, b) = ab−a−b+1.

Suponha que bc − b − c é representável como bx + cy. Então, b(x +

1) + c(y+ 1) = bc. Daí, temos que b|(y+ 1) e c|(x+ 1), já que b e c são

coprimos. Portanto, existem r, s ≥ 1 tal que x + 1 = rc e y + 1 = sb.

Portanto, bcr + bcs = bc, ou seja, r + s = 1, um absurdo.

2.2.1 Corolário Sobre o Caso Geral.

Raczunas e Chrz�astowski-Wachtel no artigo A diophantine problem

of Frobenius in terms of the least common multiple descrevem uma

classe de problemas com sua respectiva cota ótima. Nesta seção, va-

mos mostrar como o caso bidimensional nos ajuda a deduzir tal cota.

ii


ii

ii


Como visto na seção anterior, dados a e b inteiros positivos copri-

mos, o último natural que não pode ser escrito da forma ax+ by, com

x e y inteiros não-negativos, é ab − a − b. Agora descreveremos uma

classe de problemas de Frobênius geral que atestam que a cota gerada

pelo problema do McNuggets (ver exercício 4) é relativamente ótima.

Considere n ≥ 1 e A = {a1, · · · , an+1} um conjunto de inteiros pos-

itivos dois a dois coprimos. Para cada i ∈ {1, · · · , n + 1}, considerebi :=

∏j 6=i

aj. Então o maior inteiro que não pode ser escrito da forma

n+1∑i=1

bixi, com xi ≥ 0 ∀i, é nn+1∏i=1

ai −n+1∑i=1

bi.

Exemplo 1 Primeiramente, vamos mostrar por indução que todo

número a partir de nn+1∏i=1

ai −n+1∑i=1

bi + 1 pode ser escrito de tal forma.

Para n = 1, temos o problema bidimensional. Suponha que dado qual-

quer A = {a1, · · · , an+1} desta forma, o maior número que não pode

ser escrito da forman+1∑i=1

bixi, com xi ≥ 0 ∀i, é nn+1∏i=1

ai −n+1∑i=1

bi. Con-

sidere C = {c1, · · · , cn+2} um conjunto de inteiros positivos dois a dois

coprimos e, para cada i ∈ {1, · · · , n + 2}, di :=∏j 6=i

aj, e o problema

de Frobênius

d1x1 + · · ·+ dn+2xn+2 = f

Note que mdc(d1, · · · , dn+1) = cn+2. Considere e1, · · · , en+1 de forma

que di = cn+2ei. Como os ei =∏j 6=i

j<n+2

cj são dois a dois coprimos,

o problema de Frobênius e1x1 + · · · + en+1xn+1 = u tem solução se

u ≥ n

n+1∏i=1

ci−n+1∑i=1

ei+1. Portanto, fazendo-se v = u−nn+1∏i=1

ci+n+1∑i=1

ei−1,

ii


ii

ii

2.2 O Caso Bidimensional. 37

temos que e1x1 + · · · + en+1xn+1 = u tem solução para todo v ≥ 0.

Substituindo no problema de Frobênius anterior, temos

cn+2(v + nn+1∏i=1

ci −n+1∑i=1

ei + 1) + dn+2xn+2 = f

cn+2v + dn+2xn+2 = f − nn+2∏i=1

ci +n+1∑i=1

di − cn+2

Como no caso n = 1, este último problema de Frobênius bidimensional

tem solução se

f − nn+2∏i=1

ci +n+1∑i=1

di − cn+2 ≥ cn+2dn+2 − cn+2 − dn+2 + 1

f ≥ nn+2∏i=1

ci +n+2∏i=1

ci −n+1∑i=1

di − dn+2 + 1

f ≥ (n+ 1)n+2∏i=1

ci −n+2∑i=1

di + 1

Portanto, por indução segue o que queríamos.

Agora mostraremos que nn+1∏i=1

ai−n+1∑i=1

bi não pode ser escrito da forma

n+1∑i=1

bixi, com xi ≥ 0 ∀i. Suponha que existem y1, · · · , yn+1 ≥ 0 tais

quen+1∑i=1

biyi = n

n+1∏i=1

ai −n+1∑i=1

bi

∴n+1∑i=1

bi(yi + 1) = n

n+1∏i=1

ai

ii


ii

ii


Como os ai's são dois a dois coprimos, temos que ai|yi + 1 ∀i. Sejamq1, · · · , qn+1 tais que yi + 1 = aiqi ∀i. Como yi + 1 ≥ 1, temos que

qi ≥ 1 ∀i. Além disso,

n+1∑i=1

biaiqi = n

n+1∏i=1

ai

n+1∑i=1

(n+1∏j=1

aj)qi = n

n+1∏i=1

ai

n+1∏j=1

aj

n+1∑i=1

qi = nn+1∏i=1

ai

n+1∑i=1

qi = n

e isto implica que existe qi < 1, o que é um absurdo. Logo, o problema

de Frobênius não tem solução para tal número. 2

2.3 O Caso Tridimensional.

2.3.1 Corolário Sobre o Caso Tridimensional.

Proposição 2.3.1. Se d ≥ c(mdc(a, b)− 1) + mmc(a, b)− a− b+ 1,

então o problema do troco de Frobênius

ax+ by + cz = d; x, y, z, a, b, c ∈ N; a, b, c > 0; mdc(a, b, c) = 1

tem solução.

Demonstração. Fixe d ≥ c(mdc(a, b) − 1) + mmc(a, b) − a − b + 1.

Considere o problema em v e z a seguir

mdc(a, b)v + cz = d′ := d−mmc(a, b) + a+ b−mdc(a, b)

ii


ii

ii

2.3 O Caso Tridimensional. 39

Mas,

d′ = d−mmc(a, b) + a+ b−mdc(a, b) ≥

c(mdc(a, b)−1)+mmc(a, b)−a−b+1−mmc(a, b)+a+b−mdc(a, b) ≥

cmdc(a, b)− c−mdc(a, b) + 1.

Logo, existem v0, z0 ∈ N tais que mdc(a, b)v0 + cz0 = d−mmc(a, b) +

a + b − mdc(a, b). Considere m,n ∈ N tais que a = mmdc(a, b) e

b = nmdc(a, b). Como o problema em x e y dado por

mx+ ny = v0 +mn−m− n+ 1

tem solução para todo v0 ∈ N, tome x0, y0 ∈ N tais que mx0 + ny0 =

v0 +mn−m− n+ 1. Finalmente,

ax0 + by0 + cz0 = mdc(a, b)(mx0 + ny0) + cz0

= mdc(a, b)(v0 +mn−m− n+ 1) + cz0

= mdc(a, b)v0 + cz0 + mmc(a, b)− a− b−mdc(a, b)

= d−mmc(a, b) + a+ b−mdc(a, b) + mmc(a, b)− a− b−mdc(a, b)

= d.

Portanto, (x0, y0, z0) é uma solução.

Como consequência do resultado anterior, podemos estimar o valor

de

g(a1, a2, a3) ≤ mini 6=ji 6=kj 6=k

{ak(mdc(ai, aj)− 1) + mmc(ai, aj)− ai − aj + 1

}.

ii


ii

ii


2.3.2 Solução Algorítmica.

Nesta seção, trataremos o problema de Frobênius ax + by + cz = d

de forma algorítmica, isto é, exibiremos um algoritmo para encontrar

g(a, b, c). Em 1960, Johnson no seu artigo A linear diophantine prob-

lem mostrou, além de outros resultados para o problema de Frobênius,

que se mdc(a, b) = d, então g(a, b, c) = d ·g(a/d, b/d, c)+c(d−1). Isto

quer dizer que se soubermos resolver o problema no caso em que a e

b são coprimos, então sabemos resolver o problema em geral. Como

o problema de Frobênius é simétrico com respeito às suas incógnitas,

podemos supor, a partir de agora, que a, b e c são coprimos dois a dois

e, além disso, que a < b < c. Rødseth, em seu artigo On a linear dio-

phantine problem of Frobenius, descreve um algoritmo para o cálculo

de g(a, b, c)1. Apesar de não incluir neste texto uma demonstração

que ateste que tal algoritmo funciona, vamos fazer um exemplo para

que o leitor possa usar o algoritmo a depender de sua vontade.

Algoritmo de Rødseth: Sejam s−1 := a1. Podemos mostrar que

exite um inteiro k > 0 tal que

0 ≤ a3 + ka1a2

< a1 ;a3 + ka1

a2∈ Z

Portanto, considere s0 := (a3 + ka1)/a2. Daí, encontre s1, · · · , sm+1 e

q1, · · · , qm+1 de forma que2

a1 = q1s0 − s1, 0 ≤ s1 < s0,

1existem algoritmos mais e�cientes que este, mas o escolhemos pela simplicidade

das notações.2este procedimento faz parte do estudo das frações contínuas. Sempre é possível

achar tais números si e qi.

ii


ii

ii


s0 = q2s1 − s2, 0 ≤ s2 < s1,

s1 = q3s2 − s3, 0 ≤ s3 < s2,

...

sm−1 = qm+1sm,

sm+1 = 0,

tal que qi ≥ 2, si ≥ 0 para todo i = 1, · · · ,m+ 1. Considere p−1 = 0,

p0 = 1, pi+1 = qi+1pi − pi−1 e ri = sia2 − pia3. Seja v o único inteiro

tal que rv+1 ≤ 0 < rv. Então

g(a1, a2, a3) = −a1 + a2(sv − 1) + a3(pv+1 − 1)−min{a2sv+1, a3pv}.

Exemplo: Vamos calcular g(16, 21, 25). Com cálculos breves, acha-se

que s0 = 5. Portanto, r0 = 5 · 9 − 25 = 20. Lembre-se que estamos

procurando pelo único v tal que rv+1 ≤ 0 < rv. Então, façamos

8 = q1 · 5− s1 ; 0 ≤ s1 < 5

Daí, s1 = 2, q1 = 2, p1 = 2 e r1 = 2 ·9−2 ·25 = −32. Portanto, v = 0.

Com isso,

g(16, 21, 25) = −16 + 21(5− 1) + 25(2− 1)−min{21 · 2, 25 · 1}

= −16 + 84 + 25− 25 = 84− 16 = 68 2

2.3.3 Comentários e Casos Especiais.

Ao longo dos anos, vários matemáticos resolveram muitas classes de

problema de Frobênius. Em 1974, por exemplo, Vitek provou, em seu

artigo [13] que

ii


ii

ii


Teorema 2.3.2. Vitek Sejam a1 < · · · < an inteiros positivos tais

que mdc(a1, · · · , an) = 1. Então,

g(a1, · · · , an) <

⌊(a2 − 1)(an − 2)

2

⌋Roberts no artigo [14] resolveu o problema de Frobênius quando

as constantes estão em progressão aritmética:

Teorema 2.3.3. Roberts Sejam a, d e s inteiros tais que mdc(a, d) =

1. Então,

g(a, a+ d, · · · , a+ sd) =

(⌊a− 2

s

⌋+ 1

)a+ (d− 1)(a− 1)− 1.

Estes são apenas 2 exemplos das várias classes de problemas que

são restrições do problema de Frobênius. Além desses, na seção 3.2.3 já

havíamos falado também sobre o resultado de Raczunas e Chrz�astowski-

Wachtel para qualquer número de variáveis. O leitor poderá encontrar

mais exemplos de classes no livro The Diophantine Frobenius Problem

(Oxford Lecture Series in Mathematics and its applications - 30) do

autor J. L. Ramírez Alfonsín.

Exercícios

1. Prove que toda quantia inteira maior ou igual a R$4, 00 pode

ser paga utilizando notas de R$2, 00 e R$5, 00.

2. Em um país imaginário a moeda se chama nioc. Existem moedas

de 1, 3 e 5 niocs. Mostre que não é possível pagar 25 niocs com

exatamente 10 moedas com os valores citados.

ii


ii

ii


3. Em uma partida de Rugby (um esporte de origem inglesa) exis-

tem quatro diferentes tipos de pontuações. Penalty (3 pontos),

drop goal (3 pontos), try (5 pontos) e converted try (7 points).

Combinando tais pontuações mostre que é possível atingir qual-

quer quantidade de pontos, exceto 1,2 e 4.

4. Originalmente, as caixas de McNuggets eram de 3 tipos: os que

continham 6 McNuggets, 9 ou 20. Mostre que qualquer número

de McNuggets maior que 43 pode ser comprado.

5. Determine g(9, 16, 35).

ii


ii

ii


ii


ii

ii

CAPÍTULO 3

Pontos Inteiros em Regiões Poligonais

Considere que um agricultor possui um terreno poligonal com vértices

inteiros e que cada ponto inteiro do interior do terreno deve represen-

tar uma planta. Como determinar a quantidade de plantas no terreno?

Quais parâmetros do terreno in�uenciam em tal quantidade?

Certamente a área do terreno é de grande importância, vamos mostrar

que não é o único fator. Considere, na �gura a seguir, diversos ter-

renos com formatos diferentes, mas com mesma área. Observe que a

quantidade de plantas não é a mesma...

Observamos que todos os polígonos da �gura possuem a mesma

área, entretanto o número de pontos em seu interior é variável. Uma

Olhada mais precisa te fará notar que alguns tem o mesmo número de

pontos inteiros no interior e isso ocorre justamente quando o número

de pontos inteiros na fronteira coincide.

45

ii


ii

ii

46 Pontos Inteiros em Regiões Poligonais

3.1 O Teorema de Pick

O teorema de Pick fornece uma maneira combinatória de calcular

a área de um polígono simples com vértices inteiros. A fórmula de

Pick envolve o número de pontos inteiros na fronteira do polígono e o

número de pontos inteiros no interior do polígono. No presente con-

texto a fórmula de Pick pode ser interpretada como uma forma de

encontrar o número de pontos inteiros no interior do polígono.

De�nição 3.1.1. Um polígono plano é dito ser simples se não possuir

�furos"e se suas arestas só se intersectarem nos vértices. Um polígono

simples pode ser côncavo ou convexo.

De�nição 3.1.2. Sejam P ⊂ R2 um polígono simples cujos vértices

pertencem a Z2 (pontos do plano com coordenadas inteiras). De�na

ii


ii

ii

3.1 O Teorema de Pick 47

F o número de pontos inteiros na fronteira de P (vértices e arestas)

e I o número de pontos inteiros no interior de P.

Como temos observado polígonos de mesma área podem ter difer-

entes números de pontos inteiros em seu interior e em sua fronteira.

Uma análise dos exemplos nos leva a crer que quando área é mantida,

a cada unidade diminuída na quantidade de pontos inteiros interiores

aumentam duas unidades de pontos inteiros da fronteira. Assim é

razoável acreditar que a quantidade

1

2F + I

é invariante desde que a área também o seja. O próximo resultado

con�rma essa intuição e é devido a Pick.

Teorema 3.1.3. (Pick) Sejam P ⊂ R2 um polígono simples cujos

vértices pertencem a Z2. Então a área do polígono P é

A(P) =1

2F + I − 1

Demonstração. De�na o número de Pick de um polígono simples Pcom vértices inteiros por:

Pick(P) =1

2F + I − 1.

Se dois polígonos simples possuem uma aresta de mesmo módulo e

direção, então podemos obter, a partir deles, um novo polígono identif-

icando essa aresta e deletando-a - desde que não haja superposição das

�guras- o polígono assim obtido é o que chamaremos a justaposição

dos polígonos iniciais P = P1

⊕P2.

ii


ii

ii


P1

P2

Vamos mostrar que o número de Pick é aditivo por justaposição.

Sejam Pi, i = 1, 2 dois polígonos simples com vértices inteiros e com

uma aresta de mesmo módulo e direção. E sejam Fi e Ii, respectiva-

mente, o número de pontos inteiros na fronteira e no interior do polí-

gono Pi, i = 1, 2. Digamos que o segmento comum, na justaposição

possui k + 2 pontos inteiros.

O número de pontos inteiros no interior da justaposição é

I = I1 + I2 + k

pois, após a justaposição, os k vértices (não terminais) da aresta dele-

tada vão pertencer ao interior do polígono P = P1 ⊕ P2.

O número de pontos inteiros na fronteira da justaposição é

F = F1 + F2 − 2(k + 2) + 2

ii


ii

ii


pois somando os pontos de fronteira de P1 e P2 e subtraindo duas

vezes os pontos inteiros da aresta deletada só faltam os terminais da

aresta deletada para completar os pontos inteiros na fronteira de P .

Calculando o número de Pick de P , temos:

Pick(P) =1

2(F1+F2−2(k+2)+2)+I1+I2+k = Pick(P1)+Pick(P2).

Agora note que todo polígono simples no plano pode ser subdivi-

dido em triângulos de modo que o vértice de cada triângulo seja algum

vértice do polígono. Assim, todo polígono com vértices inteiros pode

ser subdividido em triângulos com vértices inteiros. Pelo resultado de

aditividade por justaposição, podemos nos reduzir ao caso de triângu-

los com vértices inteiros para provar o teorema de Pick.

Todo triângulo com vértices inteiros pode ser inscrito em um retân-

gulo horizontal com vértices inteiros. Assim podemos nos reduzir aos

triângulos retângulos horizontais ou melhor, aos próprios retângulos

horizontais.

Todo triângulo horizontal é formado por justaposição de quadra-

dos 1×1. Assim, se veri�camos a fórmula de Pick em quadrados 1×1,

então vale o teorema de Pick em geral

Para um quadrado 1 × 1 temos: A = 1, F = 4, I = 0, e efetiva-

mente,

A = 1 =1

2.4 + 0− 1 =

1

2F + I − 1.

ii


ii

ii


Observação 3.1.4. Ver, por exemplo, Lages Lima, E. [9]. A seção

intitulada Como calcular a área de um polígono se você sabe contar.

Como havíamos dito queremos olhar para a fórmula de Pick de

outra forma:

I = A− 1

2F + 1

E sabemos que a área pode ser calculada de várias formas. Gostaríamos

de terminar essa seção mostrando como calcular F de maneira instan-

tânea.

Proposição 3.1.5. Seja P = A0A1A2...An−1An, com An = A0, um

polígono simples no plano com vértices inteiros, isto é, Ai ∈ Z. De�navi =

−−−−→Ai−1Ai = (ai, bi) e di = mdc(ai, bi). Então o número de pontos

inteiros na fronteira de P é F =n∑

i=1

di.

Demonstração. Em primeiro lugar notamos que um segmento de reta

PQ com P,Q ∈ Z2 tal que v =−→PQ = (a, b) com mdc(a, b) = 1, não

possui ponto inteiro no seu interior. Com efeito, se existisse um ponto

inteiro R em seu interior, então teríamos triângulos semelhantes, com

lado inteiro como na �gura.

Q

R

I J

ii


ii

ii


Da nossa hipótese PJ = a e QJ = b são inteiros e mdc(a, b) = 1.

Agora estamos supondo que PI = c e RI = d também são inteiros e

além disso c < a e b < d. Da semelhança de triângulos obtemos

PI

PJ=PJ

QR⇔ a

b=c

d

Entretanto a fração abé uma fração irredutível e, portanto, é um ab-

surdo que ela seja semelhante a outra fração com numerador e de-

nominador de menor módulo. Assim concluímos que não existe ponto

inteiro no interior do segmento PQ.

Sejam P,Q ∈ Z2 ⊂ R2 e v =−→PQ = (a, b) dois vértices consecutivos

do polígono, então o número de pontos inteiros na aresta PQ é igual

a d + 1 em que d = mdc(a, b). Com efeito, basta dividir o segmento

PQ em d segmentos cujo vetor que o representa tenha coordenadas

inteiros coprimos.

Para concluir note que cada aresta Ai−1Ai do polígono vai possuir,

em seu interior(sem contar os vértices), di− 1 pontos inteiros. Logo o

número de pontos inteiros na fronteira do polígono será

n∑i=1

di − n+ n

−n corresponde a −1 para cada aresta e +n corresponde aos vértices

do polígono.

3.1.1 Teorema de Pick e a fórmula de Euler

Nessa seção gostaríamos de destacar a natureza topológico-combinatória

do Teorema de Pick. Para isso gostaríamos de recordar a famosa

ii


ii

ii


relação de Euler para grafos planos. Mais precisamente, para nos-

sos propósitos, será su�ciente considerar uma versão mais fraca da

relação de Euler. Vamos considerar uma �gura plana simples con-

stituída de uma quantidade �nita de polígonos (que chamaremos de

faces); justapostas pelas arestas, de forma que duas faces, quando se

intersectam, o fazem ou por um vértice ou por uma aresta. De�nimos

para uma tal �gura v seu número de vértices, a seu número de arestas

e f seu número de faces ( na nossa formulação não será contada a face

ilimitada, exterior a �gura). Estaremos supondo ainda que a fron-

teira da �gura seja um polígono simples de modo que podemos pensar

na mesma como sendo uma cobertura do polígono simples por out-

ros polígonos simples. Tal �gura será chamada grafo poligonal plano.

Temos o seguinte resultado devido a Euler:

Teorema 3.1.6. Seja G um grafo poligonal plano com v vértices, a

arestas e f faces. Então vale a seguinte relação:

v − a+ f = 1

De�nição 3.1.7. Um triângulo T ⊂ R2 é chamado fundamental se

possui vértices inteiros e não possui nenhum outro ponto inteiro em

sua fronteira e em seu interior.

Proposição 3.1.8. Todo polígono fundamental no plano T ⊂ R2 pos-

sui área 12.

Demonstração. ver [elon]

Temos condições agora de fornecer uma outra demonstração para

o Teorema de Pick.

ii


ii

ii


Teorema 3.1.9. (Pick) Sejam P ⊂ R2 um polígono simples cujos

vértices pertencem a Z2. Sejam F e I, respectivamente, o número de

pontos inteiros em sua fronteira e em seu interior. Então a área do

polígono P é

A(P) =1

2F + I − 1

Demonstração. É sempre possível triangularizar o polígono P (seu in-

terior e sua fronteira) utilizando polígonos fundamentais, assim de�n-

imos um grafo poligonal plano e denotaremos por v, a e f seu número

de vértices, arestas e faces, respectivemente. Note que v = F + I uma

vez que todos os pontos inteiros do interior e da fronteira de P são

vértices de algum triângulo da triangulação.

Como os polígonos fundamentais possuem área 12obtemos a seguinte

relação:

A = A(P ) =f

2(3.1)

Utilizando a fórmula de Euler e fazendo as substituições citadas, obte-

mos

f = F + 2I − 2⇒ A =f

2=

1

2F + I − 1

3.1.2 Área de Polígonos no Plano

Existem muitas formas de calcular a área de um polígono no plano

cartesiano. Vamos apresentar uma forma determinantal de calcular a

área de um polígono convexo dados seus seus vértices em uma ordem

cíclica. Esse método é muito difundido entre os que trabalham com

Topogra�a - tanto em nível técnico quanto em nível acadêmico - en-

tretanto é pouco lembrado pelos que trabalham com Matemática.

ii


ii

ii


Em primeiro lugar vamos calcular a área de um paralelogramo

P ⊂ R2. Um paralelogramo no plano pode ser de�nido a partir de

dois vetores v, w ∈ R2. Seus vértices serão 0, v, w e v+w. Se consider-

armos estes vetores como vetores espaciais (com a última coordenada

nula), estamos fazendo a identi�cação R2 ∼= {(x, y, z) ∈ R3|z = 0}.Agora, podemos usar o produto vetorial do R3 para calcular a área do

paralelogramo, veri�ca-se facilmente que

v × w = det(v, w)k = (0, 0, det(v, w)).

Ou seja, a área de um paralelogramo no plano gerado pelos vetores v

e w é

A = ||v × w|| = | det(v, w)|.

Nessa notação, det(v, w) é o determinante da matriz quadrada de

ordem 2 cujas linhas são, respectivamente, as coordenadas de v e w.

Dado um triângulo no plano com vértices A = (x1, y1), B = (x2, y2)

e C = (x3, y3) podemos determinar sua área que é a metade da área

do paralelogramo gerado pelos vetores v = ~AB = (x2 − x1, y2 − y1) ew = (x3 − x1, y3 − y1). Assim

A = | det(v, w)| = 1

2

∣∣∣∣∣ x2 − x1 x3 − x1y2 − y1 y3 − y1

∣∣∣∣∣Aqui tomamos o valor absoluto deste determinante.

Vamos usar uma notação diferente que nos auxiliará na determi-

nação de uma fórmula para a área de um polígono convexo qualquer.

De�nição 3.1.10. Sejam xi, yi ∈ R com i = 1, . . . n∣∣∣∣∣ x1 . . . xn x1

y1 . . . yn y1

∣∣∣∣∣ := ∆(1, 2) + ∆(2, 3) + · · ·+ ∆(n− 1, n) + ∆(n, 1)

ii


ii

ii


Em que ∆(i, j) =

∣∣∣∣∣ xi xj

yi yj

∣∣∣∣∣.Se escolhermos a orientação anti-horária na ordem cíclica, então

este determinante generalizado é sempre positivo.

Teorema 3.1.11. Seja P = A1A2 . . . AnA1 ⊂ R2 um polígono convexo

cujos vértices foram dados em ordem cíclica e tem coordenadas Ai =

(xi, yi) para i = 1, . . . , n.

Demonstração. Em primeiro lugar notamos que o resultado vale para

triângulos. Com efeito, basta notar que

A =1

2

∣∣∣∣∣ x2 − x1 x3 − x1y2 − y1 y3 − y1

∣∣∣∣∣ =

∣∣∣∣∣ x1 x2 x3 x1

y1 y2 y3 y1

∣∣∣∣∣Suponhamos, por hipótese indutiva, que o resultado seja válido para

polígonos convexos com n− 1 ≥ 3 vértices. Considere

P = A1A2 . . . AnA1 ⊂ R2 um polígono convexo com n vértices. Clara-

mente podemos decompor P em um triângulo e um polígono de n− 1

lados, por exemplo T = A1An−1An e P = A1A2 . . . An−1A1. Usando a

hipótese indutiva temos

A(P ) = A(T ) +A(P ) =

∣∣∣∣∣ x1 xn−1 xn x1

y1 yn−1 yn y1

∣∣∣∣∣+∣∣∣∣∣ x1 . . . xn−1 x1

y1 . . . yn−1 y1

∣∣∣∣∣Pela de�nição temos

A(P ) = ∆(1, n− 1) + ∆(n− 1, n)

+∆(n, 1) + ∆(1, 2) + ∆(2, 3) + . . . + ∆(n− 2, n− 1) + ∆(n− 1, 1)

Cancelando ∆(1, n − 1) + ∆(n − 1, 1) obtemos o resultado desejado.

E o teorema segue por indução.

ii


ii

ii


3.1.3 Teorema de Pick Generalizado e Estimativas

de Plantação

Uma versão mais geral do Teorema de Pick pode ser naturalmente

formulada num reticulado qualquer no plano. Sejam P ⊂ R2 um

polígono simples e L ⊂ R2 um reticulado no plano de modo que cada

um dos vértices do polígono P são elementos do reticulado. Denotamos

por I = IL(P ) o número de pontos de L no interior do polígono P e

por F = FL(P ) o número de pontos de L na fronteira de P . Vamos

de�nir uma aplicação linear

T : R2 → R2

De modo que a imagem de Z2 por T consiste precisamente de T (Z2) =

L. Dada uma base de L, v1, v2, de�nimos T exigindo que T (ei) =

vi para i = 1, 2. A transformação linear assim de�nida possui as

seguintes propriedades:

1. T é um isomor�smo linear;

2. T−1(L) = Z2.

Com as notações iniciais P ⊂ R2 e L ⊂ R2 respectivamente um polí-

gono simples e um reticulado não degenerado (de modo que os vértices

do polígono são pontos do reticulado); Podemos utilizar a transfor-

mação T , acima construida, para de�nir, via Pullback, P := T−1(P ) ⊂R2 que é também um polígono simples, L := T−1(L) = Z2 ⊂ R2 que

consiste do reticulado padrão, por construção, e os vértices de P são

pontos inteiros.

ii


ii

ii


Lema 3.1.12. Com as notações estabelecidas, T restrita à fronteira

de P é uma bijeção entre a fronteira de P e a fronteira de P que

leva pontos inteiros da fronteira de P em pontos da fronteira de P

que pertencem a L. T restrita ao interior de P é uma bijeção entre

o interior de P sobre o interior de P que envia pontos inteiros do

interior de P em pontos do interior de P que pertencem a L. Em

particular

FL(P ) = F (P ), IL(P ) = I(P )

Demonstração. Em primeiro lugar notamos que os polígonos P e P

de�nem dois subconjuntos abertos do plano; o interior e o exterior de

cada um deles. Sendo T e T−1 funções contínuas suas restrições ao

interior de P e P é uma bijeção. Analogamente para a região exterior.

Daí concuímos a bijeção entre as fronteiras. As demais a�rmações

seguem diretamente da construção de T .

Teorema 3.1.13. Sejam P ⊂ R2 um polígono simples e L ⊂ R2 um

reticulado no plano com área fundamental A(L), de modo que cada um

dos vértices do polígono P são elementos do reticulado. Denotamos

por I = IL(P ) o número de pontos de L no interior do polígono P e

por F = FL(P ) o número de pontos de L na fronteira de P . Então

A(P )

A(L)=

1

2FL(P ) + IL(P )− 1

Demonstração. É su�ciente tomar o pull-back de P e L pela transfor-

mação linear anteriormente de�nida e usar o Teorema de Pick origi-

nal.

Para efeito de aplicações reais o modelo de plantas representando

pontos inteiros no plano não é o mais conveniente. Com efeito para

ii


ii

ii


plantar em um terreno faz-se sulcos que chamaremos linhas de plan-

tação (ou simplesmente linhas) que são paralelas entre si e estão a uma

distância constante que chamaremos distância entre linhas e denotare-

mos por a. Em cada sulco de plantação as plantas são plantadas em

covas que estão a uma distância �xa que denotaremos por b e chamare-

mos distância entre plantas. Uma hipótese bastante natural é que as

plantas estão nas perpendiculares das linhas de plantação de modo que

cada planta represente um ponto de um reticulado que possui como

domínio fundamental um retângulo de lados a e b e, portanto, área

A(L) = ab.

Segundo a Embrapa, em seu sítio o�cial, ver [16].

O espaçamento é de�nido como sendo a distância existente entre plan-

tas de mesma �leira (espaçamento entre plantas) ou entre plantas de

�leiras diferentes (espaçamento entre linhas). Os espaçamentos re-

comendados para as principais culturas são apresentados na tabela a

seguir. Ainda segundo o mesmo:

O espaçamento é bastante variável entre as espécies e, mesmo para

uma mesma espécie, entre as cultivares. Está também relacionado com

diversos fatores, como, por exemplo, tecnologia adotada, maquinário

disponível na propriedade, vigor do porta-enxerto e da cultivar-copa,

disponibilidade de área, entre outros.

ii


ii

ii

3.2 O tetraedro de Reeve 59

3.2 O tetraedro de Reeve

Em 1957 John Reeve apresentou a seguinte família de tetraedros para

mostrar que não existe uma generalização natural do teorema de Pick

em dimensão superior.

Em R3 considere a família de tetraedros Tn com n natural, de vértices

(0, 0, 0), (1, 0, 0), (0, 1, 0) e (1, 1, n) todos pertencentes ao reticulado

padrão Z3 ⊂ R3. O fato é que qualquer que seja n o tetraedro de

Reeve não possui nenhum ponto inteiro em suas faces nem em seu

interior.

Problemas

1. Um agricultor possui um terreno poligonal e deseja plantar pés

de milho em seu interior. Suponhamos que, após uma escolha de

eixos coordenados os vértices do polígono e os pés de milho vão

corresponder a pontos com coordenadas inteiras. Determinar o

número de pés de milho que podem ser plantados supondo que

os vértices do polígono são: A = (0, 0), B = (8, 0), C = (15, 10),

D = (12, 20), E = (10, 15) e F = (0, 10).

2. Dado v ∈ Z2 ⊂ R2, v = (a, b), com mdc(a, b) = 1, mostre que

existe w = (c, d) ∈ Z2 ⊂ R2 tal que o paralelogramo gerado por

v e w não possui ponto inteiro em seu interior.

3. Prove que todo polígono simples com vértices inteiros possui área

cujo dobro é um número inteiro.

4. Mostre que um triângulo plano com vértices inteiros tem área

mínima A = 12se, e somente se, o triângulo não possui ponto

ii


ii

ii


inteiro no seu interior. Mostre que de fato essa é a área mínima.

5. Mostre que no plano existem triângulos com vértices inteiros de

área mínima A = 12com perímetro arbitrariamente grande.

6. Sejam v ∈ Z2 ⊂ R2, v = (a, b), d = mdc(a, b) e ∆(v) =

{det(v, w)|w ∈ Z2}. Então:

∆(v) = dZ = {dm|m ∈ Z}.

Ou seja, o mdc entre as coordenadas do vetor v representa a

menor área de um paralelogramo com vértices inteiros tendo v

como um dos lados.

7. Considere, no plano cartesiano, o segmento de reta ligando os

pontos A(n, 0) e B(0, n) sua equação é x+ y = n, com x, y ≤ n.

Os pontos inteiros nesse segmento são da forma (i, n − i), comi natural. Assim sendo, temos n − 1 pontos inteiros no interior

do segmento. Conectando cada um desses pontos inteiros com a

origem surgem n triângulos menores que particionam o triângulo

OAB. Claramente os trinâgulos que possuem um dos vértices A

ou B não possui pontos inteiros em seu interior. Mostre que se

n é um número primo, então todos os outros triângulos possuem

o mesmo número de pontos inteiros em seu interior.

8. Considere o reticulado padrão no plano Z2 ⊂ R2. Considere

também um quadrado n× n. Mostre que o quadrado não pode

cobrir mais de (n+ 1)2 pontos do reticulado padrão.

ii


ii

ii

3.2 O tetraedro de Reeve 61

CULTURA

DISTÂNCIAENTRE

PLANTAS(m)

DISTÂNCIA ENTRE LINHAS

(m)

ESPAÇAMENTO MAIS

UTILIZADO(m)

AceroleiraAbacateiroAbacaxizeiroAmeixeiraAmoreirapretaAraçazeiroBananeiraCaquizeiroCitrosFigueiraFramboeseiraGoiabeiraJabuticabeiraQuivizeiroMacieiraMamoeiroMangueiraMaracujazeiroMarmeleiroMirtiloMorangueiroNespereiraPereiraPessegueiroRomanzeiraVideira

2,0 a 5,07,0 a 10,0

0,33,0 a 4,00,3 a 0,72,0 a 4,0

2,55,0 a 7,02,0 a 7,02,0 a 3,0 0,3 a 0,73,0 a 11,04,0 a 7,04,0 a 6,00,8 a 5,0

2,08,0 a 12,0

2,53,0

1,0 a 1,50,3 a 0,45,0 a 7,0

4,0 a 10,01,0 a 4,04,0 a 6,0 1,0 a 3,5

4,0 a 6,0 9,0 a 12,00,8 a 1,05,0 a 7,02,5 a 3,02,5 a 6,0

3,06,0a 8,05,0 a 8,03,0 a 5,02,5 a 3,06,0 a 11,04,0 a 7,04,0 a 6,04,0 a 7,0

3,08,0 a 12,0

3,04,0

3,0 a 4,00,3 a 0,45,0 a 7,0

5,0 a 10,05,0 a 7,04,0 a 6,0 2,5 a 4,0

4,0 x 5,010 x 10

0,3 x 0,94,0 x 6,00,5 x 3,02,0 x 4,02,5 x 3,07,0 x 7,0 4,0 x 6,03,0 x 5,00,5 x 3,05,0 x 7,06,0 x 6,05,0 x 5,01,25 x 5,02,0 x 3,0

10,0 x 10,02,5 x 3,03,0 x 4,01,0 x 4,00,3 x 0,46,0 x 6,0 4,0 x 604,0 x 6,05,0 x 5,02,0 x 3,0

Figura 3.1: Espaçamento entre plantas

ii


ii

ii


ii


ii

ii

CAPÍTULO 4

Apêndice-Reticulados

Neste apêndice damos início ao estudo dos reticulados no espaço eu-

clidiano Rn. Esta teoria de reticulados permite que seja desenvolvida

uma álgebra linear inteira.

4.1 Reticulados e seus Domínios Fundamen-

tais

De�nição 4.1.1. Sejam v1, v2, . . . , vm ⊂ Rn vetores que geram um

subespaço vetorial de dimensão k. Um reticulado de posto k em Rn,

com conjunto de geradores os vetores {v1, v2, . . . , vm}, consiste do con-junto das combinações (lineares) inteiras desses vetores, ou seja

L = {v ∈ Rn|v = a1v1 + a2v2 + · · ·+ amvm, ai ∈ Z i = 1, 2, . . . ,m}.

63

ii


ii

ii

64 Apêndice-Reticulados

Vamos conectar a noção de reticulado e a noção algébrica de gru-

pos. Se L ⊂ Rn é um reticulado com conjunto de geradores

{v1, v2, . . . , vm}, dados v, w ∈ L, podemos escrever v = a1v1 + a2v2 +

· · · + amvm e w = b1v1 + b2v2 + · · · = bmvm em que ai, bi ∈ Z para

i = 1, 2, . . . ,m, portanto, v + w = (a1 + b1)v1 + (a2 + b2)v2 + · · · +(am + bm)vm ∈ L e −v = (−a1)v1 + (−a2)v2 + · · · + (−am)vm ∈ L.

Estas são as condições para que L seja um subgrupo aditivo de Rn.

Entretanto um reticulado L ⊂ Rn não é qualquer tipo de sub-

grupo. Como respeiton a topologia de Rn um reticulado é, sempre,

um subconjunto discreto!!!

De�nição 4.1.2. Um subconjunto de X ⊂ Rn é discreto se todos os

seus pontos são isolados, isto é, se dado p ∈ X, existir δ > 0 tal que o

único ponto da interseção da bola aberta B(p, δ) = {q ∈ Rn| ||q−p|| <δ} com X for o próprio p. Ou seja,

D(p, δ) ∩X = {p}

Observação 4.1.3. Lembramos que os únicos subgrupos discretos da

reta real são isomorfos a Z (e todos são reticulados da reta!!!). De fato,

seja G ⊂ R um subgrupo aditivo discreto e seja m o menor elemento

positivo de G (tal elemento existe pois G é discreto), então G = mZ.(Veri�que os detalhes!)

Subgrupos de R não discretos são bem mais complicados, por ex-

emplo, Q ⊂ R é um subgrupo aditivo que é denso!!!

Proposição 4.1.4. Seja G ⊂ Rn um subgrupo aditivo. Então são

equivalentes:

ii


ii

ii

4.1 Reticulados e seus Domínios Fundamentais 65

1. G é um reticulado;

2. G ⊂ Rn é discreto.

Demonstração. Vamos fazer a demonstração em R2, por simplicidade,

mas o caso geral segue de maneira análoga.

Seja G ⊂ R2 um reticulado com conjunto de geradores {v, w}. Vamos

mostrar que G é um conjunto discreto. Vamos mostrar que 0 é um

ponto isolado e o resultado segue, por translação. Claramente não ex-

iste ponto reticulado no conjunto int(D) = {u ∈ R2|u = αv+βw} com0 < α < 1 e 0 < β < 1. Assim, tome δ = 1

2min{||v||, ||w||, ||v + w||}.

Claro que G ∩D(0, δ) = 0.

Reciprocamente, seja G ⊂ R2 um subgrupo aditivo discreto. Para

mostrar que G é um reticulado devemos encontrar geradores. Seja

v ∈ G o vetor não nulo de menor norma. Seja w ∈ G o ponto mais

próximo da reta ` =< v >= {λv|λ ∈ R} (não contido na reta).

A�rmamos que G =< v,w >= {av + bw|a, b ∈ Z}. Com efeito,

seja u ∈ G, e considere os pontos u − mw ∈ G com m ∈ Z. O

ponto mais próximo da reta ` deve pertencer a mesma, caso contrário

encontraríamos um ponto mais próximo que w. Assim u −mw = λv

e λ = n ∈ Z, logo u = mv + nw.

A partir da proposição acima vemos que é possível exibir um retic-

ulado intrinsecamente, isto é, sem explicitar um conjunto de geradores.

Por um lado é mais fácil tratar um reticulado quando conhecemos um

conjunto de geradores, por outro lado, muitas vezes é mais fácil provar

que um dado conjunto é um reticulado observando que o mesmo é um

subgrupo aditivo e discreto do plano R2.

ii


ii

ii

66 Apêndice-Reticulados

Exemplo 4.1.5. Considere o reticulado padrão do plano, ou seja,

L = Z2 ⊂ R2. Temos vários possíveis conjuntos de geradores para

tal reticulado. Por exemplo B1 = {(1, 0), (0, 1)} é um conjunto de

geradores para L e B2 = {(2, 1), (1, 1)} também é um conjunto de

geradores para L (faça um esboço dos reticulados associados a estes

conjuntos de geradores e veri�que que ambos coincidem com Z2). De

fato,

(2, 1) = 2.(1, 0) + 1.(0, 1), (1, 1) = 1.(1, 0) + 1.(0, 1)

logo o reticulado associado a B2 está contido no reticulado associado

a B1 (combinações inteiras dos vetores de B2 são combinações inteiras

dos vetores de B1 pois os próprios vetores de B2 o são) e, reciproca-

mente

(1, 0) = 1.(2, 1)− 1.(1, 1) (0, 1) = −1.(2, 1) + 2.(1, 1).

Ou seja, os reticulados associados são o mesmo e, claramente, tal

reticulado é Z2 ⊂ R2.

De�nição 4.1.6. Uma base de um reticulado é um conjunto de ger-

adores minimal.

Notamos que o problema computacional de fazer funcionar o pseudo-

algoritmo anteriormente mecionado é bem complicado uma vez que

oproblema de determinar uma base com vetores minimais é computa-

cionalmente complicado.

De�nição 4.1.7. Dado um reticulado L ⊂ Rn com base

{v1, v2, . . . , vm} , o conjunto dos pontos a1v1 + a2v2 + · · · + amvm ∈Rn para os quais 0 ≤ ai < 1 é chamado o domínio fundamental do

reticulado L associado `a base {v1, v2, . . . , vm}.

ii


ii

ii

4.1 Reticulados e seus Domínios Fundamentais 67

Observação 4.1.8. A noção de domínio fundamental depende da

base, como mostramos no exemplo anterior. Por outro lado, a área

(volume) de um domínio fundamental independe do conjunto de ger-

adores.

Proposição 4.1.9. Sejam L ⊂ Rn um reticulado de posto k, D e E

domínios fundamentais associados, respectivamente, às bases

{v1, v2, . . . , vk} e {u1, u2, . . . , uk}. Então os volumes dos domínios fun-

damentais são iguais,

V ol(D) = V ol(E).

Demonstração. Sabemos que existem inteiros aij ∈ Z com 1 ≤ i, j ≤ k

tais que

ui = ai1v1 + ai2v2 + . . . aikvk

pois ui pertencem ao reticulado, logo, são combinação inteira de

v1, v2, . . . , vk e reciprocamente. Assim, a matriz de mudança de base

M =(aij

)é inversível e sua inversa N é também uma matriz

de coe�cientes inteiros(dados pelas coordenadas de v1, v2, . . . , vk es-

critos como combinação inteira de u1, u2, . . . uk). Como M.N = I2,

det(M). det(N) = 1 e como são ambos inteiros, det(M) = ±1.

O volume do domínio fundamental E é

V ol(E) = | det(M)|V ol(D) = V ol(D).

ii


ii

ii

68 Referências

ii


ii

ii

Referências Bibliográ�cas

[1] Alfonsín, J.R. (2005) The Diofantine Frobenius Problem.

Oxford University Press.

[2] Ho�mann, K., Kunze, R. (1976) Álgebra Linear LTC,

Rio de Janeiro

[3] van der Waerden, B.L. (1970) Algebra, Volume 2. Fred-

erick Ungar Publishing Co., New York, 1970.

[4] Stewart, I. N.; Tall, D. O. (2002) Algebraic number

theory and Fermat`s last Theorem. A K Peters, Natick

MA, 3rd Edition.

[5] Garcia, A.; Lequain, I. (1996) Elementos de Álgebra.

Projeto Euclides, IMPA, Rio de Janeiro, 1996.

[6] Hefez, A. Iniciação à Aritmética. PIC-OBMEP, Rio de

Janeiro.

69

ii


ii

ii

70 REFERÊNCIAS BIBLIOGRÁFICAS

[7] Hefez, A. Elementos de Aritmética. Textos Univer-

sitários, SBM, Rio de Janeiro.

[8] Lima, E.L. (2006) Meu Professor de Matemátrica e

outras Histórias Coleção do Professor de Matemática,

IMPA, Rio de Janeiro.

[9] Lima, E.L. (2006) Algebra Linear Coleção Matemática

Universitária, IMPA.

[10] Abdulrab, H.; Pécuchet, J.P. (1989) Solving systems of

linear diophantine equations and word equations. Lec-

ture Notes in Computer Science Volume 355, pp 529-

532.

[11] Lazebnik, F (1996) On systems of linear diophantine

equations. Mathematics Magazine, vol. 69, no. 4, 261-

266.

[12] Barrière, L. ; Miralles, A. (2007) The Frobenius problem:

A Geometric Approach Technical report UPCommons

[13] Vitek, Y.(1974) Bounds for a linear diophantine problem

of Frobenius J. London Math. Soc., 10(2), 79-85

[14] Roberts, J.B. (1956) Note on Linear forms Proc. Am.

Math. Soc., 7

[15] Rodseth, O. J. (1978) On a linear diophantine Frobenius

plroblem J. Reine Ang. Math., 301, 171-178

ii


ii

ii

4.1 REFERÊNCIAS BIBLIOGRÁFICAS 71

[16] Fachinello, J.C., Nachitigal, J.C., Kersten, E.

Fruticultura: Fundamentos e Praticas http :

//www.cpact.embrapa.br-EMBRAPA

Documents

Sumário - univasf.edu.brfelipe.wergete/ensino/profmat_arit/aritmetica... · Aritmética à Álgebra, que essencialmente foi desenvolvida com o ob-jetivo de resolver equações. A