Question

Mostre que o numero M₈₃ = 2⁸² - 1 é divisível por 167.

Answer 1

Correção ao enunciado:

Mostre que o número M₈₃ = 2⁸³ − 1 é divisível por 167.

Explicação passo a passo:

A ideia principal em se trabalhar com aritmética módulo p, sendo p um primo razoavelmente grande, é tentar buscar congruências que tornem os cálculos menos custosos, ou ao menos não tão trabalhosos. Segue o caminho que achei mais conveniente, porém não significa que seja o mais eficiente.

Tomemos algumas potências de 2 e calculemos seus resíduos, módulo 167.

     $2^2\equiv 4\quad\mathrm{(mod~}167)\\\\ 2^3\equiv 8\quad\mathrm{(mod~}167)\\\\ 2^4\equiv 16\quad\mathrm{(mod~} 167)\\\\ 2^9=(2^3)^3=512=501+11=167\cdot 3+11\\\\ \Longrightarrow\quad 2^9\equiv 11\quad\mathrm{(mod~}167)\qquad\mathrm{(i)}$

     $2^{13}=2^9\cdot 2^4\overset{\mathrm{(i)}}{\equiv} 11\cdot 16\quad\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 2^{13}\equiv 176=167+9\equiv 9\quad\mathrm{(mod~}167)\qquad\mathrm{(ii)}$

Para que possamos usar as congruências (i) e (ii), procuramos escrever o expoente 83 como a soma de um múltiplo de 9 com um múltiplo de 13:

Como mdc(9, 13) = 1, tentaremos resolver a equação diofantina linear a seguir, com os menores valores inteiros positivos possíveis:

     $9x+13y=83\\\\ \Longleftrightarrow\quad 9x=83-13y$

Poderíamos usar o algoritmo de Euclides para resolvê-la, no entanto, aqui vou atribuir valores para y, e assim subtrair de 83 múltiplos de 13 até que obtenhamos um múltiplo de 9:

     $y=1:\quad 83-13\cdot 1=70\\\\ y=2:\quad 83-13\cdot 2=57\\\\ y=3:\quad 83-13\cdot 3=44\\\\ y=4:\quad 83-13\cdot 4=31\\\\ y=5:\quad 83-13\cdot 5=18=9\cdot 2\qquad\checkmark$

Assim, uma solução para a equação é $(x,\,y)=(2,\,5),$ e podemos escrever

     $83=9\cdot 2+13\cdot 5\qquad\mathrm{(iii)}$

Portanto,

     $\Longrightarrow\quad 2^{83}=2^{(9\,\cdot\,2\,+\,13\,\cdot\,5)}=(2^{9\,\cdot\, 2})\cdot (2^{13\,\cdot\,5})\\\\ \Longleftrightarrow\quad 2^{83}=(2^9)^2\cdot (2^{13})^5\\\\ \overset{\mathrm{(i)~e~(ii)}}{\Longrightarrow}\quad 2^{83}\equiv 11^2\cdot 9^5\quad\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 2^{83}\equiv 11^2\cdot (9^3\cdot 9^2)\quad\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 2^{83}\equiv 121\cdot 729\cdot 81\quad\mathrm{(mod~}167)\qquad\mathrm{(iv)}$

Reduzindo:

     $729=668+61=167\cdot 4+61\\\\ \Longrightarrow\quad 729\equiv 61\quad\mathrm{(mod~}167)\qquad\mathrm{(v)}$

     $121=167-46\equiv -46\quad\mathrm{(mod~}167)\\\\ \overset{\mathrm{(v)}}{\Longleftrightarrow}\quad 121\cdot 729\equiv (-46)\cdot 61\quad\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 121\cdot 729\equiv -2\,806=(-17)\cdot 167+33\\\\ \Longleftrightarrow\quad 121\cdot 729\equiv 33\quad\mathrm{(mod~}167)\qquad\mathrm{(vi)}$

Multiplique ambos os lados da congruência acima por 81:

     $\Longrightarrow\quad 121\cdot 729\cdot 81\equiv 33\cdot 81=2673\\\\ \Longleftrightarrow\quad 121\cdot 729\cdot 81\equiv 2672+1=167\cdot 16+1\equiv 1 \quad\mathrm{(mod~}167)\qquad\mathrm{(vii)}$

Então, a congruência (iv) fica

     $\overset{\mathrm{(vii)}}{\Longrightarrow}\quad 2^{83}\equiv 1 \quad\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 167\,|\,(2^{83}-1)\qquad\checkmark$

Logo, M₈₃ = 2⁸³ − 1 é divisível por 167, como queríamos.

Duvidas? Comente.

Bons estudos! :-)

Answer 2

Olá camarada,

Se você deseja uma solução elegante, você está lendo a resposta errada. Leia a feita por Lukyo, que com certeza será melhor. Eu estou aqui para oferecer uma solução BRUTA, fácil de entender e ao mesmo tempo trabalhosa (pois requer o cálculo manual do resto de 3 números grandes):

$2^{83} - 1 \equiv 0 \pmod {167}\\(2^8)^{10} \cdot 2^3 \equiv 1 \pmod {167}\\256^{10} \cdot 8 \equiv1 \pmod {167}\\89^{10} \cdot 8 \equiv1 \pmod {167}\\(89^2)^{5} \cdot 8 \equiv1 \pmod {167}\\7921^5 \cdot 8 \equiv1 \pmod {167}\\72^5 \cdot 8 \equiv1 \pmod {167}\\(72^2)^2 \cdot 72 \cdot 8 \equiv1 \pmod {167}\\5184^2 \cdot 576 \equiv1 \pmod {167}\\7^2 \cdot 75 \equiv1 \pmod {167}\\49 \cdot 75 \equiv1 \pmod {167}\\3675 \equiv1 \pmod {167}\\1 \equiv1 \pmod {167}$