Problemas Teoremas

Abril 24, 2009

Congruences and Divisibility — A Purdue University Problem

Filed under: Congruences,Math,Number Theory,Problem,Purdue University — Américo Tavares @ 12:59 pm
Tags: ,

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

Tema: Rubric. Blog em WordPress.com.