Given the below coefficients, if the Diophantine equation $Axy + Bx + Cy + D = \lfloor\frac{n}{3}\rfloor$ has exactly one solution, then $n$ is prime, otherwise $n$ is composite. In a sense, this equation models primes by formalizing the factorization of $n$. The nonnegative solutions for $y$ uniquely encode the exhaustive set of odd factors of $n$. Here are the assumptions: $n=2x+1$ where $x \in \mathbb{N}$, $d=2a+1$ is the divisor of $n$ corresponding to $y$, where $a=y+b$ if $3 \mid n$, otherwise $a=3y+b$ (thus $d$ is decoded from $y$), and where the following coefficients are used:

$$\begin{array}{c|c|c|} & \text{A} & \text{B} & \text{C} & \text{D} & \text{b} \\ \hline \text{1.a} & 6 & 5 & 2 & 1 & 2 \\ \hline \text{1.b} & 6 & 7 & 2 & 2 & 3 \\ \hline \text{2.a} & 6 & 5 & 4 & 3 & 2 \\ \hline \text{2.b} & 6 & 7 & 4 & 4 & 3 \\ \hline \text{3} & 2 & 5 & 0 & 0 & 2 \\ \hline \end{array}$$

For each $n$ the equation must be solved once or twice in order to complete the list of factors. Values of $n$ of the form $6j-1$, for any integer $j>0$, must use the $1.a$ and $2.b$ coefficients, those of the form $6j+1$ must use the $1.b$ and $2.a$ coefficients, and multiples of 3 must use the case 3 coefficients. For case 3, 3 is not in the solution (but choosing case 3 coefficients implies 3 is a factor). Here are the solutions for $n=99$: 3 $\rightarrow$ 11 and 33, for $n=119$: 1.a $\rightarrow$ 119, 17 and 2.b $\rightarrow$ 7, and for $n=157$: 1.b $\rightarrow$ 157. The value $x=0$ for case-1 coefficients is a trivial solution, since that solution corresponds to $d=n$. No values of $y$ correspond to $d=1$. The first four cases simplify to two equations, both of which may be evaluated for any $n=6j\pm1$, where $z=c \pmod 2$, $n=f(c)=2g+1$, $g=c+\lceil\frac{c}{2}\rceil$, and $c=\lfloor\frac{n}{3}\rfloor$:

$6xy + 5x + 4y + 3 - 2z(y+1) = c$

$6xy + 7x + 2y + 2 + 2z(y+1) = c$

My question is, does this qualify as one of the prime-representing Diophantine equations revealed by Matiyasevich? In either case, please explain what aspects of the above equation meet of violate Matiyasevich's criteria.

  • 3
    $\begingroup$ Your explanation is hard to understand. Can you provide a nice example, e.g. for $n=10^8+7$? $\endgroup$ – mvw Jul 26 '18 at 16:55
  • $\begingroup$ @mvw there are three examples provided in the second paragraph. Try clicking the links there. For example, n=99: 3.a -> 11 and 33, means that the factors of 99 are 11 and 33, and these factors were produced by the above polynomial where coefficients 3 (the fifth row of the table) were used. Click "3" next to n=99 and view the solution to the polynomial (for coefficients 3) in wolframalpha. Only the positives ones represent factors of 99. Click "11" or "33" to see the "decoding" of the positive solutions (the positive y values) into the d values (the factors). $\endgroup$ – In Lak'ech Jul 26 '18 at 17:01
  • $\begingroup$ It is hard to understand what to do with your table. So I want to check $n=10^8+7$, what to do next to check its primality? $\endgroup$ – mvw Jul 26 '18 at 17:06
  • $\begingroup$ Does "exactly one solution" mean exactly one solution with $X\le Y$ ? $\endgroup$ – Peter Jul 26 '18 at 17:15
  • $\begingroup$ @Peter Exactly one solution means $x=0$ (where $y$ is arbitrary) is the only solution. For $(x,y)=(0,0)$, $n=5$ $\endgroup$ – In Lak'ech Jul 26 '18 at 20:49

A representation of a Diophantine set $S \subset \mathbb{N}$ is a polynomial with integer coefficients


with the following property: $y \in S$ if and only if there exist $x_1,x_2,\ldots,x_n \in \mathbb{N}$ such that $P(x_1,x_2,\ldots,x_n,y)=0$.

That is all. You need one polynomial in some number of variables, and the coefficients of that polynomial are integers.

For example, the polynomial


has a solution with $Y=y$ if, and only if, $y$ is a composite natural number. Therefore the set of composite numbers is a Diophantine set.

If you want to show that the set of primes is Diophantine, you need to exhibit such a polynomial. The equation $Axy+Bx+Cy+D=\lfloor \frac{n}{3} \rfloor$ doesn't qualify since the floor function is not part of the language of polynomials, and since you didn't say what $A,B,C,D$ are: you gave several options which seem to depend on the other variables. A polynomial has specific, fixed coefficients.

There are, indeed, Diophantine equations defining the set of primes, but all known such equations have high degree or a large number of variables (or both). It is extremely unlikely that there is such an equation with just two variables, though I'm not aware that this is a proven result. It is certain that there is no such equation with two variables and degree $2$, as your example attempts (I think) to show.

  • $\begingroup$ I would like to add that, even though it is a floor function, when $n=6t\pm1$, since this form of integer only makes use of coefficients 1 and 2, the above polynomial $f(n)$ is always a function of $n$. It is only when $n \mid 3$ that the one-to-many relation between $n$ and $f(n)$ obtains. This is why I separated the multiples of 3 to use their own set of coefficients. Does this alter your reply in any way? $\endgroup$ – In Lak'ech Jul 26 '18 at 17:38
  • 2
    $\begingroup$ No, it doesn’t. A polynomial is a very specific, clearly defined thing. This isn’t a polynomial. $\endgroup$ – Alon Amit Jul 26 '18 at 17:43
  • $\begingroup$ Thank you again $\endgroup$ – In Lak'ech Jul 26 '18 at 17:44

Even apart from the points raised in Alon's answer, because $n$ is part of the equation, it is only a means to test a specified $n$ for primality, not a prime-generator.

So why not "If $n>0$ and $xy=n$ has 4 solutions in integers, $n$ is prime?"? (The four being $(x,y)=(1,n),(n,1),(-1,-n),(-n,-1)$.

  • $\begingroup$ Yes, I see the equation I give is actually this statement in disguise. Thank you for pointing this out. $\endgroup$ – In Lak'ech Jul 29 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.