2

Is there a fast way ($O((\log n)^c)$) to solve $$ax+by+xy=n$$ over integers when $a,b$ are known and $0<x,y<a,b$ holds?

Rodrigo de Azevedo
  • 1

1 Answers1

2

$$ (x+b)(y+a) = n + ab $$ four

Will Jagy
  • 139,541
  • stupid me....... so equivalent to factoring? ok. –  May 30 '16 at 02:31
  • if I said $0<x^2,y^2<a,b$ would it change? –  May 30 '16 at 02:36
  • 3
    @student, I don't see how bounds would change much unless they would immediately rule out all, or almost all, solutions. If $n+ab$ is prime then $x+b = \pm 1, \pm n,$ similar for $y+a.$ On the whole, problems filled with variables do not allow you to predictably take advantage of special features. – Will Jagy May 30 '16 at 02:48
  • @WillJagy I do not get the "four" part. Can you enlight me a bit? – mvw May 30 '16 at 03:24
  • @mvw i said I could not post the answer because i had four too few characters. Then I forgot about it. – Will Jagy May 30 '16 at 03:26
  • @WillJagy Thanks! – mvw May 30 '16 at 03:54