Resto da divisão

por CASSIANE Qui 02 Out 2014, 21:00

Determine o resto na divisão de $Resto da divisão Gif$ por 853.
Dica: Observe que 327 = 1 + 2 + $Resto da divisão Gif$ + $Resto da divisão Gif$ + $Resto da divisão Gif$

por **ivomilton** Sex 03 Out 2014, 13:57

CASSIANE escreveu:Determine o resto na divisão de $Resto da divisão Gif$ por 853.
Dica: Observe que 327 = 1 + 2 + $Resto da divisão Gif$ + $Resto da divisão Gif$ + $Resto da divisão Gif$

Boa tarde,

Usando a função MOD da calculadora científica do Windows, encontrei que:
7^327 ≡ 286 (mod 853).
Talvez esta informação possa ajudar quem estiver tentando resolver esta questão.

Um abraço.

por CASSIANE Seg 06 Out 2014, 11:11

Não entendi muito bem.
Eu sei que 853 é um número primo e tentei fazer da forma $Resto da divisão Gif$
Mas fiquei um pouco perdida no caminho.
Esse é o jeito certo?

por **ivomilton** Seg 06 Out 2014, 12:54

CASSIANE escreveu:Não entendi muito bem.
Eu sei que 853 é um número primo e tentei fazer da forma $Resto da divisão Gif$
Mas fiquei um pouco perdida no caminho.
Esse é o jeito certo?

Bom dia, Cassiane.

Eu não saberia lhe dizer qual o caminho a seguir para resolver, pois creio que é questão da área das Congruências, assunto com o qual não estou muito familiarizado.
O que eu fiz (se é que poderá ajudar-lhe em algo) foi achar os restos das divisões das potências que voce relacionou (na decomposição de 7³²⁷, a saber:

Potência ____ Resto
7¹ _____________ 7
7² ____________ 49
7⁴____________ 695
7⁶⁴ -__________ 123
7²⁵⁶ _________ 298
-----------------------------
7³²⁷- _________ 286 = resto da divisão de (7.49.695.123.298)/853

O modo pelo qual eu consegui esses restos foi o mesmo: utilizando a calculadora científica do Windows.

Um abraço.

por **Carlos Adir** Seg 06 Out 2014, 13:50

Você pode "brincar" com os números:
$\\7^{327} \equiv (\sqrt[3]{7})^{3 \times 327} \equiv (\sqrt[3]{7})^{981} \pmod{853}\\ Por \ definicao: a^{p-1} \equiv 1 \pmod{p}; \ se \ MDC(a, p) = 1\\ 7^{327} \equiv (\sqrt[3]{7})^{852} \times (\sqrt[3]{7})^{129} \equiv 1 \times (\sqrt[3]{7})^{3 \times 43} \pmod{853}\\ 7^{327} \equiv 7^{43} \equiv 286$

Agora é mais facil calcular 7^{43} né? Fica por sua conta Wink

por CASSIANE Seg 06 Out 2014, 15:09

Vc está usando o Pequeno Teorema de Fermat, não é?
Eu preciso calcular sem esse teorema.
Mas obg.

por **Carlos Adir** Seg 06 Out 2014, 15:32

Não pode demonstrar o Teorema de Fermat, e depois aplica-lo não? Seria bem mais facil que tentar achar uma solução sem utilizá-lo.
Mas talvez consiga fazendo a seguinte relação:
$a = bq + r$
Logo:
$\\a^2 = (bq+r)^2 = (bq+r)(bq+r)=bq^2+2bqr+r^2=q(bq^2+2qr)+r^2\\ a^4 = (qb'+r^2)^2 = q^2b'^2+2qb'r+r^4=q(qb'^2+2b'r)+r^4$
Assim, se q é o numero divisor(853 no caso), então pode-se ir reduzindo.
O resto de a quando dividido por q equivale a r. Assim, o resto de a^(n) quando dividido por q equivale a r^(n)

Assim, juntando com o método acima mostrado, daria-se a mostrar. Não achas?

por **ivomilton** Seg 06 Out 2014, 15:52

CASSIANE escreveu:Vc está usando o Pequeno Teorema de Fermat, não é?
Eu preciso calcular sem esse teorema.
Mas obg.

Boa tarde, Cassiane.

Veja o que encontrei pesquisando pelo Google a respeito; link a seguir:

http://www.math.tecnico.ulisboa.pt/~pmartins/EMF/Notas/Euler.pdf

Após abrir esse link, procure, ao final da página 6, o subtítulo

1.1 Nota sobre o cálculo eficiente de potências

e leia desse lugar em diante; você irá encontrar a resposta que você deseja.

Ali foi feito como eu (sem saber) apresentei como solução a você.

Um abraço.

por CASSIANE Seg 06 Out 2014, 22:16

Obrigada pela ajuda, Ivomilton.

por euricotorres Ter 07 Out 2014, 19:16

CASSIANE escreveu:Determine o resto na divisão de $Resto da divisão Gif$ por 853.
Dica: Observe que 327 = 1 + 2 + $Resto da divisão Gif$ + $Resto da divisão Gif$ + $Resto da divisão Gif$