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

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Bem, da pra usar a reciprocidade quadratica.
Completando quadrado vemos que nosso polinomio deixa algo como

(2x)^2+2*5*(2x)++25-25+4*23=0 mod p, ou como quiser

(2x+5)^2=67mod p ou seja 67 e residuo quadratico mod p e assim, lendo a Eureka e possivel ver que p e quadrado modulo 67.

 

Agora e ir a luta mesmo!

 

"Domingos Jr." <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).
>
> 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
> =========================================================================

---

Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!