Congruences and Divisibility — A Purdue University Problem

pdf: ver caderno

Versão portuguesa aqui

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)

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

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

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.

5 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/

  3. Adicionei a esta entrada a justificação anterior.

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