Congruências e divisibilidade — Um Problema da Purdue University

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)

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Caderno, Congruências, Matemática, Problem, Problemas, Purdue University, Teoria dos Números com as etiquetas , , . ligação permanente.

Deixe uma Resposta

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

Logótipo da WordPress.com

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

Imagem do Twitter

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

Facebook photo

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

Google+ photo

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

Connecting to %s