Matemática

Teoria Elementar dos Números

Quando se fala em Teoria dos Números, não podemos deixar de falar de divisibilidade. Por isso, devemos ter em mente alguns teoremas simples sobre divisibilidade:

Teorema Básico: Sempre podemos escrever [; a = bq +r ;]

. Chamamos [;q;]

de quociente da divisão e [;r;]

de resto da divisão euclidiana, onde 0< r < q ou r=0.

Teorema da Divisibilidade de Inteiros: Dados inteiros [;a,b,c;]

, então

(a) Se

, então

para quaisquer valores de [;x,y;]

nos inteiros

(b) Se

, então $[;|a| \le |b|;]$

, então

Como a demonstração de ambos os teoremas é muito intuitiva, esta será deixada a cargo do leitor interessado. Esta é a nossa primeira parte, que nos permite resolver alguns problemas interessantes:

Exemplo 1: Determine todos os inteiros não negativos [; n;]

tais que $[;\frac{n^3+2n-1}{3n^2-1};]$ é também inteiro.

Resolução: Utilizando o nosso item (a), Reduzimos a expressão para achar todos os [;n;]

tais que $[;\frac{7n-3}{3n^2-1};]$ é inteiro. Utilizando, agora, o item (b), temos que $[;|3n^2-1|\le|7n-3|;]$ . Portanto, temos que $[;o\le n \le 2;]$ . Verificando, todos estes números são realmente soluções.

Exemplo 2: (Bielorrussia 1996) Sejam [;m,n;]

inteiros tais que

$[;(m-n)^2=\frac{4mn}{m+m-1};]$

a) Prove que [;(m-n);]

é um quadrado perfeito.

b) Ache todos os inteiros que satisfazem esta relação.

Resolução:

[; (m+n)(m-n)^2 = 4mn + m^2 - 2nm + m^2 = (m+n)^2;]

b) Se

,então

(segundo caso), e nossos pares são $[;(t,-t), (\frac{t^2+t}{2}, \frac{t^2-t}{2});]$ que são realmente soluções da equação.

Agora, analisemos o exemplo a seguir:

Exemplo 3: (IMO-2007) Se [;a,b;]

são inteiros positivos tais que [; 4ab-1 | (4a^2 -1)^2 ;]

, prove que [; a=b;]

Bom, comecemos utilizando nosso item (a), parece ser o mais correto a se fazer:

[;4ab-1 | 16a^4b - 8a^2b +b +8a^2b-2a = 16a^4b-2a+b ;]

[; 4ab-1|16a^4b-2a+b-16a^4b +4a^3 = 4a^3-2a+b ;]

[; 4ab-1|4a^3b-2ab+b^2-4a^2b+a^2 = (a-b)^2 ;]

Ao tentar reduzir o grau do lado direito, entretanto, falhamos. Agora, o que fazer? A resposta é simples: usar o root-flipping. O nome parece estranho, mas é uma ideia natural: vejamos o que faremos:

Pela condição de divisão, temos que

$[;(a-b)^2=(4ab-1)k \Rightarrow a^2-2ab(2k+1)+b^2+k=0;]$

Agora, você já deve ter percebido o que fizemos! Vamos, é claro, considerar como uma equação do segundo grau em [;a;]

! Seja, agora, [;a,b;]

uma solução minimal da equação dada. Logo, pelas relações de Girard,

Como

são positivos, então [;a_1;]

é também solução. Se [; a > b(2k+1) ;]

, então

é menor que [;a;]

, contradizendo sua minimalidade. Logo, [;a<b(2k+1);]

. Portanto, $[;b^2+k \ge a^2 \Rightarrow k \ge a^2 -b^2;]$ (considerando, aqui, $[;a\ge b;]$ , sem perda de generalidade). Porém, sabemos que

$[;k=\frac{a^2-b^2}{4ab-1} \ge a^2-b^2;]$

Porém, isto é, por si só, uma contradição, pois o denominador é sempre maior ou igual a 3. A única maneira de não haver contradição é com [; a=b;]

, e isto termina o problema.

Vamos esclarecer ao leitor o processo acima. O root-flipping consiste em um caso particular do descenso infinito de fermat: buscamos uma equação dada, e, considerando uma solução mínima, encontramos uma menor, e isso contradiz a minimalidade da solução e, portanto, a existência de uma (pois o conjunto dos números naturais é bem ordenado, ou seja, todo subconjunto deste possui um elemento mínimo).

Basicamente, o root-flipping é achar uma equação do segundo (ou qualquer outro) grau em uma das variáveis, considerá-la mínima ou considerar algum aspecto possivelmente contraditório e, com ajuda das relações de Girard, contradizer essa minimalidade ou a propriedade contraditória, provando algo sobre a equação dada. Lendo esta definição, pode parecer um pouco vago, mas o exemplo acima mostra bem a utilidade desta ferramenta. Vejamos mais dois exemplos da descida de Fermat aliada ao root flipping:

Exemplo 4: Sejam [; a,b ;]

inteiros tais que $[;\frac{a^2+b^2+1}{ab};]$ é também inteiro. Prove que este inteiro é 3.

Resolução: Usando a técnica que acabamos de aprender, então temos que

Logo, vamos procurar uma solução com soma [;a+b;]

minimal, e mostrar que [;a=b=1;]

. De fato, [;k=3;]

neste caso. Caso $[;k\ne 3;]$ , nossa procura por uma solução com [;a>b;]

(sem perda de generalidade) se abrevia ao notarmos que $[;a_1+a_2=kb> 2y \Rightarrow a_1 \ge a_2 > b;]$ . Porém, pela relação de Girard, $[;a_1 \cdot a_2 =b^2 + 1;]$ , que contradiz claramente as desigualdades acima. Logo, $[;k \ne 3;]$ não pode acontecer, e terminamos. C.Q.D.

Exemplo 5: Sejam [;m,n ;]

inteiros positivos tais que [;m|n^2 +1;]

. Ache todos tais inteiros.

Resolução: Notemos que esta equação implica em [; nm | n^2 + m^2 +1 ;]

, que é exatamente a equação do exemplo acima. Portanto, [;3mn = n^2 + m^2 +1;]

, que implica [; (3m-n)n = m^2 +1;]

. Ou seja, se [;n;]

é solução, então [;3m-n;]

também é. Portanto, sempre podemos transformar um par [;(m,n);]

em um par

. Achamos, assim, uma cadeia ascendente de soluções, ou descendente, dependendo do ponto de vista, que para na solução mínima. Como vimos, esta é [;(n,m)=(1,1);]

. Portanto, as soluções são todas as geradas a partir desta satisfazendo a relação acima. C.Q.D.

Agora, que tal alguns exercícios para praticar o que aprendeu?

P.1 - (IMO) Ache todos os pares [; (x,y) ;]

de inteiros positivos tais que [;x^2y + x + y;]

é divisível por [;xy^2 + y+7 ;]

P.2 - (IMO) Ache todos os inteiros [;(n,m);]

tais que $[;\frac{n^3+1}{nm-1};]$ é um inteiro.

P.3 - (IMO) Sejam [;(a,b);]

inteiros tais que [;ab+1;]

divide

. Prove que $[;\frac{a^2b^2}{ab+1};]$ é um quadrado perfeito.

P.4 - Prove que, além de haver infinitos [;(a,b);]

satisfazendo que $[;\frac{a^2+b^2}{ab-1};]$ seja inteiro, esse quociente vale 5.

P.5 - (IMO) Encontre todos os inteiros positivos [;(m,n);]

tais que

$[;\frac{m^2}{2mn^2-n^3+1};]$

Também é um inteiro.

Referências Bibliográficas:

[1] - TENGAN, Eduardo; SALDANHA, Nicolau; MOREIRA, Carlos Gustavo, B. MARTINEZ, Fabio. Teoria dos Números: Um passeio com números primos e outros números familiares pelo mundo inteiro. Rio de Janeiro, RJ, Projeto Euclides, IMPA, 2010.

[2] - http://cyshine.webs.com/tres-vip.pdf. - Treinamento Para as Olimpíadas Iberoamericana e IMO.

- Questão 80 ? Concurso See ? 2.010 ? Professor De Educação Básica Ii ? Matemática
O triângulo ABC tem vértices A(0,0) e B(36,15). A respeito do vértice C, sabe-se que suas coordenadas são números inteiros. A menor área possível do triângulo ABC é (A) 1/2.(B) 1.(C) 3/2.(D) 9/2.(E) 13/2. Obs: Caderno de Prova ?E05? ? Tipo 001...

- Matemática Através De Problemas - V
Olá, pessoal! Aqui vamos apresentar mais alguns problemas interessantes, e mostrar algumas soluções pros problemas propostos da ultima vez. Problemas Propostos 1 - (OMERJ-2011) Dada uma sequência de N inteiros não-negativos $a_j$ tal...

- Equações Polinomiais Nos Inteiros
É bastante interessante pensarmos em problemas do tipo: "Ache todos os pares de inteiros que satisfaçam...". A grande questão é que muitos dos problemas são aparentemente difíceis, mas se resolvem com uma ideia bastante simples para alunos do oitavo...

- O Algoritmo Da Divisão Parte Iv [o Fim]
Esta é a última postagem da série que teve o objetivo de demonstrar o algoritmo da divisão: Se a é um número inteiro qualquer e b é um número inteiro maior do que zero, então existem dois números inteiros q e r tais...

- Por Que Podemos Somar Os Algarismos De Um Número Para Saber Se Ele é Divisível Por 3?
Todos conhecemos, desde muito cedo, um critério de divisibilidade por 3, afinal, quem é que quando precisou dividir um número por três nunca somou os seus algarismos? O que, talvez, nem todos sabemos é explicar porque este procedimento sempre funciona. Esta...

Matemática