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