Re: [obm-l] Congruência!!!

["Bernardo Freitas Paulo da Costa" <bernardofpc@xxxxxxxxx>]

2008/6/5 Pedro Júnior <pedromatematico06@xxxxxxxxx>:
> 01) Existe um inteiro positivo tal que seus fatores primos pertenem ao
> conjunto {2, 3, 5, 7} e que terminam em 11? Se existir, ache o menor deles.
> Se não existir, mostre porquê.
>
> claramente percebe-se que tal problema poderá ser feito sem congruência,
> mas, como esse problema faz parte de uma lista de exercícios de congruência
> então, queria saber como faço...
Eu não conheço muitas outras idéias que não tenham a ver com
congruência, mas como é o que você quer, vou dar uma idéia :

O teu número se escreve 2^a 3^b 5^c 7^d, e o enunciado diz que ele é
côngruo a 11 mod 100 ("termina em 11"). Em particular, ele é
congruente a 1 mod 2 e a 1 mod 5, logo não pode ter fator 2 ou 5 (o
que já simplifica pra burro o problema !)

Então temos 3^b 7^d = 11 mod 100. Podemos agora calcular tudo no grupo
multiplicativo (Z/100Z)* que tem 100(1 - 1/2)(1 - 1/5) = 40 elementos.
Se a gente der sorte, 3 (ou 7) é um gerador desse grupo, então acabou
(enfim, existe, mas ainda falta calcular o menor deles). Então a minha
idéia é calcular as potências de 3 e 7 mod 100 :
3, 9, 27, 81, 243 == 43, 129 == 29, 87, 261 == 61, 183 == 83, 249 ==
49, 147 == 47, 141 == 41, 123 == 23, 69, 207 == 7 (olha que legal,
isso permite que a gente calcule só as potências do 3, as do 7 são do
3 também, e 3^15 == 7), 21, 63, 189 == 89 == -11 estamos quase lá ;)
Resumindo : 3^15 = 7, 3^18 = -11. Agora a gente tem que ver como fazer
um "-1", vamos continuar multiplicando por três :
3^19 == -33, 3^20 = -99 == 1. Opa, não dá mais (repare que os próximos
são 3, 9, ...) Então não dá pra fazer -1. E como a gente consegue
fazer -11 com 3, e o 7 = 3^15, o 7 também não pode fazer -1. Resultado
: é impossível.

É bem "força bruta", mas isso garante os seus pontos sem precisar de
uma idéia genial (ou seja, você perde tempo fazendo contas, mas não
precisa penar 10 horas até achar a solução mágica). Mas não vai pra
Eureka! :D
-- 
Bernardo Freitas Paulo da Costa

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