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

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

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. For how many positive integers $x\leq 10,000$ is $2^{x}-x^{2}$ not divisible by $7$?

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

## Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer