0
$\begingroup$

I believe that the answer to the question is negative, because if it were possible, we would be generally able to tell if some positive integer is prime or not using the sieve of Sundaram, but I would like to know additional arguments (or counterarguments!) supporting a negative answer.

To be more especific, with "generally" I mean using some general method to show that some given positive integer is not of the form mentioned. The question could be rephrased as how to find the positive integers which are not solutions to the equation $x+y+2xy=z$, being $x,y,z$ positive integers.

Thanks in advance!

$\endgroup$
6
  • 3
    $\begingroup$ I know this is a somewhat trivial point but I'm assuming there are conditions on $x$ and $y$? i.e. $x,y>0$? Otherwise just force one of them to be zero. $\endgroup$
    – Cryptokyo
    Mar 26, 2021 at 10:09
  • $\begingroup$ As a quick observation, if an integer $n$ is congruent to 1 modulo 3 then taking $x=1$ and $y=(n-1)/3$ is such a decomposition. $\endgroup$
    – Cryptokyo
    Mar 26, 2021 at 10:10
  • 2
    $\begingroup$ The question needs further details, as mentioned. For positive integers, $5=x+y+2xy$ is impossible for example. $\endgroup$ Mar 26, 2021 at 10:31
  • $\begingroup$ My fault; just edited, I hope now the question is more concrete and precise $\endgroup$ Mar 26, 2021 at 11:29
  • 1
    $\begingroup$ As the answer from Derivative indicates, the question you're asking is equivalent to the question of whether one can "generally" decide if a number is prime. $\endgroup$ Mar 27, 2021 at 10:04

1 Answer 1

5
$\begingroup$

If $n=x+y+2xy$, then we have that

$$2n+1=1+2x+2y+4xy$$

$$2n+1=(2x+1)(2y+1)$$

It's kind of like completing the square. Now we want $2n+1$ to be the product of two integers greater than one, otherwise x or y is zero. That is possible if and only if $2n+1$ is not prime. Luckily since $2n+1$ is odd all its factors are odd so you can always select $x,y$ for any factor. Therefore $n$ is of the form $x+y+2xy$ if and only if it is not of the form $\frac{p-1}2$ where $p$ is a prime.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .