Category Archive

You are currently browsing the category archive for the 'Teoria dos Números' category.

Indução matemática

Setembro 15, 2009 in Exercício, Indução matemática, Matemática, Matemática Gerais, Teoria dos Números | Tags: Exercícios, Matemática | Leave a comment

Reuno aqui, para comodidade de leitura, algumas entradas já publicadas sobre o princípio da indução matemática.

§1. Por este princípio, a demonstração da veracidade de uma determinada proposição matemática $p\left( n\right)$ para todos os inteiros $n\geq n_{0}$ , comporta dois passos:

(1) Verifica-se a sua validade para um dado valor inteiro $n_{0}$ (normalmente, 0 ou 1) da variável de indução $n$ .

(2) Assume-se que é válida para o inteiro $n$ e demonstra-se que é também válida para $n+1,$ isto é, que $p\left( n\right)\implies p\left( n+1\right)$ .

$\bigskip$

Vamos demonstrar de seguida o Teorema Binomial por este princípio.

Teorema: Para todo o valor de $n$ natural, tem-se

$\left( 1+x\right) ^{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}$

qualquer que seja o valor real de $x.$

$\bigskip$

Demonstração:

O teorema verifica-se para $n=0:$ $\displaystyle\sum_{k=0}^{0}\dbinom{0}{k}x^{k}=\dbinom{0}{0}x^{0}=1$ e $\left( 1+x\right) ^{0}=1,$ logo $\left( 1+x\right) ^{0}=\displaystyle\sum_{k=0}^{0}\dbinom{0}{k}x^{k}.$ Admitimos agora que o teorema é válido para $n,$ isto é, que $\left( 1+x\right)^{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}$ e demonstremos que o é igualmente para $n+1.$ Como $\left( 1+x\right) ^{n+1}=\left( 1+x\right) \left(1+x\right) ^{n},$ vem

$\left( 1+x\right) ^{n+1}=\left( 1+x\right) \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}$ $=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k}x^{k+1}.$

Manipulamos o segundo membro (lado direito) até obter $\displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k}.$ De facto,

$\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k}x^{k+1}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\displaystyle\sum_{k=1}^{n+1}\dbinom{n}{k-1}x^{k}$ $=\dbinom{n}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k-1}x^{k}\right) +\dbinom{n}{n}x^{n+1}$ $=\dbinom{n+1}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n+1}{k}x^{k}\right) +\dbinom{n+1}{n+1}x^{n+1}$

pela identidade de Pascal e porque

$\dbinom{n+1}{0}=\dbinom{n}{0}=\dbinom{n+1}{n+1}=\dbinom{n}{n}=1.$

Mas, como

$\dbinom{n+1}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n+1}{k}x^{k}\right) +\dbinom{n+1}{n+1}x^{n+1}$ $=\displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k}$

provámos, como pretendíamos, que $\left( 1+x\right)^{n+1}=\displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k},$ e assim acabámos a demonstração. $\qquad \blacksquare$

$\bigskip$

A partir do desenvolvimento de $\left( 1+x\right) ^{n}$ deduz-se imediatamente o de $\left( x+y\right) ^{n}.$

$\bigskip$

Corolário: Quaisquer que sejam os reais $x$ e $y$ e o natural $n$ é válida a fórmula

$\left( x+y\right) ^{n}=\displaystyle \sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}.$

$\bigskip$
Demonstração: Admitamos que $y\neq 0:$

$\left( x+y\right) ^{n}=y^{n}\left( 1+\frac{x}{y}\right)^{n}=y^{n}\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\left( \frac{x}{y}\right)^{k}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}$ .

Como

$\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}=\displaystyle\sum_{k=0}^{n-1}\dbinom{n}{k}x^{k}y^{n-k}+\dbinom{n}{n}x^{n}y^{0}$ ,

para $y=0,$ tem-se

$\left( x+y\right)^{n}=x^{n}$

$\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}=x^n=\left( x+y\right) ^{n}$

ou seja a fórmula ainda é válida $\qquad \blacksquare$ .

§2. O Princípio de indução matemática é o seguinte axioma de Peano:

Se o conjunto A, contido em N, for tal que 1 pertence a A e n+1 pertence igualmente a A sempre que n seja elemento de A, então A = N. [N aqui é o conjunto dos naturais 1, 2, 3, ... ].

Uma propriedade P diz-se hereditária quando, sendo verdadeira para o inteiro n, é também verdadeira para o sucessor de n (n+1).

Assim, o Princípio de Indução equivale a afirmar que uma dada proposição, verdadeira para n=1 e hereditária, implica que seja verdadeira para todos os naturais 1, 2, 3, … .

Por isso, a aplicação deste método comporta as duas etapas (ou passos) conhecidos

Demonstração de que uma dada proposição é válida para n=1. (Caso Base).
Demonstração de que a proposição é hereditária. (Etapa de Indução).

Este princípio nada ou quase nada tem a ver com o método de indução próprio das ciências naturais, que se caracteriza por se estabelecer uma lei geral observando a repetição do mesmo fenómeno em inúmeros casos particulares.

§3. Nem todas as provas por indução têm o mesmo grau de dificuldade. Enquanto a do 1º. exemplo é 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)$

$\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}$

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

§ 4. Exercício 1: prove que existe apenas um número natural que verifica a relação

$^{n\!}C_{n-2}=2^{n-2}-1$

Sugestão: utilize o princípio de indução para provar que a relação não é satisfeita por nenhum natural superior a seis.

Esta ideia é devida a Vishal Lama (neste comentário em inglês).

§ 5. Exercício 2: podemos demonstrar que

$\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }\qquad n=1,2,3,\ldots .$

De facto substituindo em

$\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }$

$n$ por $1$ , ficamos com

$\Gamma \left(1+\dfrac{1}{2}\right)=\Gamma \left( \dfrac{3}{2}\right) =\dfrac{1}{2^{1}}\sqrt{\pi }=\dfrac{1}{2}\sqrt{\pi }$ ,

que vemos ser verdadeiro, visto que da equação funcional da função gama

$\Gamma \left( x+1\right) =x\Gamma \left( x\right)$

se obtém, para $x=\dfrac{1}{2}$

$\Gamma \left( 1+\dfrac{1}{2}\right) =\dfrac{1}{2}\Gamma \left( \dfrac{1}{2}\right) =\dfrac{1}{2}\sqrt{\pi }$ .

Admitimos agora que

$\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }$

e fazemos, na equação funcional, $x=n+\dfrac{1}{2}$ . Como vem sucessivamente

$\Gamma \left( n+1+\dfrac{1}{2}\right) =\left( n+\dfrac{1}{2}\right) \Gamma\left( n+\dfrac{1}{2}\right) =\left( n+\dfrac{1}{2}\right) \dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }$

$=\dfrac{2n+1}{2}\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }=\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) \left( 2n+1\right) }{2^{n+1}}\sqrt{\pi }$

$=\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) \left[ 2\left( n+1\right) -1\right] }{2^{n+1}}\sqrt{\pi }$

demonstra-se desta forma o passo de indução. $\blacktriangleleft$

Congruências e divisibilidade — Um Problema da Purdue University

Maio 29, 2009 in Caderno, Congruências, Matemática, Problema, Teoria dos Números | Tags: Caderno, Matemática, Problema | Leave a comment

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

Princípio de indução matemática aplicado a uma relação combinatória

Março 15, 2009 in Combinatória, Indução matemática, Matemática, Problema, Teoria dos Números | Tags: Matemática, Problema | Leave a comment

Prove que existe apenas um número natural que verifica a relação

$^{n\!}C_{n-2}=2^{n-2}-1$

Sugestão: utilize o princípio de indução para provar que a relação não é satisfeita por nenhum natural superior a seis.

Esta ideia é devida a Vishal Lama (neste comentário em inglês).

Dígitos de um número inteiro positivo na base factorial

Março 5, 2009 in Computação, Demonstração, Matemática, Teoria dos Números | Tags: Matemática, Computação, Demonstração | 8 comments

Suscitado pela ideia do leitor António Ferrão, acrescentei o ponto 7 ao meu artigo a propósito de 123456. Por considerar que merece ser autonomizado, e para não alongar esse artigo, republico agora esse tema com adaptações de exposição. A parte principal deve-se a Jacques Glorieux.

Trata-se de saber como se pode decompor em factoriais o inteiro positivo $n$ .

Uma possível decomposição é

$n=f_k\times k!+f_{k-1}\times (k-1)!+\dots+f_2\times 2!+f_1\times 1!$

que é única, se se considerarem os maiores factoriais possíveis; uso a notação

$(f_k,f_{k-1},\dots,f_2,f_1)_{k!}$

para me referir à sucessão que a cada $n$ faz corresponder os $k$ inteiros obtidos por este método. Esta sucessão está registada na The On-line Encyclopedia of Integer Sequences com a identificação A108731 (autor: Frank Adams-Watters). Começa por

$1,1,0,1,1,2,0,\dots,$

visto que $1=(1)_{1!}$ , $2=(1,0)_{2!}$ , $3=(1,1)_{2!}$ , $4=(2,0)_{2!},\dots$ .

O desenvolvimento de $n$ na forma indicada — que aparece no livro de Donald Knuth, The Art of Computer Programming, Vol II, p. 192, como me chamou a atenção António Ferrão — é, como disse, único.

$\bigskip$

Apresento a seguir uma tradução da demonstração de Jacques Glorieux da seguinte

$\bigskip$

Proposição. Seja $n$ be um inteiro positivo. A decomposição

$n=f_{k}\times k!+f_{k-1}\times (k-1)!+\cdots +f_{2}\times 2!+f_{1}\times 1!\qquad (1)$

é única se admitirmos que $k!, (k-1)!,\dots$ têm os maiores valores possíveis, a começar por $k!$ e continuando no sentido decrescente.

Demonstração. Baseia-se no teorema do qual depende o algoritmo da divisão, a saber:

“Dados os inteiros $a$ e $b$ com $b>0$ existem dois únicos inteiros $q$ e $r$ , com $0\leq r<b$ tais que $a=bq+r$ “

Admitamos que $k$ é o maior inteiro tal que $k!\leq n$ .

Então se dividirmos $n$ por $k!$ e se designarmos o quociente por $f_{k}$ , temos:

$n=f_{k}\times k!+r_{k}$ , em que $r_{k}$ designa o resto da divisão ( $0\leq r_{k}<k!$ )

Distinguimos dois casos:

1. $r_{k}=0$

Neste caso, $n=f_{k}\times k!$ . O desenvolvimento de $n$ indicado em $(1)$ está certo e é único. Temos $f_{k-1}=f_{k-2}=\dots =f_{1}=0$

2. $r_{k}>0$

Neste caso, denotemos por $m$ o menor inteiro tal que

$(k-m-1)!\leq r_{k}$ ( $m=0,1,...,k-2$ )

Dividamos $r_{k}$ por $(k-m-1)!$ : temos

$r_{k}=f_{k-m-1}\times (k-m-1)!+r_{k-m-1}$

(com $0\leq r_{k-m-1}<(k-m-1)!$ ).

Assim $n=f_{k}\times k!+f_{k-m-1}\times (k-m-1)!+r_{k-m-1}$

que se pode escrever

$n=f_{k}\times k!+f_{k-1}\times (k-1)!+\dots$

$\dots +f_{k-m}\times (k-m)!+f_{k-m-1}\times (k-m-1)!+r_{k-m-1}$

com $f_{k-1}=\dots =f_{k-m}=0$

Podemos prosseguir da mesma maneira até chegarmos a:

$r_{2}=f_{1}\times 1!+r_{1}$ (tem-se $r_1=0$ , uma vez que $0\leq r_{1}<1!$ ).

Provámos desta forma que:

$n=f_{k}\times k!+f_{k-1}\times (k-1)!+\cdots +f_{2}\times 2!+f_{1}\times 1!$

Esta decomposição de $n$ é única, visto que os coeficientes $f_{k}$ são determinados também de forma única pelo algoritmo da divisão. $\qquad\square$

No meu artigo “linkado” acima poderá ver também o texto em inglês.

Entre $n,k$ e $f_k$ verificam-se as seguinte relações, uma prova das quais se deve também a Jacques Glorieux:

$0\leq f_k\leq k\leq k!\leq n<(k+1)!$

Se algum leitor interessado conseguir estabelecer relações mais fortes do que estas, seria certamente útil para definir melhor o comportamento da sucessão.

Adenda de 6-3-2009

Uma interpretação informal poderá ser:

Vejamos o exemplo 123456=3×8!+3×6!+2×5!+4×4! . 123456 pode ter outras decomposições: por exemplo

123456=123456×1!

Mas se nos restringirmos ao máximo factorial menor ou igual a 123456, encontramos 8!=40320 (9!= 362880>123456).

Agora subtraímos 8! de 123456:

123456-8!= 83136

Prosseguimos de forma semelhante:

    83136-8!= 42816
    42816-8!= 2496
    2496-6!= 1776
    1776-6!= 1056
    1056-6!= 336
    336-5!= 216
    216-5!= 96
    96-4!= 72
    72-4!= 48
    48-4!= 24
    24-4!= 0

Donde 123456=3×8!+3×6!+2×5!+4×4!.

O caso geral é uma generalização deste procedimento.

É similar a 123456 na base 10

123456-100000=23456

    23456-10000=13456
    13456-10000=3456
    3456-1000=2456
    2456-1000=1456
    1456-1000=456

    456-100=356
    356-100=256
    256-100=156
    156-100=56

    56-10=46
    46-10=36
    36-10=26
    26-10=16
    16-10=6

    6-1=5
    5-1=4
    4-1=3
    3-1=2
    2-1=1
    1-1=0

Donde 123456=1×100000+2×10000+3×1000+4×100+5×10+6×1.

[7-3-2009: corrigi erro na primeira decomposição, em resposta ao 1º. comentário]

Propriedades aritméticas ilustradas por 123456. Será um número interessante?

Fevereiro 22, 2009 in Blogue, Estatísticas, Exercício, Matemática, Teoria dos Números | Tags: Blogue, Exercícios, Matemática | 2 comments

123456

A propósito do número de visitas deste blogue — o contador do WordPress passou hoje por 123456 — lembrei-me de ver se descobria algo de interessante nele. Por exemplo:

1 - Quantos divisores admite?

Para respondermos a esta questão sem os indicar explicitamente, podemos recorrer a um teorema da aritmética racional (ou teoria dos números) cujo enunciado é:

O número de divisores do inteiro $n$ é a função aritmética $d(n)$ cuja expressão analítica é

$d(n)=(e_1+1)(e_2+1)\cdots (e_k+1)$

em que $e_1,e_2,\dots , e_k$ são os expoentes da decomposição factorial em números primos de $n$

$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

Então, como

$123456=2^6\times 3\times 643$

o número de divisores de $123456$ é

$d(123456)=(6+1)(1+1)(1+1)=28$

2 - Como se escreve na base 6?

Como

$123456=0+2\times 6+3\times 6^2+1\times 6^3+5\times 6^4+3\times 6^5+2\times 6^6$

tem-se

$(2351320)_6=(123456)_{10}$

Penso acrescentar mais exemplos, no futuro, aqui. São quase 23h30m e pretendo “postar” ainda hoje.

(Continuação, 23-2-2009)

3 - Quais são os maiores números de Fibonacci de que é soma?

Ora, como

$123456=121393+1597+377+55+21+13$

$=x_{26}+x_{17}+x_{14}+x_{10}+x_{8}+x_{7}$

em que

$x_{n}=\dfrac{\left( \dfrac{1+\sqrt{5}}{2}\right) ^{n}-\left( \dfrac{1-\sqrt{5}}{2}\right) ^{n}}{\sqrt{5}}$

é o número de Fibonacci de ordem $n$ , os números são precisamente $x_{26},x_{17},x_{14},x_{10},x_{8},x_{7}$ .

4 - Em quantos modos diferentes se pode decompor num produto de factores primos ente si?

Atendendo a que há $3$ potências ( $2^6,3,643$ ) na sua decomposição em primos, a resposta é $2^{3-1}=4$ , e que são:

$123456=1\times 123456$

$123456=2^6\times (3\times 643)=64\times 1929$

$123456=(2^6\times 3)\times 643)=192\times 643$

$123456=(2^6\times 643)\times 3=41152\times 3$

(Continuação, 24-2-2009)

5 - Qual é o resto da divisão inteira do seu cubo por 7?

Sem fazer a conta na calculadora, podemos utilizar propriedades das congruências, para chegar ao resultado.

Notação e definição: $a\equiv b\; (\mod m)$ , que se lê $a$ é congruente com $b$ para o módulo $m$ , significa que $a-b$ é um múltiplo de $m$ (com $a,b,c$ inteiros).

Ora, $64\times 1929=123456$ , $64\equiv 1\;\left( \mod 7\right)$ e $1929\equiv 4\;\left( \mod 7\right)$ . Pela propriedade da relação de congruência que diz que

se $a\equiv b\;\left( \mod m\right)$ e $b\equiv d\;\left( \mod m\right)$ , então $ac\equiv bd\;\left( \mod m\right)$

vem

$123456=$ $64\times 1929\equiv 1\times 4\;\left( \mod 7\right) =4\;\left( \mod 7\right)$

e por outra propriedade, a que diz que

se $a\equiv b\;\left( \mod m\right)$ , então $a^{n}\equiv b^{n}\;\left( \mod m\right)$

tem-se

$123456^{3}\equiv 4^{3}\;\left( \mod 7\right) =64\;\left( \mod 7\right)$

E como $64\equiv 1\;\left( \mod 7\right)$ , pela propriedade transitiva da relação de congruência

se $a\equiv b\;\left( \mod m\right)$ e $b\equiv c\;\left( \mod m\right)$ , então $a\equiv c\;\left( \mod m\right)$

conclui-se que

$123456^{3}\equiv 1\;\left( \mod 7\right)$

pelo que o resto é $1.$

(Continuação, 25-2-2009)

6 - Qual é a soma dos seus divisores?

Sabendo-se a factorização em primos de um número $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ a soma dos seus divisores é dada por

$\dfrac{p_{1}^{^{e_{1}+1}}-1}{p_{i}-1}\times \dfrac{p_{2}^{e_{2}+1}-1}{p_{2}-1}\times \cdots \times \dfrac{p_{k}^{e_{k}+1}-1}{p_{k}-1}$

No caso de $123456=2^{6}\times 3\times 643$ será

$\dfrac{2^{7}-1}{1}\times \dfrac{3^{2}-1}{2}\times \dfrac{643^{2}-1}{642}=327152$

Read the rest of this entry »

	Américo Tavares no Optimização por método general…
	Allyne no Optimização por método general…
	Américo Tavares no Optimização por método general…
	Allyne no Optimização por método general…
	Eduardo Lazarini no Matemática, papel e caneta, e …
	mario dumbo hossi no Descobrir a Moeda Falsa
	Américo Tavares no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	anonimo no Dodecaedro e outros poliedros…

Category Archive

Indução matemática

Congruências e divisibilidade — Um Problema da Purdue University

Princípio de indução matemática aplicado a uma relação combinatória

Dígitos de um número inteiro positivo na base factorial

Propriedades aritméticas ilustradas por 123456. Será um número interessante?

Américo Tavares

Bem-vindo(a)!

Últimos Comentários e respostas

Arquivos

Últimos Artigos

Categorias (Temas)

Acompanhamento via RSS de Blogues com Matemática

… em português

A MATEMÁTICA ANDA POR AÍ

Disquisitiones Mathematicae

Geometria

morfismo

… não portugueses

Gaussianos

Gower’s Weblog

The Unapologetic Mathematician

Todd and Vishal’s blog

What’s new

Weblog de Pierre Bernard

Ligações (Links)

Matemática

Matemática/Computação

Matemática/Problemas

Matemática/Publicações, bibliotecas online

Meu blogue auxiliar

Outros: ciências, tecnologia e economia, etc.

N.º de Visualizações (início: Out. 2007)

Acompanhe este blogue via RSS

COMENTÁRIOS