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>
=========================================================================