Congruências e divisibilidade — Um Problema da Purdue University

Posted on Maio 29, 2009 por Américo Tavares

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

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer

Ver todos os posts de Américo Tavares →

Esta entrada foi publicada em Caderno, Congruências, Matemática, Problem, Problemas, Purdue University, Teoria dos Números com as tags Caderno, Matemática, Problema. ligação permanente.

Deixar uma resposta Cancelar resposta

Escreva o seu comentário aqui...

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Email (obrigatório) (O endereço nunca será tornado público)

Nome (obrigatório)

Website

Está a comentar usando a sua conta WordPress.com ( Log Out / Modificar )

Está a comentar usando a sua conta Twitter ( Log Out / Modificar )

Está a comentar usando a sua conta Facebook ( Log Out / Modificar )

Cancelar

Connecting to %s

	Américo Tavares em Três quadrados e dois triângul…
	Vanderlúcio em Três quadrados e dois triângul…
	Américo Tavares em Yitang Zhang
	Américo Tavares em Livro de Terence Tao Como Reso…
	Henrique em Livro de Terence Tao Como Reso…
	Américo Tavares em Yitang Zhang
	jocimar em Problema simples resolvido sob…
	Aline em Problema simples resolvido sob…