Re: [obm-l] OBM-2 e 3 - problema da divisibilidade

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 23.10.03 21:30, Domingos Jr. at dopikas@uol.com.br wrote:

> "Determine o menor primo positivo que divide x^2 + 5x + 23 para algum
> inteiro x."
> 
> ----
> 
> q(x) = x² + 5x + 23
> 
> note que 23 é divisor de q(0)
> em segundo lugar veja que se para um dado x p|q(x), então existe um valor r
> < p tal que p|q(r), basta ver que pelo algoritmo da divisão temos x = pm + r
> com 0 <= r < p para algum m inteiro, logo
> 
> q(x) = q(pm + r) = (pm + r)² + 5(pm + r) + 23 = p²m² + 2pm(r + 5) + r² + 5r
> + 23
> como p|q(pm + r), p|[p²m² + 2pm(r + 5) + r² + 5r + 23], logo
> p|(r² + 5r + 23), p|q(r)
> 
> então você vai testar no máximo os primeiros 23 valores do polinômio :-)
> tá, ok, não deixa de ser uma tarefa massante, mas dá pra fazer isso
> facilmente
> q(x+1) = (x+1)² + 5(x+1) + 23 = x² + 7x + 29
> q(x+1) - q(x) = 2x + 6
> 
> q(0) = 23
> q(1) = 23 + 2.1 + 6 = 31
> q(2) = 31 + 2.2 + 6 = 41
> q(3) = 41 + 2.3 + 6 = 53
> q(4) = 53 + 2.4 + 6 = 67
> ...
> se você quer ser metódico, monte uma tabela com os primeiros valores de 2x +
> 6 e vá calculando os valores do polinômio dessa forma (duvido que vc perca
> mais do que 5 minutos pra chegar na solução).
> 
> não sei se respondi seu item (a) satisfatoriamente, mas não veio nenhuma
> idéia de como resolver isso facilmente (resolver os polinômios mod p não é
> muito divertido).
> 

Acho que a forma mais eficiente eh testar os valores de x que minimizam (ou
quase) o valor de p(x). O minimo de p(x) = x^2 + 5x + 23 ocorre para x =
-5/2. Testando p(x) de x = -5 a x = 0, obtemos:
p(-5) = 23
p(-4) = 19
p(-3) = 17
p(-2) = 17
p(-1) = 19
p(0) = 23.
Assim, o tal primo eh <= 17. Se for < 17, entao serah <= 13.
Nesse caso, basta calcular o valor de p(x) para 13 valores consecutivos de x
e ver se algum eh divisivel por algum primo <= 13. Mas repare que:
1) Voce ja fez isso para x de -5 a 0;
2) p(-5/2+y) = p(-5/2-y).
Assim, basta calcular p(1) (=p(-6)), p(2) (=p(-7)), p(3) (=p(-8)) e p(4).
No caso, o menor primo eh mesmo o 17.

Um abraco,
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
=========================================================================