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

[Cesar Ryudi Kawakami <cesarkawakami@xxxxxxxxxx>]

Teoria dos Números, certo?

Quem mandou eu fugir das aulas preparatórias no etapa... que droga.

Muito obrigado... Valeu mesmo, assim já me preparo pra a do ensino médio, 
que provavelmente só terei chance no 3o. ano...

Um abraço,

Cesar Ryudi Kawakami

At 21:30 23/10/2003, you 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).
>
>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
>=========================================================================

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