Congruências e divisibilidade — Um Problema da Purdue University [Republicação] :: Congruences and Divisibility — A Purdue University Problem [Repost]

Publicado em 6 de Março de 2019 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)$

* * *

PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series):

“ Problem. 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. ”

Here is my solution (accepted).

If $a\equiv b\quad \left( \text{mod }m\right)$ , then $a^{n}\equiv b^{n}\quad\left( \text{mod }m\right)$ . Applied to $2^{n}$ this property gives in general for $n=3k+s,1\leq s\leq 3,0\leq k$

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

which means that the remainders of the division of $2^{n}$ by $7$ form a periodic sequence of length $3$ starting at $n=1$

$\overset{\text{period}}{\overbrace{2,4,1}},\overset{3\text{ terms}}{\overbrace{2,4,1}},\ldots .$

As for $n^{2}$ since (a) if $a\equiv b\quad \left( \text{mod }m\right)$ and $c\equiv d\quad \left( \text{mod }m\right)$ , then $a+c\equiv b+d\quad \left( \text{mod }m\right)$ and (b) if $a\equiv b\quad \left( \text{mod }m\right)$ , then $a^{2}\equiv b^{2}\quad \left( \text{mod }m\right)$ , we have in general for $n=7j+r,1\leq r\leq 7,0\leq j$

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

which means that the remainders of the division of $n^{2}$ by 7 form a periodic sequence of length 7 starting at $n=1$

$\overset{\text{period}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ terms}}{\overbrace{1,4,2,2,4,1,0}},\ldots .$

If $a\equiv b\quad \left( \text{mod }m\right)$ and $c\equiv d\quad \left( \text{mod }m\right)$ , then $a-c\equiv b-d\quad \left( \text{mod }m\right)$ . Let $u_{n}=2^{n}-n^{2}.$ Therefore from (1) and (2) we have

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

The remainders of the division of $u_{n}$ by $7$ form another periodic sequence of length $21=\text{lcm}(3,7)$ which starts also at $n=1$ . Four examples of the evaluation of these remainders are presented below.

For $1\leq n\leq 21$ the following $15$ terms are not divisible by $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}$ .

Hence for $1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor$ , there are $15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140$ terms that are not divisible by $7$ .

From the remaining 4 terms $u_{9997}$ and $u_{9999}$ are not divisible by $7$ , which gives a total of $7140+2=7142$ numbers $u_{n}=2^{n}-n^{2}$ not divisible by $7$ .

Four examples of the evaluation of the remainders:

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

Editado em 12-03-2019 para acrescentar a versão original inglesa

Anúncios

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer

Ver todos os artigos de Américo Tavares →

Esta entrada foi publicada em Matemática. ligação permanente.

3 respostas a Congruências e divisibilidade — Um Problema da Purdue University [Republicação] :: Congruences and Divisibility — A Purdue University Problem* [Repost]*

Antonio Ferrao diz:

6 de Março de 2019 às 23:22

Quase um ano de intervalo, mas continua vivo este blog.

Responder
- Américo Tavares diz:
  
  6 de Março de 2019 às 23:24
  
  É bem verdade, António Ferrão!
- Américo Tavares diz:
  
  7 de Março de 2019 às 10:03
  
  Obrigado pela sua visita!

Deixe uma Resposta Cancelar resposta

Insira aqui o seu comentário...

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

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

Nome (obrigatório)

Site da Web

Está a comentar usando a sua conta WordPress.com ( Terminar Sessão / Alterar )

Está a comentar usando a sua conta Google ( Terminar Sessão / Alterar )

Está a comentar usando a sua conta Twitter ( Terminar Sessão / Alterar )

Está a comentar usando a sua conta Facebook ( Terminar Sessão / Alterar )

Cancelar

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

	aline em Problemas: determinar dois núm…
	Nietzsche em Desigualdade de Cauchy-Schwarz
	sempseudoliberdade em A Matemática é uma Ciência? ::…
	Américo Tavares em A sample of some contributions…
	Paulo Estevão Pauli em Conjectura de Collatz ou probl…
	Américo Tavares em Congruências e divisibilidade…
	Américo Tavares em Congruências e divisibilidade…
	Antonio Ferrao em Congruências e divisibilidade…
	Congruências e divis… em Congruences and Divisibility…
	Leandro Tezoto em LaTeX – matrizes…