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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

"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).

item (b)
se q(x) = a0 + a1x + a2x² + ... + a[n]x^n é um polinômio de coef. inteiros
(se forem racionais, multiplique o pol. por um inteiro que transforme todos
os coef. em inteiros) então r = u/v é uma raiz racional desse polinômio
somente se u divide a0 e v divide a[n].

item (c)
a lista é para todos os níveis


[ ]'s

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