Verified answer

Resposta: O resto da divisão é 5.

Algoritmo da divisão euclidiana

Sejam a, b números naturais. Pelo algoritmo da divisão euclidiana, existem q, r naturais, tais que

     a = bq + r

com r ∈ {0, 1, ..., b - 1}.

Tal valor de r é o resto da divisão de a por b, e q é o quociente da divisão de a por b.

Algumas propriedades da aritmética dos restos

Sejam a, b, c, n, r, s naturais.

Suponha que a deixa resto r na divisão por c, e b deixa resto s na divisão por c, ou seja, existem q₁, q₂ naturais, tais que

     a = cq₁ + r

     b = cq₂ + s

com r, s ∈ {0, 1, ..., c - 1}.

Então, valem as seguintes propriedades:

• a + b deixa o mesmo resto que r + s na divisão por c.

• ab deixa o mesmo resto que rs na divisão por c.

• aⁿ deixa o mesmo resto que rⁿ na divisão por c.

Pequeno Teorema de Fermat

Sejam a, p naturais, p primo. Se mdc(a, p) = 1, então p divide [tex]a^{p-1}-1,[/tex] ou seja, [tex]a^{p-1}[/tex] deixa resto 1 na divisão por p.

Calculando o resto da divisão por 11

Temos

     [tex]672588=61144\cdot 11+4[/tex]

Portanto, basta calcularmos o resto da divisão de [tex]4^{607}[/tex] por 11.

     [tex]4^{607}=(2^2)^{607}=2^{1214}[/tex]

Como 11 é primo e mdc(2, 11) = 1, pelo Pequeno Teorema de Fermat, concluímos que 11 divide [tex]2^{10}-1,[/tex] ou seja,

     [tex]2^{10}-1=11q\\\\ 2^{10}=11q+1,\quad\exists q\in\mathbb{N}.[/tex]

Efetuando a divisão euclidiana do expoente 1214 por 10, temos

     [tex]1214=121\cdot 10+4[/tex]

Portanto,

     [tex]2^{1214}=2^{121\cdot 10+4}\\\\ 2^{1214}=2^{121\cdot 10}\cdot 2^4\\\\ 2^{1214}=(2^{10})^{121}\cdot 2^4[/tex]

Como [tex]2^{10}[/tex] deixa resto 1 na divisão por 11, o resto procurado é o mesmo resto que

     [tex]1^{121}\cdot 2^4=16[/tex]

na divisão por 11. E como

     [tex]16=1\cdot 11+5[/tex]

concluímos que o resto é 5.

Dúvidas? Comente.

Bons estudos! :-)