Almost extended Euclidean algorithm - $ax+by=\gcd(a,b)+2$

Question

So I have this equation: $$\eta+2=2g+1n,$$ where $g,n \in \mathbb{N}_{\geq 0}$ and $\eta \in \mathbb{N}_{>0}$. I want to find all possible integer-valued 2-tuples $(g,n)$ that satisfy this equation, e.g. $(g,n)_{|_{\eta=1}} = \{(0,3),(1,1)\}$.

I immediately thought of Diophantine equations/Chinese remainder thm./Bezout/extended Euclidean algorithm.. but

1.) I don't have $ax+by=\gcd(a,b)$ for extended Euclidean algorithm.

2.) I cannot use Pell's equation, $x^2-ny^2=1$, since my $n$ wouldn't be a nonsquare positive number.

3.) Re-writing the equation as $1=\frac{2}{\eta+2}g+\frac{1}{\eta+2}n$ is no good as a Diophantine equation since the fractions are no longer integers.

My last attempt was trying to use the extended Euclidean algorithm in a finite field, like $\mathcal{Z}/(\eta+1)\mathcal{Z} = \{\overline{0},\overline{1},\ldots,\overline{\eta}\}$ s.t. $\overline{\eta+2} \equiv \overline{1}$. But I'm not strong in number theory and am unsure of whether this is even the best approach (if it is one that is even valid).

Lastly I would like to implement this in Maxima and iterate over integer values of $\eta$ from $\eta=1$ to $\eta=10$ (or more).

Thanks!!

NOTE

I know I could do something like,

for(g=0;g<\eta+2;g++){

for(n=0;n<\eta+2;n++){

if (2g+n=eta+2)

then ans[s]: [g,n]

else

print("bad")

which is a bad mix of Maxima and C. If ther isn't a better way, this will be my "brute" force method.

Answer 1

$(g,n)$ is a solution to your problem if and only if $$\begin{cases} 0\le g\le\left\lfloor {\eta\over 2}\right\rfloor+1\\ n=\eta+2-2g\end{cases}$$

And I sincerely see no better way to describe them (because this allows you to generate each of them in constant time). For a single $\eta$, you just have to make $g$ range from $0$ to $\left\lfloor{\eta\over 2}\right\rfloor+1$ and calculate the corresponding $n$-s.

Of course, one could try be smart about it and notice that, for instance, if $\left\{(g_1,n_1),\cdots,(g_k,n_k)\right\}$ are the solutions for $\eta=2\mu$, then the solutions for $\eta+1=2\mu+1$ are $\left\{(g_1,n_1+1),\cdots,(g_k,n_k+1)\right\}$ and the solutions for $\eta+2=2\mu+2$ are $\left\{(0,\eta+2),(g_1+1,n_1+2),\cdots,(g_k+1,n_k+2)\right\}$. This might help, but as far as I know this does not drop significantly the complexity of the algorithm: if you aim to write down all the solutions for $1\le\eta\le M$, then you need to write down $\sim {M^2\over 4}$ couplets of integers. As long as you generate them in constant time, you neither lose nor gain anything.

Answer 2

1. Looking for all integer solutions:

This equation $$ 1 N + 2 G = \eta+2 \quad (*) $$ is a linear Diophantine equation $$ a X + b Y = c \quad (**) $$ and thus subject to the known solution algorithms. Critical is $d = \gcd(a,b) = \gcd(1,2) = 1$. If $d|c=\eta + 2$, then $(*)$ has infinite many solutions. As $d = 1$ this is always the case.

For a particular solution one solves the equation $$ sa + tb = d \Rightarrow s + 2 t = 1 \quad (\#) $$ in unknown integers $s$ and $t$ either by using the extended Euclidean algorithm once, or by guessing. Of course $s = 1$, $t=0$ is a solution of $(\#)$. This leads to the particular solution $$ (N_0, G_0) = ((c/d) s, (c/d) t) = (\eta+2, 0) $$ which we could have guessed as well, but we want to execute the systematic algorithm.

Finally the algorithm gives us all solutions as \begin{align} (N, G) &= (N_0 + t (b/d), G_0 - t (a/d)) \quad (t \in \mathbb{Z}) \\ &= (\eta + 2+ 2t, -t) \quad (t \in \mathbb{Z}) \end{align} Test: $$ \eta + 2 + 2t + 2 (-t) = \eta + 2 $$ which we might have guessed as well. The nice thing about the algorithm and its theory is that it tells us that these are all solutions and we get all those solutions nicely parameterized in a linear fashion. So we are finished, regarding integer solutions $(N,G)$.

2. Restricting to non-negative Integers:

Now lets look at the restriction to non-negative integer solutions. This simply means restricting the parameter $t$ according to $-t \ge 0$ for feasible $G$ solutions. To simplify, we switch the direction of the parameter and thus to a non-negative parameter $t \ge 0$ and general solution: $$ (N, G) = (\eta + 2 - 2t, t) \quad (t \in \mathbb{Z}) $$ where $\eta + 2 - 2t \ge 0$ for feasible $N$ choices. This gives $$ 0 \le t \le \frac{\eta + 2}{2} \quad \wedge \quad t \in \mathbb{Z} $$ Test:

$\eta = 0$, then we loop $t$ from $0$ upwards, while $t \le 2/2=1$, thus $t=0$ and $t=1$ with the solutions $(N,G) = (2-2t,t)$ thus $(2,0)$ and $(0,1)$.

$\eta = 1$, then we loop $t$ from $0$ upwards, while $t \le 3/2=1+1/2$, thus $t=0$ and $t=1$ with the solutions $(N,G) = (3-2t,t)$, thus $(3,0)$ and $(1,1)$.

$\eta = 2$, then we loop $t$ from $0$ upwards, while $t \le 4/2=2$, thus $t=0$, $t=1$ and $t=2$ with the solutions $(N,G) = (4-2t,t)$, thus $(4,0)$, $(2,1)$ and $(0,2)$.

$\eta = 42$, then we loop $t$ from $0$ upwards, while $t \le 44/2=22$, thus $t=0, t=1. \ldots, t=22$ with the solutions $(N,G) = (44-2t,t)$, thus $(44,0), (42,1), \ldots, (0,22)$.

&c.

Answer 3

$g, n \ge 0, \quad \eta > 0$

---

$\eta+2=2g+1n$
$2g = 2 + \eta - n$
$ g = 1 + \dfrac{\eta - n}{2}$

We need to have \begin{align} g &\ge 0\\ 1 + \dfrac{\eta - n}{2} &\ge 0\\ \eta - n &\ge -2\\ n &\le \eta + 2 \end{align}

$ \text{Then the acceptable values of n are $\mathbf S = $} \begin{cases} \{0, 2, 4, \dots, \eta + 2\} & \text{If $\eta$ is even}\\ \{1, 3, 5, \dots, \eta + 2\} & \text{If $\eta$ is odd}\\ \end{cases}$

and the solutions are $(g,n) = \left(1 + \dfrac{\eta - n}{2}, n \right)$ for all $n \in \mathbf S$.

I don't know Maxima, so think of this as pseudo-code.

firstn = if(even(eta), 0, 1)

for(n=firstn, s=0; n<eta+2; n+=2, s++){

   ans[s]: [1 + (eta-n)/2,n]

}