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

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

 

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Caderno, Congruências, Demonstração, Exercícios Matemáticos, Matemática, Problemas, Teoria dos Números com as etiquetas , , , , , . ligação permanente.

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

  1. Curiosa periodicidade das potências de 2 e de 3, com exactamente o mesmo período (4). Depois da demonstração feita, apeteceu-me bater com a cabeça na parede. Como sempre, as questões só são fáceis para quem sabe. Mais uma vez, Américo me surpreendeu.
    O mundo apresenta-se igual para todos, mas só quem pensa repara nas suas subtilezas…

  2. Foi um pedido que recebi do Brasil. De início não sabia como lhe pegar; quando vi a questão da periodicidade disse para mim: mas isto é fácil!
    É uma das tais facilidades (ou dificuldades?) ilusórias.

    PS. 24-4-2009: a determinação dos restos das potências dos inteiros módulo m é um tema clássico da aritmética racional!

  3. Edson diz:

    good morning can you explain me this congruencia modulo m:

    I don’t understood how: 2^2002 for 101…
    the resolution it is: 2^7=27 (mod 101)
    ==> 2^14=729=22 (mod 101)
    ==> 2^28=484=-21 (mod 101)
    ==> 2^56=441=-64=-2^6 (mod 101)
    ==> 2^56=-1 (mod 101)
    and then solution is:
    2^2002=2^(50*40+2)=(2^50)^40*2^2
    =(-1)^40*2^2=4 (mod 101)…
    resulted 2^2002 for 101 is 4 explain me the all procediment please help me

    • Here is a possible explanation

      (1) Since 2^{7}=128 and \dfrac{2^{7}-27}{101}=\dfrac{101}{101}=1, we
      have 2^{7}\equiv 27\;(\mod1 01).

      Hence 2^{14}=\left( 2^{7}\right) ^{2}\equiv 27^{2}\;(\mod 101).
      Because 27^{2}=729 we have

      2^{14}\equiv 729\; (\mod 101).

      But \dfrac{729-22}{101}=\dfrac{707}{101}=7. Therefore 729\equiv 22\;(\mod 101) and 2^{14}\equiv 22\;(\mod 101).

      (2) Hence 2^{28}=\left( 2^{14}\right) ^{2}\equiv 729^{2}\;(\mod 101). Because \dfrac{729^{2}-484}{101}=5257 we have

      2^{28}\equiv 484\;(\mod 101).

      Since \dfrac{484+21}{101}=5, we have 484\equiv -21\;(\mod 101).
      Therefore 2^{28}\equiv -21\;(\mod 101).

      (3) Hence 2^{56}=\left( 2^{28}\right) ^{2}\equiv \left( -21\right) ^{2}\;(\mod 101). Because \dfrac{\left( -21\right) ^{2}-441}{101}=0 we have

      2^{56}\equiv 441\;(\mod 101).

      Since \dfrac{441+64}{101}=5, we have 441\equiv -64\;(\mod 101)=-2^{6}\;(\mod 101). Therefore 2^{56}\equiv -2^{6}\;(\mod 101).

      (4) Since 2^{6}\equiv 2^{6}\;(\mod 101) and 2^{50}=\dfrac{2^{56}}{2^{6}}, we have 2^{50}\equiv \dfrac{-2^{6}}{2^{6}}\;(\mod 101)=-1\;(\mod 101).

      Using these results, we get

      2^{2002}=2^{50\times 40+2}=(2^{50})^{40}\times 2^{2} and

      2^{2002}\equiv (2^{50})^{40}\times 2^{2}\;(\mod 101)

      2^{2002}\equiv (-1)^{40}\times 2^{2}\;(\mod 101)

      2^{2002}\equiv 4\;(\mod 101)

  4. Paulo diz:

    2^33+3^33= (2^11+3^11)(2^22-2^11*3^11+3^22)
    Isso mostra que tem dois fatores, ou seja, nao eh primo :)

    —–

    [Conversão para LaTeX

    2^{33}+3^{33}=(2^{11}+3^{11})(2^{22}-2^{11}3^{11}+3^{22}) ]

    A.T.

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