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

Teorema do resto chines generalizado

+2 votos
20 visitas
perguntada Ago 28 em Matemática por daniel cunha (11 pontos)  
editado Set 3 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 por danielcajueiro (6,051 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 por danielcajueiro (6,051 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 por daniel cunha (11 pontos)  
Obrigado!! Ja fiz a alteracao da formatacao da pergunta e das eq em Latex

1 Resposta

0 votos
respondida Set 3 por daniel cunha (11 pontos)  
editado Set 3 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]))
...