Re: [obm-l] congruencias

2015-09-25 Por tôpico Artur Costa Steiner 
Vale sim. 

Artur Costa Steiner

> Em 25 de set de 2015, às 02:20, Israel Meireles Chrisostomo 
>  escreveu:
> 
> Eu bem sei que se r é um natural e a=b mod(m) então vale que ar=br mod(m), 
> isso vale se r for negativo?Por exemplo 10=-2 mod(3), então, multiplicando 
> por -1 fica  -10=2 mod(3)?
> 
> -- 
> Esta mensagem foi verificada pelo sistema de antivírus e 
> acredita-se estar livre de perigo.

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

Re: [obm-l] congruencias

2015-09-25 Por tôpico Cassio Anderson Feitosa 
Sim, vale; m | a-b>  a-b=km  ===> r(a-b) = (rk)m ===> m | ra-rb.

Em 25 de setembro de 2015 02:20, Israel Meireles Chrisostomo <
israelmchrisost...@gmail.com> escreveu:

> Eu bem sei que se r é um natural e a=b mod(m) então vale que ar=br mod(m),
> isso vale se r for negativo?Por exemplo 10=-2 mod(3), então, multiplicando
> por -1 fica  -10=2 mod(3)?
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.




-- 
Cássio Anderson
Graduando em Matemática - UFPB

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

RE: [obm-l] congruencias

2008-11-13 Por tôpico Lucas Colucci 

2) Demonstrar que a^21 == a (mod15)

Bom isso ocorre se valer pra mod 3 e mod 5 ao mesmo tempo. Vamos fazer 
sepaadamente:

Módulo 3:
a^21==a(mod3)
a(a^20-1)=0(mod3), o que de fato ocorre, pois se 3|a, a==0(mod3), e se a==1 ou 
-1 (mod3), 3|a^20-1.

Módulo 5:
a^21==a(mod5)
a(a^10+1)(a^5+1)(a^5-1)==0(mod5)
Se a==0(mod5), ok, pois 5|a
Se a==1(mod5), ok, pois 5|a^5-1
Se a==-1(mod5), ok, pois 5|a^5+1
Se a==2 ou -2(mod 5), ok, pois a^10 termina com 4 (1024), e daí 5|a^10+1.

Logo, de fato, a^21==a(mod15), cqd.

1) Verificar que 18^6 == 1 (mod 49)

Como 18^3==1(mod 49), para verificar isso é só fazer a conta ou fatorar 
18^3-1=(18-1)(18²+18+1)=343*17==0(mod 49), pois 49|343.

Daí, (18^3)²==1(mod 49), isto é, 18^6==1(mod49).

Espero ter sido claro,


Lucas Colucci

From: [EMAIL PROTECTED]
To: obm-l@mat.puc-rio.br
Subject: [obm-l] congruencias
Date: Thu, 13 Nov 2008 22:32:45 -0200










Boa noite, poderiam, por gentileza, me ajudar 
nestes exercícios?
 
1) Verificar que 18^6 == 1 (mod 49)
 
2) Demonstrar que a^21 == a (mod15)
 
Obrigado 
Hermann
 
 
 
 
_
Confira vídeos com notícias do NY Times, gols direto do Lance, videocassetadas 
e muito mais no MSN Video!
http://video.msn.com/?mkt=pt-br

Re: [obm-l] Congruencias

2008-02-16 Por tôpico Igor Battazza 
2008/2/15, saulo nilson <[EMAIL PROTECTED]>:
> =0mod(n-1)/2
>
>
>
> On 2/15/08, saulo nilson <[EMAIL PROTECTED]> wrote:
> >
> > s= 1+soma(2 a n-1)mod(n-1)=
> > =1+(2+n-1)*(n-2)/2mod(n-1)=1+(n+1)(n-2)/2mod(n-1)=
> > = 1+(k+1)(2k-1)mod2k=
> > =q*2k+2k^2+k=k*(2q+2k+1)
> >
> >

Muito obrigadissimo Saulo! Valeu mesmo!
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

Re: [obm-l] Congruencias

2008-02-15 Por tôpico saulo nilson 
s= 1+soma(2 a n-1)mod(n-1)=
=1+(2+n-1)*(n-2)/2mod(n-1)=1+(n+1)(n-2)/2mod(n-1)=
= 1+(k+1)(2k-1)mod2k=
=q*2k+2k^2+k=k*(2q+2k+1)

On 2/10/08, Igor Battazza <[EMAIL PROTECTED]> wrote:
>
> Bom dia!
>
> Estava resolvendo uns problemihas de congruencia e enrosquei nesse aqui:
>
> "Prove que n divide 1^n + 2^(n-1) + ... + (n-1)^(n-1) se n é ímpar."
>
> Acho que não estou conseguindo compreender o enunciado (se isso ja n é
> proposital por quem o elaborou)
>
> Qualquer ajudda é bem vinda!
>
> Obrigado,
> Igor F. Carboni Battazza.
>

Re: [obm-l] Congruencias

2008-02-15 Por tôpico saulo nilson 
=0mod(n-1)/2

On 2/15/08, saulo nilson <[EMAIL PROTECTED]> wrote:
>
> s= 1+soma(2 a n-1)mod(n-1)=
> =1+(2+n-1)*(n-2)/2mod(n-1)=1+(n+1)(n-2)/2mod(n-1)=
> = 1+(k+1)(2k-1)mod2k=
> =q*2k+2k^2+k=k*(2q+2k+1)
>
>  On 2/10/08, Igor Battazza <[EMAIL PROTECTED]> wrote:
> >
> > Bom dia!
> >
> > Estava resolvendo uns problemihas de congruencia e enrosquei nesse aqui:
> >
> > "Prove que n divide 1^n + 2^(n-1) + ... + (n-1)^(n-1) se n é ímpar."
> >
> > Acho que não estou conseguindo compreender o enunciado (se isso ja n é
> > proposital por quem o elaborou)
> >
> > Qualquer ajudda é bem vinda!
> >
> > Obrigado,
> > Igor F. Carboni Battazza.
> >
>
>

Re: [obm-l] Congruencias

2008-02-12 Por tôpico Igor Battazza 
Olá Rafael,

Achei esse problema em um artigo escrito pelo Samuel Barbosa (problema 4),
com o título Congruências. Está disponível em
http://www.grupoteorema.mat.br/artigos/congruencias-2.pdf (não sei se
poderia ter colado esse link mas... peço sinceras desculpas.)

Muito obrigado,
Igor F. Carboni Battazza.

Re: [obm-l] Congruencias

2008-02-11 Por tôpico Rafael Cano 
Olá,
Acho que o enunciado está errado.
Se eu entendi direito, fazendo n=3 ou n=5 não da certo...
Abraços.
  - Original Message - 
  From: Igor Battazza 
  To: obm-l@mat.puc-rio.br 
  Sent: Sunday, February 10, 2008 8:55 AM
  Subject: [obm-l] Congruencias


  Bom dia!

  Estava resolvendo uns problemihas de congruencia e enrosquei nesse aqui:

  "Prove que n divide 1^n + 2^(n-1) + ... + (n-1)^(n-1) se n é ímpar."

  Acho que não estou conseguindo compreender o enunciado (se isso ja n é 
proposital por quem o elaborou)

  Qualquer ajudda é bem vinda!

  Obrigado,
  Igor F. Carboni Battazza.

Re: [obm-l] congruencias

2004-03-16 Por tôpico Andre 
Title: Re: [obm-l] congruencias



Pode me mostrar como foi que aparecer de 2^70 + 
3^70 = 2503155504994422192936289397389273 ?

  - Original Message - 
  From: 
  Claudio Buffara 
  To: [EMAIL PROTECTED] 
  Sent: Tuesday, March 09, 2004 12:43 
  AM
  Subject: Re: [obm-l] congruencias
  on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
  Ola pessoal, Prove que 2^70 + 3^70 eh 
divisivel por 13. Esse eh facil. Basta ver 
  que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente 
  divisivel por 13. O quociente eh 
  192550423461109399456637645953021.[]'s,Claudio.

Re: [obm-l] congruencias

2004-03-11 Por tôpico Cesar Ryudi Kawakami 
Droga, escrevi a mensagem com pressa.

Pensando melhor eu escrevi muita porcaria...

Fazendo algumas contas:

2 congruente a 2 mod 13
2^2 congruente a 4 mod 13
(2^2)^5 congruente a 4^5 mod 13 (4^5 = 1024, dá pra fazer na mao, e depois 
divide por 13) => congruente a 10 mod 13
(2^10)^7 congruente a 10^7 mod 13 (divide na mao 10^7 por 13, acha:) 
congruente a 10 mod 13.

logo 2^70 congruente a 10 mod 13.

Agora:

3 congruente a 3 mod 13;
3^2 = 9 congruente a 3^2 = 9 mod 13
(3^2)^5 congruente a 9^5 = 59049,  congruente a 3 mod 13
(3^10)^7 congruente a 3^7 = 2187, congruente a 3 mod 13.
logo 3^70 congruente a 3 mod 13.

Somando, temos que 2^70 + 3^70 congruente a 13 mod 13, logo 2^70 + 3^70 
congruente a 0 mod 13, e 13 divide 2^70 + 3^70.

É mais rápido pelo pequeno teorema de fermat, onde 2^13 congruente a 2 mod 
13 e 3^13 congruente a 3 mod 13...

At 15:46 11/3/2004, you wrote:

-Mensagem Original-
De: "Cesar Ryudi Kawakami" <[EMAIL PROTECTED]>
Para: <[EMAIL PROTECTED]>
Enviada em: quinta-feira, 11 de março de 2004 14:41
Assunto: Re: [obm-l] congruencias
Uma solucao sem cálculos seria esta:

13 divide 2^70 + 3^70 implica que:

2^70 + 3^70 = 0 (mod 13) , onde = denota congruencia.

logo

2^70 = -3^70 (mod 13)

como a^k = b^k (mod m) => a = b (mod m),  ISTO É FALSO

ver o artigo do Yuri Gomes, temos:

2 = -3 (mod 13) ISTO É FALSO

13 divide -3 - (-2) = -1, verdade. ISTO É FALSO

Logo 13 divide 2^70 + 3^70.

At 13:42 10/3/2004, you wrote:
>Bem, e se voces usassem sorobans?
>
>Claudio Buffara <[EMAIL PROTECTED]> wrote:
>Calculadora? Que calculadora?
>
>on 10.03.04 00:43, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
>
>CLARAMENTE para quem: Para voce ou para a sua calculadora ?
:-))
>
>
>
>
>Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul,
>[EMAIL PROTECTED] escreveu:
>
>
>
>Realmente, ,mais humilhante nao podia ser...
>
>Claudio Buffara <[EMAIL PROTECTED]> wrote:
>on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
>
>Ola pessoal,
>
>
>Prove que 2^70 + 3^70 eh divisivel por 13.
>
>Esse eh facil.
>
>Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh
>claramente divisivel por 13. O quociente eh
192550423461109399456637645953021.
>
>[]'s,
>Claudio.
>
>
>
>
>
>
>
>
>
>
><http://br.rd.yahoo.com//mail_br/tagline/?http://br.yahoo.com/info/mail.htm
l>Yahoo!
>Mail - O melhor e-mail do Brasil. Abra sua conta agora!
=
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
=
=
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
=


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

Re: [obm-l] congruencias

2004-03-11 Por tôpico Paulo Rodrigues 

-Mensagem Original-
De: "Cesar Ryudi Kawakami" <[EMAIL PROTECTED]>
Para: <[EMAIL PROTECTED]>
Enviada em: quinta-feira, 11 de março de 2004 14:41
Assunto: Re: [obm-l] congruencias


Uma solucao sem cálculos seria esta:

13 divide 2^70 + 3^70 implica que:

2^70 + 3^70 = 0 (mod 13) , onde = denota congruencia.

logo

2^70 = -3^70 (mod 13)

como a^k = b^k (mod m) => a = b (mod m),  ISTO É FALSO

ver o artigo do Yuri Gomes, temos:

2 = -3 (mod 13) ISTO É FALSO


13 divide -3 - (-2) = -1, verdade. ISTO É FALSO


Logo 13 divide 2^70 + 3^70.

At 13:42 10/3/2004, you wrote:
>Bem, e se voces usassem sorobans?
>
>Claudio Buffara <[EMAIL PROTECTED]> wrote:
>Calculadora? Que calculadora?
>
>on 10.03.04 00:43, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
>
>CLARAMENTE para quem: Para voce ou para a sua calculadora ?
:-))
>
>
>
>
>Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul,
>[EMAIL PROTECTED] escreveu:
>
>
>
>Realmente, ,mais humilhante nao podia ser...
>
>Claudio Buffara <[EMAIL PROTECTED]> wrote:
>on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
>
>Ola pessoal,
>
>
>Prove que 2^70 + 3^70 eh divisivel por 13.
>
>Esse eh facil.
>
>Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh
>claramente divisivel por 13. O quociente eh
192550423461109399456637645953021.
>
>[]'s,
>Claudio.
>
>
>
>
>
>
>
>
>
>
><http://br.rd.yahoo.com//mail_br/tagline/?http://br.yahoo.com/info/mail.htm
l>Yahoo!
>Mail - O melhor e-mail do Brasil. Abra sua conta agora!


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

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

Re: [obm-l] congruencias

2004-03-11 Por tôpico Cesar Ryudi Kawakami 
Uma solucao sem cálculos seria esta:

13 divide 2^70 + 3^70 implica que:

2^70 + 3^70 = 0 (mod 13) , onde = denota congruencia.

logo

2^70 = -3^70 (mod 13)

como a^k = b^k (mod m) => a = b (mod m), ver o artigo do Yuri Gomes, temos:

2 = -3 (mod 13)

13 divide -3 - (-2) = -1, verdade.

Logo 13 divide 2^70 + 3^70.

At 13:42 10/3/2004, you wrote:
Bem, e se voces usassem sorobans?

Claudio Buffara <[EMAIL PROTECTED]> wrote:
Calculadora? Que calculadora?
on 10.03.04 00:43, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

CLARAMENTE para quem: Para voce ou para a sua calculadora ? :-))



Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul, 
[EMAIL PROTECTED] escreveu:



Realmente, ,mais humilhante nao podia ser...

Claudio Buffara <[EMAIL PROTECTED]> wrote:
on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
Ola pessoal,

Prove que 2^70 + 3^70 eh divisivel por 13.

Esse eh facil.

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh 
claramente divisivel por 13. O quociente eh 192550423461109399456637645953021.

[]'s,
Claudio.








Yahoo! 
Mail - O melhor e-mail do Brasil. Abra sua conta agora!


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

Re: [obm-l] congruencias

2004-03-10 Por tôpico Johann Peter Gustav Lejeune Dirichlet 
Bem, e se voces usassem sorobans?Claudio Buffara <[EMAIL PROTECTED]> wrote:
Calculadora? Que calculadora?on 10.03.04 00:43, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
CLARAMENTE para quem: Para voce ou para a sua calculadora ? :-)) Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: 
Realmente, ,mais humilhante nao podia ser... Claudio Buffara <[EMAIL PROTECTED]> wrote: 
on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: 
Ola pessoal, Prove que 2^70 + 3^70 eh divisivel por 13. Esse eh facil. Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente divisivel por 13. O quociente eh 192550423461109399456637645953021. []'s, Claudio. Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!

Re: [obm-l] congruencias

2004-03-10 Por tôpico Claudio Buffara 
Title: Re: [obm-l] congruencias



Calculadora? Que calculadora?

on 10.03.04 00:43, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

CLARAMENTE para quem: Para voce ou para a sua calculadora ? :-)) 




Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: 



Realmente, ,mais humilhante nao podia ser... 

Claudio Buffara <[EMAIL PROTECTED]> wrote: 
on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote: 

Ola pessoal, 


Prove que 2^70 + 3^70 eh divisivel por 13. 

Esse eh facil. 

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente divisivel por 13. O quociente eh 192550423461109399456637645953021. 

[]'s, 
Claudio.

Re: [obm-l] congruencias

2004-03-09 Por tôpico Faelccmm 
CLARAMENTE para quem: Para voce ou para a sua calculadora ? :-))




Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu:



Realmente, ,mais humilhante nao podia ser...

Claudio Buffara <[EMAIL PROTECTED]> wrote: 
on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

Ola pessoal, 


Prove que 2^70 + 3^70 eh divisivel por 13. 

Esse eh facil. 

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente divisivel por 13. O quociente eh 192550423461109399456637645953021.

[]'s,
Claudio.

RE: [obm-l] congruencias

2004-03-09 Por tôpico Johann Peter Gustav Lejeune Dirichlet 
Realmente, mais humilhante nao da!Artur Costa Steiner <[EMAIL PROTECTED]> wrote:
Mas nem precisava dividir. A conclusao eh imediata.ArturProve que 2^70 + 3^70 eh divisivel por 13. Esse eh facil. Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual ehclaramente divisivel por 13. O quociente eh192550423461109399456637645953021.[]'s,Claudio. =Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!

Re: [obm-l] congruencias

2004-03-09 Por tôpico Johann Peter Gustav Lejeune Dirichlet 
Realmente, ,mais humilhante nao podia ser...Claudio Buffara <[EMAIL PROTECTED]> wrote:
on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:
Ola pessoal, Prove que 2^70 + 3^70 eh divisivel por 13. Esse eh facil. Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente divisivel por 13. O quociente eh 192550423461109399456637645953021.[]'s,Claudio. Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!

Re: [obm-l] congruencias

2004-03-08 Por tôpico Rafael 
Re: [obm-l] congruenciasCláudio,

O seu *claramente* foi invejável, invejável! ;-D


Abraços,

Rafael de A. Sampaio



- Original Message -
From: Claudio Buffara
To: [EMAIL PROTECTED]
Sent: Tuesday, March 09, 2004 12:43 AM
Subject: Re: [obm-l] congruencias


Prove que 2^70 + 3^70 eh divisivel por 13.


Esse eh facil.

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh
claramente divisivel por 13. O quociente eh
192550423461109399456637645953021.

[]'s,
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
=

RE: [obm-l] congruencias

2004-03-08 Por tôpico Artur Costa Steiner 
Mas nem precisava dividir. A conclusao eh imediata.
Artur


Prove que 2^70 + 3^70 eh divisivel por 13. 

Esse eh facil. 

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh
claramente divisivel por 13. O quociente eh
192550423461109399456637645953021.

[]'s,
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
=

Re: [obm-l] congruencias

2004-03-08 Por tôpico Ricardo Bittencourt 
[EMAIL PROTECTED] wrote:

  Ola pessoal,

Prove que 2^70 + 3^70 eh divisivel por 13.
	Como 13 é primo vale o pequeno teorema de Fermat:

	a^(p-1)=1 (mod p)

	ou seja

	a^12 = 1 (mod 13)

Agora floor(70/12)=5 e portanto
70 = 5*12+10 = 10 (mod 13)

De modo que o problema se reduz a
2^10+3^10 =0 (mod 13)
	Multiplicando dos dois lados por 4*9:

	4*9*(2^10+3^10) = 9*2^12 + 4*3^12

	mas 2^12 = 3^12 = 0 (mod 13)

	portanto 2^70+3^70 = 4+9 = 13 = 0 (mod 13) QED


Ricardo Bittencourt   http://www.mundobizarro.tk
[EMAIL PROTECTED]   "tenki ga ii kara sanpo shimashou"
-- União contra o forward - crie suas proprias piadas --
=
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
=

Re: [obm-l] congruencias

2004-03-08 Por tôpico Claudio Buffara 
Title: Re: [obm-l] congruencias



on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

Ola pessoal, 


Prove que 2^70 + 3^70 eh divisivel por 13. 

Ou entao, voce observa que 2^2 + 3^2 = 4 + 9 = 13.

Logo, mod 13, teremos: 
2^2 + 3^2 == 0  ==>
2^2 == - 3^2  ==>
(2^2)^35 == (-3^2)^35  ==>
2^70 == -3^70  ==>
2^70 + 3^70 == 0 

[]'s,
Claudio.

Re: [obm-l] congruencias

2004-03-08 Por tôpico Claudio Buffara 
Title: Re: [obm-l] congruencias



on 09.03.04 01:14, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

Ola pessoal, 


Prove que 2^70 + 3^70 eh divisivel por 13. 

Esse eh facil. 

Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh claramente divisivel por 13. O quociente eh 192550423461109399456637645953021.

[]'s,
Claudio.

Re: [obm-l] congruencias-modulo

2004-03-03 Por tôpico Claudio Buffara 
Title: Re: [obm-l] congruencias-modulo



on 03.03.04 21:47, [EMAIL PROTECTED] at [EMAIL PROTECTED] wrote:

Ola pessoal, 



1) Mostre que o quadrado de um numero inteiro nao pode terminar em 2, 3, 7 ou 8. 

mod 10:
0^2 == 0 
1^2 == 9^2 == 1
2^2 == 8^2 == 4
3^2 == 7^2 == 9
4^2 == 6^2 == 6
5^2 == 5
Logo, o ultimo algarismo de um quadrado soh pode ser 0, 1, 4, 5, 6 ou 9.


2) A soma dos inteiros a e b termina por um zero. Mostre que os quadrados a^2 e b^2 terminam pelo mesmo algarismo. 

mod 10:
a + b == 0   ==>  a == -b   ==>  a^2 == (-b)^2  ==>  a^2 == b^2


3) Ache o resto da divisao de 4^555 por 10. 

mod 10:
4^(2m) == (4^2)^m == 6^m == 6
4^(2m+1) == 4^(2m)*4 == 6*4 == 4

Como 555 eh impar, 4^555 == 4  ==> resto = 4


    Um abraco,
    Claudio.

Re: [obm-l] congruencias-modulo

2004-03-03 Por tôpico Ricardo Bittencourt 
[EMAIL PROTECTED] wrote:

2) A soma dos inteiros a e b termina por um zero. Mostre que os 
quadrados a^2 e b^2 terminam pelo mesmo algarismo.
Usando congruência fica trivial, então vou fazer
diferente. Se a soma de a e b termina em zero, então a+b=10k
e portanto a=10k-b. Logo a^2=(10k-b)^2=100k^2-20bk+b^2.
100k^2 e 20bk ambos terminam em zero, logo não afetam o
último algarismo. Portanto, o último digito de a e b é o mesmo.

Ricardo Bittencourt   http://www.mundobizarro.tk
[EMAIL PROTECTED]   "tenki ga ii kara sanpo shimashou"
-- União contra o forward - crie suas proprias piadas --
=
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
=

Re: [obm-l] congruencias-modulo

2004-03-03 Por tôpico Ricardo Bittencourt 
[EMAIL PROTECTED] wrote:
1) Mostre que o quadrado de um numero inteiro nao pode terminar em 2, 3, 
7 ou 8.
Se o número inteiro em questão for da forma 10k+p
onde 0<=p<=9, então:
(10k+p)^2=100k^2+20*k*p+p^2

Módulo 10, morrem os termos multiplicados por 100 e 20,
logo temos (10k+p)^2=p^2 (mod 10).
	Agora é só fazer a tabelinha

0^2=  0 = 0 (mod 10)
1^2=  1 = 1 (mod 10)
2^2=  4 = 4 (mod 10)
3^2=  9 = 9 (mod 10)
4^2= 16 = 6 (mod 10)
5^2= 25 = 5 (mod 10)
6^2= 36 = 6 (mod 10)
7^2= 49 = 9 (mod 10)
8^2= 64 = 4 (mod 10)
9^2= 81 = 1 (mod 10)
Logo os quadrados só podem terminar em 0,1,4,5,6,9, e
portanto nunca terminam em 2,3,7 e 8.

Ricardo Bittencourt   http://www.mundobizarro.tk
[EMAIL PROTECTED]   "tenki ga ii kara sanpo shimashou"
-- União contra o forward - crie suas proprias piadas --
=
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
=

Re: [obm-l] congruencias

2003-03-25 Por tôpico Cláudio \(Prática\) 
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" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
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" <[EMAIL PROTECTED]>
> > To: <[EMAIL PROTECTED]>
> > 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 Teor

Re: [obm-l] congruencias

2003-03-25 Por tôpico amurpe 
> 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" <[EMAIL PROTECTED]>
> To: <[EMAIL PROTECTED]>
> 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 é <[EMAIL PROTECTED]>
> ===
==
> 

 
__
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 é <[EMAIL PROTECTED]>
=

Re: [obm-l] congruencias

2003-03-24 Por tôpico Johann Peter Gustav Lejeune Dirichlet 
Por que uma predileçao por coisas tao batidas!!!?!!!??!???!??!?!?!Basta testar as congruencias por 13
 "m.ofl" <[EMAIL PROTECTED]> wrote:
quais podem ser os valores de n para (5 elevado a n) + (n elevado a 5) para que esta soma seja divisivel por 13__E-mail Premium BOLAntiví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 emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é <[EMAIL PROTECTED]>=Yahoo! Mail 
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam.

Re: [obm-l] congruencias

2003-03-24 Por tôpico Cláudio \(Prática\) 

- Original Message -
From: "m.ofl" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
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 é <[EMAIL PROTECTED]>
=