::: Continuando o vaguear pelas congruências módulo m.

Publicado em Domingo, 18 Maio, 2008 por physike

.::. Do último teorema, do último artigo, podemos fazer coisas fantásticas com os números. Por exemplo:

.::. Eu quero saber o resto da divisão de \displaystyle\ 41^{65} por 7. Mas, para que isso? Calma…

.::. Bom, eu sei que 41\equiv\ -1(mod\ 7), pois 7 | 41-(-1).

.::. Utilizando aquele último teorema, eu posso fazer: 41^{65}\equiv\ (-1)^{65}(mod\ 7), que tem como resultado:

41^{65}\equiv\ -1(mod\ 7)

.::. Mas também sabemos que -1\equiv\ 6(mod\ 7).

.::. Logo, temos que:

41^{65}\equiv\ -1(mod\ 7) e  -1\equiv\ 6(mod\ 7) \Rightarrow 41^{65}\equiv\ 6(mod\ 7).

.::. Ou seja, o resto dessa divisão é igual a 6.

_________________________________________________________________________________

.::. Utilizando os demais teoremas demonstrados no artigo anterior, podemos saber qual é, por exemplo, o resto da divisão de 7^{100}+11^{100} por 13.

.::. Bem, sabemos que 7^{2}\equiv\ 10(mod\ 13). Podemos fazer:

7^{4}\equiv\ 10^{2}(mod\ 13)\Rightarrow\ 7^{4}\equiv\ 100(mod\ 13)

.::. Mas 100\equiv\ 9(mod\ 13). Então, 7^{4}\equiv\ 9(mod\ 13).

.::. Continuando… 7^{8}\equiv\ 81(mod\ 13). Mas 81\equiv\ 3(mod\ 13). Então:

7^{8}\equiv\ 3(mod\ 13)

.::. Podemos dar um salto maior agora, já que 7^{24}\equiv\ 27(mod\ 13), e como 27\equiv\ 1(mod\ 13), então 7^{24}\equiv\ 1(mod\ 13).

7^{96}\equiv\ 1^{4}(mod\ 13)

7^{100}\equiv\ 7^{4}(mod\ 13)

.::. Mas 7^{4}\equiv\ 9(mod\ 13), então concluímos que 7^{100}\equiv\ 9(mod\ 13).

.::. Agora, vamos fazer 11^{2}\equiv\ 4(mod\ 13).

11^{6}\equiv\ 64(mod\ 13). Mas 64\equiv\ -1(mod\ 13). Então:

11^{6}\equiv\ -1(mod\ 13)

11^{96}\equiv\ (-1)^{16}(mod\ 13)\Rightarrow\ 11^{96}\equiv\ 1(mod\ 13)

11^{100}\equiv\ 11^{4}(mod\ 13)\Rightarrow\ 11^{100}\equiv\ 3(mod\ 13)

.::. Então, podemos combinar ambas as respostas, e fazer:

7^{100}+11^{100}\equiv\ 9+3(mod\ 13) \Rightarrow 7^{100}+11^{100}\equiv\ 12(mod\ 13)

.::. Ou seja, o resto dessa divisão é igual a 12.

_________________________________________________________________________________

.::. Mais um exemplo: gostaria de saber o último algarismo do número 3^{300}.

.::. O último algarismo de um número é o resto da divisão dele por 10. Então, vamos passo a passo:

3^{2}\equiv\ -1(mod\ 10)

(3^{2})^{150}\equiv\ (-1)^{150}(mod\ 10)

3^{300}\equiv\ 1(mod\ 10)

.::. Ou seja, o último algarismo desse número é 1.

_________________________________________________________________________________

.::. E para calcular o resto da divisão de:

\displaystyle\ 74892^{359}.6379^{207}.9538^{179}.3756^{729}

por 5 ? :OOOOO

.::. Bom, vamos começar por 74892^{359}. Sabemos que \displaystyle\ 74892\equiv\ 2(mod\ 5) – faça os cálculos!. E também sabemos que \displaystyle\ 2^{2}\equiv\ -1(mod\ 5). Logo:

\displaystyle\ (2^{2})^{179}\equiv\ (-1)^{179}(mod\ 5)

\displaystyle\ 2^{358}\equiv\ -1(mod\ 5)

\displaystyle\ 2.2^{358}\equiv\ 2.(-1)(mod\ 5)

\displaystyle\ 2^{359}\equiv\ -2(mod\ 5)\Rightarrow\ -2\equiv\ 3(mod\ 5)

\displaystyle\ 2^{359}\equiv\ 3(mod\ 5)\Rightarrow\ 74892^{359}\equiv\ 3(mod\ 5) (A).

.::. Agora, vamos passar para \displaystyle\ 6379^{207}. Sabemos que \displaystyle\ 6379\equiv\ 4(mod\ 5) e que \displaystyle\ 4\equiv\ -1(mod\ 5). Logo:

\displaystyle\ 4^{206}\equiv\ (-1)^{206}(mod\ 5)

\displaystyle\ 4^{206}\equiv\ 1(mod\ 5)

\displaystyle\ 4.4^{206}\equiv\ 4.1(mod\ 5)

\displaystyle\ 4^{207}\equiv\ 4(mod\ 5)\Rightarrow\ 6379^{207}\equiv\ 4(mod\ 5) (B).

.::. Agora, faremos: \displaystyle\ 9538^{179}. Bem:

\displaystyle\ 9538\equiv\ 3(mod\ 5)

\displaystyle\ 3^{2}\equiv\ -1(mod\ 5)

\displaystyle\ (3^{2})^{89}\equiv\ (-1)^{89}(mod\ 5)

\displaystyle\ 3^{178}\equiv\ -1(mod\ 5)

\displaystyle\ 3.3^{178}\equiv\ 3.(-1)(mod\ 5)

\displaystyle\ 3^{179}\equiv\ -3(mod\ 5)\Rightarrow\ -3\equiv\ 2(mod\ 5)

\displaystyle\ 3^{179}\equiv\ 2(mod\ 5)\Rightarrow\ 9538^{179}\equiv\ 2(mod\ 5) (C).

.::. Por último, faremos \displaystyle\ 3756^{729}. Da mesma maneira, temos:

\displaystyle\ 3756\equiv\ 1(mod\ 5)

\displaystyle\ 3756^{729}\equiv\ 1(mod\ 5) (D).

.::. Agora, resolvendo o produto:

\displaystyle\ 74892^{359}.6379^{207}.9538^{179}.3756^{729}\equiv\ 3.4.2.1(mod\ 5)

\displaystyle\ 74892^{359}.6379^{207}.9538^{179}.3756^{729}\equiv\ 24(mod\ 5)

.::. Mas, 24\equiv\ 4(mod\ 5). Então:

\displaystyle\ 74892^{359}.6379^{207}.9538^{179}.3756^{729}\equiv\ 4(mod\ 5)

.::. Ou seja, o resto dessa divisão é 4!!!!!!

Arquivado em: Matemática, Teoria dos Números | Etiquetado: , ,

« »

Uma resposta

  1. Américo Tavares, em Junho 5th, 2009 às 6:03 am Diz:

    Sobre um problema da Purdue University que resolvi utilizando congruências coloquei no meu blogue este artigo:

    « 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 em baixo 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.
    (…)»

    Responder

Deixe uma resposta