Re: [obm-l] congruencias

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Amurpe:

Congruências são um dos instrumentos mais úteis para se resolver problemas
que envolvem a divisibilidade de inteiros.
Assim, em todo problema que envolve, de um jeito ou de outro, o conceito de
divisibilidade, existe uma boa chance de haver uma solução usando
congruências.

O conceito é muito simples:
Dado um inteiro não nulo "m", diz-se que dois inteiros "a" e "b" são
congruentes módulo "m" se e somente se m divide (a-b). Isso se representa
assim: a = b (mod m)
onde, na verdade, o sinal correto não é o de igualdade, mas consiste de três
traços paralelos. No entanto, como no meu teclado este sinal não existe....

Qualquer livro de teoria dos números dedica um ou mais capítulos ao assunto.
Existem dois em português que eu posso recomendar:

Teoria das Congruências
Edgard de Alencar Filho
Editora Nobel

Fundamentos de Aritmética
Hygino H. Domingues
Atual Editora

Ambos têm vários problemas resolvidos.

Além disso, na revista Eureka, da OBM, você encontra alguns artigos sobre
divisibilidade e congruências:
http://www.obm.org.br/eureka.htm

Há também um livro on-line escrito pelo Nicolau e pelo Gugu cujos primeiros
capítulos tratam justamente de divisibilidade e congruências - chama-se
Primos de Mersenne (e outros primos muito grandes). Está aqui:
http://www.mat.puc-rio.br/~nicolau/publ/papers/mersenne/index.html

De resto, se você souber inglês, digite "Number Theory" ou "Congruences" em
algum mecanismo de busca (o meu preferido é o Google) e aparecerão centenas
de páginas com referências ao assunto (algumas bem melhores que outras, é
verdade).

No mais, se houver algum problema específico da lista onde você estiver
"boiando", mande um e-mail a respeito que eu posso tentar esclarecer as suas
dúvidas, ou pelo menos indicar referências bibliográficas pertinentes.

Um abraço,
Claudio.


----- Original Message -----
From: "amurpe" <amurpe@bol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, March 25, 2003 11:54 AM
Subject: Re: [obm-l] congruencias


> > Prezado , Claudio tenho observado em várias soluções ,
> inclusive envolvendo polinômios que você usa a noção de
> congruência , e as vezes o problema não mostra isso
> explicitamente .
>
> As soluções que são dadas por você ou por outros colegas
> da lista , são muito legais , embora confesse que fico
> boiando .
>
> Fiquei , de imediato , um pouco receoso de fazer esse
> tipo de pergunta , mas como você é uma pessoa paciente .
>
> Tomo coragem e pergunto a  você , como se  faz pra "
> ver" esse tipo de saída num problema ?.
>
> Tenho cosciencia de que tem muito estudo por trás
> disso , mas se vier uma orientação eu corro atrás para
> aprender.
>
> um abraço.
>
> Amurpe
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> > ----- Original Message -----
> > From: "m.ofl" <m.ofl@bol.com.br>
> > To: <obm-l@mat.puc-rio.br>
> > Sent: Sunday, March 23, 2003 11:59 AM
> > Subject: [obm-l] congruencias
> >
> >
> > > quais podem ser os valores de n para (5 elevado a n)
> +
> > > (n elevado a 5) para que esta soma seja divisivel por
>  13
> > >
> >
> > 5^n + n^5 = 0 (mod 13) ==>
> > n^5 = - 5^n (mod 13)
> >
> > Mod 13, teremos:
> > 5^1 = 5
> > 5^2 = -1
> > 5^3 = -5
> > 5^4 = 1 ==>
> >
> > 5^(4k) = 1
> > 5^(4k+1) = 5
> > 5^(4k+2) = -1
> > 5^(4k+3) = -5
> >
> > Por outro lado (ainda mod 13)
> > n = 0 ==> n^5 = 0
> > n = 1 ==> n^5 = 1
> > n = 2 ==> n^5 = 6
> > n = 3 ==> n^5 = -4
> > n = 4 ==> n^5 = -3
> > n = 5 ==> n^5 = 5
> > n = 6 ==> n^5 = 2
> > n = -6 ==> n^5 = -2
> > n = -5 ==> n^5 = -5
> > n = -4 ==> n^5 = 3
> > n = -3 ==> n^5 = 4
> > n = -2 ==> n^5 = -6
> > n = -1 ==> n^5 = -1
> >
> > Como -5^n só pode ser igual a 1, 5 , -1 e -
> 5 (mod 13), temos que os únicos
> > valores admissíveis de n serão:
> > 1, 5, -1 e -5 (mod 13)
> >
> > n = 1 (mod 13);
> > n^5 = 1 ==> 5^n = -1 ==> n = 4k+2 ==> n = 2 (mod 4)
> >
> > n = -1 (mod 13):
> > n^5 = -1 ==> 5^n = 1 ==> n = 4k ==> n = 0 (mod 4)
> >
> > n = 5 (mod 13):
> > n^5 = 5 ==> 5^n = -5 ==> n =  4k+3 ==> n = 3 (mod 4)
> >
> > n = -5 (mod 13):
> > n^5 = -5 ==> 5^n = 5 ==> n = 4k+1 ==> n = 1 (mod 4)
> >
> > Agora, resta-
> nos resolver estes 4 sistemas de congruências, o que pode
>  ser
> > feito usando-
> se o Teorema Chinês dos Restos, uma vez que mdc
> (4,13) = 1:
> > n = a (mod 13)
> > n = b (mod 4) ==>
> >
> > n = -12a + 13b (mod 52)
> >
> > a = 1, b = 2 ==> n = 14 (mod 52)
> > a = -1, b = 0 ==> n = 12 (mod 52)
> > a = 5, b = 3 ==> n = -21 = 31 (mod 52)
> > a = -5, b = 1 ==> n = 73 = 21 (mod 52)
> >
> > Assim, a congruência n^5 + 5^n = 0 (mod 13) terá soluçã
> o para:
> > n = 12, 14, 21 e 31 (mod 52)
> >
> > Um abraço,
> > Claudio.
> >
> > =======================================================
> ==================
> > Instruções para entrar na lista, sair da lista e usar a
>  lista em
> > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> > O administrador desta lista é <nicolau@mat.puc-rio.br>
> > =======================================================
> ==================
> >
>
>
> __________________________________________________________________________
> E-mail Premium BOL
> Antivírus, anti-spam e até 100 MB de espaço. Assine já!
> http://email.bol.com.br/
>
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================