## Congruences and Divisibility — A Purdue University Problem

Versão portuguesa aqui

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

Remark: typos corrected. [In the 2nd. last paragraph before the examples: “there are”  added]

Edited: May 29, 2009: Portuguese version removed and posted here

Anúncios

## Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Congruences, Math, Number Theory, Problem, Purdue University com as etiquetas , . ligação permanente.

### 6 respostas a Congruences and Divisibility — A Purdue University Problem

1. Américo,

Congrats! It’s good to see that your solution was accepted. Keep the problems coming.

2. Could we just say that $a^n + b^n$ is divisible by $a + b$ for all odd $n$, and hence, $2^{33} + 3^{33}$ is divisible by 5?

Indeed, $b \equiv -a \quad (\mod a+b)$, and so, $b^n \equiv -a^n \quad (\mod a+b)$ for odd $n$. Therefore, $a^n + b^n \equiv 0 \quad (\mod a+b)$.

[copied from a comment to 2^33+3^33 (“Cálculos Auxiliares”)]
http://calcauxprobteor.wordpress.com/2009/05/23/233333/

• NELSON diz: