Category Archive

You are currently browsing the category archive for the 'Congruências' category.

Congruências e divisibilidade — Um Problema da Purdue University

Maio 29, 2009 in Caderno, Congruências, Matemática, Problema, Teoria dos Números | Tags: Caderno, Matemática, Problema | Leave a comment

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

Exercício: provar que dois elevado a 33 mais três elevado a 33 não é primo

Janeiro 20, 2009 in Caderno, Congruências, Demonstração, Exercício, Matemática, Problema, Teoria dos Números | Tags: Caderno, Demonstração, Exercícios, Matemática, Problema | 4 comments

pdf: ver caderno

Provar que a soma de 2 elevado a 33 com 3 elevado a 33 é um número composto.

[do Vestibular da UFPE, 2008]

$\blacktriangleright$ Para $n=1+4k$ (com $k=1,2,\ldots )$ as potências $2^{n}$ e $3^{n}$ terminam (*), respectivamente, em $2$ e $3$ ; a sua soma $2^{n}+3^{n}$ termina por isso em $5.$ Ora

$2^{33}+3^{33}=2^{1+4\times 8}+3^{1+4\times 8}$

e, consequentemente, $2^{33}+3^{33}$ é divisível por $5$ , logo não é primo. $\blacktriangleleft$

$\bigskip$

(*) Por exemplo: $\mathbf{2}^{1}\mathbf{=2}$ , $2^{2}=\allowbreak 4$ , $2^{3}=\allowbreak 8$ , $2^{4}=\allowbreak 16$ , $\mathbf{2}^{5}\mathbf{=\allowbreak 32}$ , $2^{6}=\allowbreak 64$ , $2^{7}=\allowbreak 128$ , $2^{8}=\allowbreak 256$ , $\mathbf{2}^{9}\mathbf{=\allowbreak 512},\dots$

$\bigskip$

$\mathbf{3}^{1}\mathbf{=\allowbreak 3}$ , $3^{2}=\allowbreak 9$ , $3^{3}=\allowbreak 27$ , $3^{4}=\allowbreak 81$ , $\mathbf{3}^{5}\mathbf{=\allowbreak 243}$ , $3^{6}=\allowbreak 729$ , $3^{7}=\allowbreak 2187$ , $3^{8}=\allowbreak 6561$ , $\mathbf{3}^{9}\mathbf{=\allowbreak 19\,683},\dots$

Adenda de 24-4-2009:

Método alternativo: de uma forma mais rigorosa e aproveitando uma ideia desenvolvida neste artigo pode justificar-se este resultado da seguinte maneira.

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=4k+s,1\leq s\leq 3,0\leq k$

$2^{n}\equiv 2^{s}\quad\left( \text{mod }5\right) ,\quad (1)$

o que significa que os restos da divisão de $2^{n}$ por $5$ formam uma sucessão periódica de comprimento $4$ com início em $n=1$

$\overset{\text{per\'{\i}odo}}{\overbrace{2,4,3,1}},\overset{4\text{ termos}}{\overbrace{2,4,3,1}},\ldots .$

Aplicada a $3^{n}$ ( $n=4k+s,1\leq s\leq 3,0\leq k$ ) dá

$3^{n}\equiv 3^{s}\quad\left( \text{mod }5\right) ,\quad (2)$

o que significa que os restos da divisão de $3^{n}$ por $5$ formam uma sucessão periódica de comprimento $4$ com início em $n=1$

$\overset{\text{per\'{\i}odo}}{\overbrace{3,4,2,1}},\overset{4\text{ termos}}{\overbrace{3,4,2,1}},\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)$ . Em consequência de (1) e (2) obtemos

$2^n+3^n\equiv 2^{s}+3^{s}\quad \left( \text{mod }5\right) .\quad (3)$

Os restos da divisão de $2^n+3^n$ por $5$ formam outra sucessão periódica de comprimento $4$ que se inicia também em $n=1$

$\overset{\text{per\'{\i}odo}}{\overbrace{0,3,0,2}},\overset{4\text{ termos}}{\overbrace{0,3,0,2}},\ldots .$

Logo para $n$ ímpar, $2^n+3^n\equiv 2^{s}+2^{s}$ é divisível por $5$ , pelo que $2^{33}+3^{33}$ não é primo.

Ou então calcula-se simplesmente $33=4\times 8+1,s=1$ e

$2^{33}\equiv 2^{1}\quad\left( \text{mod }5\right)$

$3^{33}\equiv 3^{1}\quad\left( \text{mod }5\right)$

donde

$2^{33}+3^{33}\equiv 2^{1}+3^{1}\quad \left( \text{mod }5\right) \equiv 0\quad \left( \text{mod }5\right)$

visto que

$5 \equiv 0\quad \left( \text{mod }5\right) .$

Adenda de 4-6-2009:

Justificação de Vishal Lama: 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)$ .

	Eduardo Lazarini no Matemática, papel e caneta, e …
	mario dumbo hossi no Descobrir a Moeda Falsa
	Américo Tavares no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	Moura Mendes no Notas soltas sobre a Conferênc…
	anonimo no Dodecaedro e outros poliedros…
	Elias_Brasil no Probabilidades com cartas
	Pedro Cunha no Caderno
	Andrea no Matemática, papel e caneta, e …
	alessandro no Caderno

Category Archive

Congruências e divisibilidade — Um Problema da Purdue University

Exercício: provar que dois elevado a 33 mais três elevado a 33 não é primo

Américo Tavares

Bem-vindo(a)!

Últimos Comentários e respostas

Arquivos

Últimos Artigos

Categorias (Temas)

Acompanhamento via RSS de Blogues com Matemática

… em português

A MATEMÁTICA ANDA POR AÍ

Disquisitiones Mathematicae

Geometria

morfismo

… não portugueses

Gaussianos

Gower’s Weblog

The Unapologetic Mathematician

Todd and Vishal’s blog

What’s new

Weblog de Pierre Bernard

Ligações (Links)

Matemática

Matemática/Computação

Matemática/Problemas

Matemática/Publicações, bibliotecas online

Meu blogue auxiliar

Outros: ciências, tecnologia e economia, etc.

N.º de Visualizações (início: Out. 2007)

Acompanhe este blogue via RSS

COMENTÁRIOS