Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Teorema do resto chines generalizado

+2 votos
147 visitas
perguntada Ago 28, 2020 em Matemática por daniel cunha (31 pontos)  
editado Set 3, 2020 por daniel cunha

A imagem será apresentada aqui.

a) traducao livre do enunciado do texto

M=[m1,m2,…,mr] sao inteiros positivos. Tome m como o minimo multiplo comum de M e a e U=[u1,u2,…,ur] qualquer numero interiro. Prove que ha' um unico inteiro u que satisfazendo as sequintes condicoes:

\( a ≤ u < a + m \) onde \( u \equiv u_{j}\), \( 1\leq j \leq r \)

tal que

\( u_{i} \equiv u_{j}\) mod \( g{cd} ((m_{i}, m_{j}) \) \(1\leq i \leq j \leq r \)

Mostre que tal interiro u nao existe quando a ultima condicao e' violada.

Com vistas a deixar o enunciado do problema mais didatico, podemos reescreve-lo deixando claro que u e' a solucao de um sistema de r equações congruentes:

\( u \equiv u_{1}\) mod \( m_{1}\)
\( u \equiv u_{2}\) mod \( m_{2}\)

\( u \equiv u_{r}\) mod \( m_{r}\)

se \( u_{i} \equiv u_{j}\) mod \( g{cd} ((m_{i}, m_{j}) \)

b) Esse problema 3 apresentado no Livro Knuth no Capitulo 4 do Volume 2 e na pagina 292.

Compartilhe
comentou Set 3, 2020 por danielcajueiro (5,551 pontos)  
Ola Daniel.
Vc precisa copiar o texto da sua resposta numa resposta. Ou seja, primeiro vc faz uma pergunta. Em seguida vc abre uma aba de resposta e coloca a resposta. Não posso fazer isso por vc pois ficaria com o meu nome.
comentou Set 3, 2020 por danielcajueiro (5,551 pontos)  
Para melhorar a edicao do texto e ficar mais clara, vc deve considerar colocar sua resposta em latex. http://prorum.com/?qa=213/como-escrever-equacoes-matematicas-usar-latex-no-prorum-com&show=213#q213
comentou Set 3, 2020 por daniel cunha (31 pontos)  
Obrigado!! Ja fiz a alteracao da formatacao da pergunta e das eq em Latex

1 Resposta

0 votos
respondida Set 3, 2020 por daniel cunha (31 pontos)  
editado Set 3, 2020 por daniel cunha

c) Para resolvermos o problema, precisamos conhecer a definicao de equações congruentes

Dois inteiros a e b sao congurentes modulo n, inteiro positivo, se \( a-b\) e' divisivel por n, ou seja, \( a \equiv b\) mod\( (n)\). Por exemplo \( 24 \equiv 4\) mod\( (5)\) e' congruente, pois 4 e' resto da razao \( 24/5\) e tambem o resto da razao \( 4/5\)

Link interessante sobre equações congruentes e o teorma do resto chines

d) Comentarios o teorema do resto e resolucao da questao.

Reporta-se a criacao do teorema e' oriunda de um sistema idealizado general Han Xin a fim de evitar que espioes pudessem descobrir o numero de soldados do seu exercito. Aqui esta' um link com a historia do teorema e aplicacoes em python de uma versao simples deste. O teorema e' usado para resolver problemas de criptografia, transformacao de Fourier dentre outros.

Para resolvermos a questao, precisamos combinar a identidade de Bezout e com o algoritmo de euclides, de modo que podemos escrever uma combinacao linear de inteiros x e y tal que:

\( x\times a + y\times b = g = g{cd}(a,b) \)

Link com mais informacoes sobre a resolucao do teorema.

Link com o codigo em diversas linguagem aplicado a versao nao generalizada do teorema

A funcao crt retorna a solucao unica u para U e M bem como o minimo multiplo comum de M (m) usado para resolver o sistema de equacoes. A ideia aqui e' resolver primeiro um sistema para 2 equacoes crt([u1,u2],[m1,m2] e usar a solucao de forma iterativa fazendo u=u1 e m=m1 com u2 = u3 e m2=m3...

def crt(U, M):

u1 = U[0]
m1 = M[0]
r = len(U)
for i in range(1, r):
    u2 = U[i]
    m2 = M[i]

    a_coefficient, b_coefficient, g = 1, 0, m1
    a_coefficient2, b_coefficient2, g2 = 0, 1, m2

    while g2:
        q = g // g2
        a_coefficient, a_coefficient2 = a_coefficient2, a_coefficient-q*a_coefficient2
        b_coefficient, b_coefficient2 = b_coefficient2, b_coefficient-q*b_coefficient2
        g, g2 = g2, g-q*g2
        assert a_coefficient*m1 + b_coefficient*m2 == g
        assert a_coefficient2*m1 + b_coefficient2*m2 == g2

    if g < 0:
        a_coefficient, b_coefficient, g = -a_coefficient, -b_coefficient, -g

    if (u1 - u2) % g != 0:
        raise ValueError(f"violacao de m")

    lcm = m1 // g * m2
    rem = (u1*b_coefficient*m2 + u2*a_coefficient*m1)//g
    u = rem % lcm
    u1 = u
    m1 = lcm 
return u1, m1

 if __name__ == '__main__':
     print(crt([6,3,18],[15,6,3]))

Levando em consideracao o caso anteior e sabendo que a condicao \( u_{i} \equiv u_{j}\) mod \( g{cd} ((m_{i}, m_{j}) \) implica que \( u_{i} - u_{j}\equiv 0\) mod \( g \) , basta escolher, por exemplo, U = [2,3,2] para violar o teorema

if __name__ == '__main__':
    print(crt([2,3,2],[15,6,3]))
comentou Nov 19, 2020 por Andrei Leite (21 pontos)  
Oi Daniel.
Muito boa sua resolução. Achei que cumpriu o requisito pedido pelo professor de ser auto-contida. Apesar de eu não chegar a ler o livro do Knuth para entender melhor os teoremas em questão nem ter prévio conhecimento sobre eles, consegui entender bem qual era a ideia do problema e como você estruturou sua resposta para solucioná-lo.
Sobre seu código. Tem um erro de identação, possivelmente deve ter ocorrido na hora de passar para o Prorum. É  necessário dar um tab nas linhas entre a linha u1 = U[0] e     a_coefficient2, b_coefficient2, g2 = 0, 1, m2.
Além disso, incluí alguns print() para entender como você pensou a resposta e como estava funcionando o loop for. Me ajudou na compressão.
Achei interessante você ter incluído as duas linhas com o comando assert, para garantir a ocorrência das condições a_coefficient*m1 + b_coefficient*m2 == g  e a_coefficient2*m1 + b_coefficient2*m2 == g2. Não estava utilizando esse comando para isso, então foi um aprendizado para mim.  
Caso algum leitor de sua resposta não tenha familiaridade ainda com esse comando, segue um link do Stackoverflow sobre o assunto:  https://stackoverflow.com/questions/5142418/what-is-the-use-of-assert-in-python#:~:text=Python%20assert%20is%20basically%20a,Assert%20check%20those%20impossible%20cases.
Abraço.
comentou Dez 17, 2020 por danielcajueiro (5,551 pontos)  
O teorema do resto chinês me traz lembranças dos idos de 1993, quando iniciei minha primeira iniciação científica em matemática. Estudamos esse teorema para o caso de polinômios. Não lembro muito bem, mas foi bem divertido estudar algebra abstrata: grupos, aneis, algebras..
comentou Dez 17, 2020 por danielcajueiro (5,551 pontos)  
Ahhh sim. O ponto de partida era o knuth...
...