Quinta, 16 Agosto 2018 16:53

ANTONIO CLAUDIO LAGE BUFFARA RESPONDE: QUESTÕES PUC-RIO - FATORAR! PRIMALIDADE! FUNÇÃO DISCRETA! TUDO SE RELACIONA?

Escrito por

Toda semana compartilho com vocês dúvidas publicadas na lista PUC-RIO, para dividir conhecimento e agregar ainda mais experiências.

DÚVIDA

Bem eu tô com uma relação interessante que dá para associar a primalidade de um número, a fatoração de um número qualquer. Acho que não é nada especial, mas estou precisando de uma ajuda! Eu quero analisar a seguinte função:

y= (c1 -10*x*c2)/(100*x+10c3)

É o seguinte, eu tenho: c1,c2,c3 mas não x, nem y. Logo é uma função em x e y.

Quero saber quando essa função vai ter um y natural para um x também natural?

Tem algum procedimento, raciocínio, fórmula para dizer se essa função tem par (x,y) natural? Ou alguma função que retorne se uma função tem par (x,y) natural num intervalo qualquer?

SOLUÇÃO

Pelo que eu entendi, voce tem uma expressão do tipo:

y = (ax + b)/(cx + d)

com a, b, c, d inteiros conhecidos e quer saber se existe algum inteiro positivo x tal que y seja inteiro positivo.

Se esse for o caso, faça o seguinte:

Caso 1: c = 0

Nesse caso, d tem que dividir ax + b, ou seja, ax == -b (mod d).

Se mdc (a,d) dividir b, então a solução será única no intervalo [1,d/mdc(a,d)].

Chame-a de x_0.

O conjunto-solução será: {x_0 + md | m >= 0, a(x_0 + md)/c > 0 e ambos são inteiros}

Caso 2: c <> 0 

Re-escreva a expressão como y = (1/c)*(a + (bc - ad)/(cx + d)).

Pra y ser inteiro positivo, é necessário que cx + d dívida bc - ad.

Assim, teste os valores inteiros de x no intervalo [1,b-(a+1)d/c]

(se b-(a+1)d/c < 1, então não existe solução).

De qualquer forma, o número de candidatos a solução será finito. Para cada x candidato, teste pra ver se c divide (a + (bc-ad)/(cx+d)). Se algum dividir e o quociente for positivo, você tenha achado o y.

Confira a discussão completa em: http://www.mat.puc-rio.br/~obmlistas/obm-l.200511/msg00055.html

Ler 57 vezes Última modificação em Quinta, 16 Agosto 2018 16:59

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.