Problemas Teoremas

Maio 29, 2009

Congruências e divisibilidade — Um Problema da Purdue University

Filed under: Caderno,Congruências,Matemática,Problem,Problemas,Purdue University,Teoria dos Números — Américo Tavares @ 10:15 am
Tags: , ,

pdf: ver caderno

Versão portuguesa da entrada “Congruences and Divisibility– A Purdue University Problem“

Tradução do enunciado do Problema original [PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series)]:

« Para quantos inteiros positivos x\leq 10000 é que  2^{x}-x^{2} não é divisível por 7?

Justifique a sua resposta sem utilizar o computador. »

“For how many positive integers x\leq 10,000 is 2^{x}-x^{2} not divisible by 7?

Justify your answer without the use of computers.”

Eis a tradução da  minha resolução (aceite):

Se a\equiv b\quad \left( \text{mod }m\right) , então a^{n}\equiv b^{n}\quad\left( \text{mod }m\right) . Esta propriedade aplicada a 2^{n} dá em geral, para n=3k+s,1\leq s\leq 3,0\leq k

2^{n}\equiv 2^{s}\quad\left( \text{mod }7\right) ,\quad (1)

o que significa que os restos da divisão de  2^{n} por 7 formam uma sucessão periódica de comprimento 3 com início em n=1

\overset{\text{per\'{\i}odo}}{\overbrace{2,4,1}},\overset{3\text{ termos}}{\overbrace{2,4,1}},\ldots .

Quanto a n^{2}, dado que: a) se a\equiv b\quad \left( \text{mod }m\right) e c\equiv d\quad \left( \text{mod }m\right) , então a+c\equiv b+d\quad \left( \text{mod }m\right) e b) se a\equiv b\quad \left( \text{mod }m\right) , então a^{2}\equiv b^{2}\quad \left( \text{mod }m\right) , temos em geral, para n=7j+r,1\leq r\leq 7,0\leq j

n^{2}\equiv r^{2}\quad\left( \text{mod }7\right)\quad (2)

o que quer dizer que os restos da divisão de n^{2} por 7 formam uma sucessão  periódica  de comprimento 7 que começa em n=1

\overset{\text{per\'{\i}odo}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ termos}}{\overbrace{1,4,2,2,4,1,0}},\ldots .

Se a\equiv b\quad \left( \text{mod }m\right) e c\equiv d\quad \left( \text{mod }m\right) , então a-c\equiv b-d\quad \left( \text{mod }m\right) . Seja u_{n}=2^{n}-n^{2}. Em consequência de (1) e (2) obtemos

u_{n}\equiv 2^{s}-r^{2}\quad \left( \text{mod }7\right) .\quad (3)

Os restos da divisão de  u_{n} por 7 formam outra sucessão periódica de comprimento 21=\text{mmc}(3,7) que se inicia também em n=1. Apresentamos abaixo quatro exemplos da determinação destes restos.

Para 1\leq n\leq 21 os seguintes 15 termos não são divisíveis por 7:

u_{1},u_{3},u_{7},u_{8},u_{9},u_{11},u_{12},u_{13},u_{14},u_{16},u_{17},u_{18},u_{19},u_{20},u_{21}.

Assim para 1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor , há 15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140 termos que não são divisíveis por 7.

Dos restantes 4 termos u_{9997} e u_{9999}  não são divisíveis por 7, o que dá um total de 7140+2=7142 números u_{n}=2^{n}-n^{2} não divisíveis por 7.

Quatro exemplos do cálculo dos restos:

u_{9}=2^{9}-9^{2}

(9=3\times 2+3,s=3,9=7\times 1+2,r=2)

2^{9}\equiv 2^{3}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

9^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9}\equiv 2^{3}-2^{2}\quad\left(\text{mod }7\right) \equiv -3\quad\left(\text{mod }7\right)

u_{10}=2^{10}-10^{2}

(10=3\times 3+1,s=1,10=7\times 1+3,r=3)

2^{10}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

10^{2}\equiv 3^{2}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

u_{10}\equiv 2^{1}-3^{2}\quad\left( \text{mod }7\right)\equiv 0\quad\left( \text{mod }7\right)

u_{9997}=2^{9997}-9997^{2}

(9997=3\times 3332+1,s=1,9997=7\times 1428+1,r=1)

2^{9997}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

9997^{2}\equiv 1^{2}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

u_{9997} \equiv 2^{9997}-9997^{2}\quad \left( \text{mod}7\right) \equiv 1\quad \left( \text{mod }7\right)

u_{9998}=2^{9998}-9998^{2}

(9998=3\times 3332+2,s=2,9998=7\times 1428+2,r=2)

2^{9998}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

9998^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9998} \equiv 2^{9998}-9998^{2}\quad \left( \text{mod}7\right) \equiv 0\quad \left( \text{mod }7\right)

Maio 9, 2009

Uma aplicação interessante do teorema de Rolle

Filed under: Análise Matemática,Cálculo,Matemática,Teorema / Teoria — Américo Tavares @ 3:15 pm
Tags:

Admitamos que uma dada função  real f é  contínua no intervalo \left[ a,b\right] e diferenciável em \left] a,b\right[ . Pelo teorema de Rolle, se f(a)=f(b), existe um ponto c\in\left] a,b\right[ tal que f^{\prime}(c)=0. Como é sabido a interpretação geométrica é  que entre os pontos \left( a,f(a)\right) e \left( b,f(b)\right) do gráfico de f há  pelo menos uma tangente horizontal. Por exemplo, consideremos a função f(x)=x^{2}-1 no intervalo \left[ -1,1\right] . Neste caso, em que f(-1)=f(1)=0 e as condições da hipótese do teorema se verificam, deve haver um c\in\left] -1,1\right[ tal que f^{\prime }(c)=0. Como f^{\prime }(x)=2x vemos que c=0 .

Antes de expor a aplicação em toda a sua generalidade, vejamos primeiro duas situações particulares. Uma, com g(x)=x^{2}-1 e f(x)=g(x)e^{-3x}. Continua a ser f(-1)=f(1)=0. Mas

f^{\prime }(x)=g^{\prime }(x)e^{-3x}-3g(x)e^{-3x}=\left[ g^{\prime }(x)-3g(x)\right] e^{-3x}

Pelo mesmo teorema existe algum ponto c em \left] -1,1\right[ onde f^{\prime }(c)=0. Como e^{-3x}\neq 0, c deve ser a raiz de

g^{\prime }(c)-3g(c)=0

Podemos dar uma interpretação gráfica a este resultado: há pelo menos um ponto entre \left( -1,g(-1)\right) e \left( 1,g(1)\right) do gráfico de g cuja tangente tem um declive igual ao triplo do valor de g nesse ponto. Para esta função g esse ponto é facilmente calculável

g^{\prime }(c)-3g(c)=0\Leftrightarrow 2c-3\left( c^{2}-1\right) =0\Leftrightarrow c=\dfrac{1}{3}-\dfrac{1}{3}\sqrt{10}

\bigskip

rolleex

\bigskip

Generalizando um pouco, se g(x)=x^{2}-1 e alterarmos f(x) para

f(x)=g(x)e^{-kx}\qquad k\in\mathbb{R}

obtemos c\in \left] -1,1\right[ tal que

g^{\prime }(c)-kg(c)=0

Finalmente eis a aplicação de maior generalidade, cuja  forma  de resolução é a sugerida na Referência.

Seja g  uma função real definida em \left[ a,b\right] e diferenciável em \left] a,b\right[ ; se g(a)=g(b)=0, então qualquer que seja o real k, existe um ponto c\in \left] a,b\right[   tal que

g^{\prime }(c)=kg(c).

\blacktriangleright Consideremos um k\in\mathbb{R} arbitrário e a função f(x)=g(x)e^{-kx}. Como e^{-kx} não se anula qualquer que seja o real x, os zeros de g(x) são  os de f(x), o que nos permite afirmar que f(a)=f(b)=0.

Sendo g diferenciável em \left] a,b\right[ , é contínua neste intervalo, pelo que f também é contínua e diferenciável para todo o x\in \left] a,b\right[ , logo verificam-se as condições de aplicação à  função  f do teorema de Rolle. Assim existe um ponto c em \left] a,b\right[ onde f^{\prime }(c)=0. Mas a derivada de f(x) é a função

f^{\prime }(x)=g^{\prime }(x)e^{-kx}-kg(x)e^{-kx}

donde, pelo mesmo motivo atrás indicado em relação  aos zeros de g(x) e de f(x), haverá um zero de f^{\prime }(c)

f^{\prime }(c)=g^{\prime }(c)e^{-kc}-kg(c)e^{-kc}=\left( g^{\prime }(c)-kg(c)\right) e^{-kc}

que ocorre quando

g^{\prime }(c)-kg(c)=0

o que justifica a afirmação enunciada. \blacktriangleleft

O k é  arbitrário, o que nos permite apenas afirmar que qualquer que seja k\in\mathbb{R} existe um c\in \left] a,b\right[ tal que f^{\prime }(c)=kf(c), sem saber em geral a relação entre c e k. A interpretação  geométrica deste resultado é  a de que no gráfico de uma função g, nas condições enunciadas, há pelo menos um ponto entre \left( a,g(a)\right) e \left( b,g(b)\right) cuja tangente tem um declive que é  um múltiplo  arbitrário do valor de g nesse ponto.

Nota: informaram-me que a aplicação apresentada será  um exercício de Curso de Análise, vol.1, de Elon Lages Lima.

Maio 4, 2009

Exemplos de diferente dificuldade do método de indução matemática

Filed under: Exercícios Matemáticos,Indução matemática,Matemática,Matemáticas Gerais — Américo Tavares @ 10:11 pm
Tags: ,

Neste blogue  já descrevi e utilizei o método de indução  matemática em certas demonstrações. Nesta entrada apresento dois novos exemplos, ilustrativos de que nem todas as provas por indução têm o mesmo grau de dificuldade. Enquanto a do 1º.  é  extremamente simples e natural, a do 2º.  obtive-a após tentativas, recorrendo a uma identidade algébrica auxiliar — a ser usada no passo de indução — cuja demonstração  me pareceu mais simples do que a identidade inicialmente apresentada, que pode ser deduzida a partir da regra de Ruffini de divisão de um polinómio em x, de grau n, por x-\alpha .

Exemplo 1: prove por indução  matemática

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

Para n=1 a igualdade verifica-se:

\dfrac{1}{2}=1-\dfrac{1}{2}

Admite-se que se verifica para n

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

e prova-se que nesse caso também se verifica para n+1, ou seja, devemos chegar a

\displaystyle\sum_{k=1}^{n+1}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n+1}}

Vejamos: se

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

então, somando \dfrac{1}{2^{n+1}} a ambos os membros da igualdade e simplificando o segundo membro, deduzimos sucessivamente

\left( \displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}\right) +\dfrac{1}{2^{n+1}} =1-\dfrac{1}{2^{n}}+\dfrac{1}{2^{n+1}}=1-\left( \dfrac{1}{2^{n}}-\dfrac{1}{2^{n+1}}\right) =1-\dfrac{1}{2^{n+1}}

Ora, como

\displaystyle\sum_{k=1}^{n+1}\dfrac{1}{2^{k}}=\left( \sum_{k=1}^{n}\dfrac{1}{2^{k}}\right) +\dfrac{1}{2^{n+1}}

provámos deste modo que a igualdade se verifica para qualquer inteiro n\geq 1.

Exemplo 2: se n for um inteiro positivo, prove

a^{n}-b^{n}=\left( a-b\right) \displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}

Para n=1, temos a^{1}-b^{1}=\left( a-b\right) \displaystyle\sum_{k=0}^{1-1}a^{k}b^{1-1-k}=a-b.

Antes de aplicar a hipótese de indução, a ideia fundamental consiste em mostrar a validade da identidade auxiliar

\left( a^{n}-b^{n}\right) P(n+1)=\left( a^{n+1}-b^{n+1}\right) P(n)\qquad (\ast )

em que

P(n)=\displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}.

De facto

\left( a^{n}-b^{n}\right) P(n+1)=\left( a^{n}-b^{n}\right) \displaystyle\sum_{k=0}^{n}a^{k}b^{n-k}

=\left( \displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}\right) -\left( \displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}\right)

e

\left( a^{n+1}-b^{n+1}\right) P(n)=\left( a^{n+1}-b^{n+1}\right) \displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}

=\left( \displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}\right) -\left( \displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}\right)

Mas

\displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}=a^{n}b^{n}+\displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}

e

\displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}=a^{n}b^{n}+\displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}

Subtraindo membro a membro, vem

\left( \displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}\right) -\left( \displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}\right)

=\left( \displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}\right) -\left( \displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}\right)

pelo que fica provada a identidade (\ast ) da qual se tira

a^{n+1}-b^{n+1}=\dfrac{a^{n}-b^{n}}{P(n)}P(n+1)

Assim, admitindo que

a^{n}-b^{n}=\left( a-b\right) P(n)

resulta que

a^{n+1}-b^{n+1}=\dfrac{\left( a-b\right) P(n)}{P(n)}P(n+1)

=\left( a-b\right) P(n+1)

=\left( a-b\right) \displaystyle\sum_{k=0}^{n}a^{k}b^{n-k}

como se queria mostrar.

Veja aqui um exercício sobre este método.

Tema: Rubric. Blog em WordPress.com.