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

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



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

• You do not need to implement the extended Euclidean algorithm, as the relevant coefficients $a=1$ and $b=2$ do not change. Only $\eta$ changes. And you can guess $sa +tb=1$ here, see my answer below. – mvw Jun 7 '15 at 1:56

$(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.

• So you would recommend then the double for loop approach? – nate Jun 6 '15 at 23:07
• Well, I added some speculation on some recursive properties of the solutions (maybe a recursion on the even values of $\eta$ and, afterwards, another sub-routine to derive the solutions for odd values of $\eta$ from those, but I don't really see the gain in doing that). – user228113 Jun 6 '15 at 23:23
• Yes, I also do not see the point. Thanks to your answer I don't have to waste time (though its interesting) trying to implement the extended Euclidean or something like that. :) – nate Jun 6 '15 at 23:32

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.

• This is awesome! I saw briefly something that looked like parameterizing but I gave up when I failed to see the equation as a linear Diophantine equation. Very impressive, and cool - wish I could accept both answers, but I already wrote the code with 2 loops instead of one! – nate Jun 7 '15 at 23:34
• No problem. I learned the algorithm myself a few weeks ago, attending a lecture course on elementary number theory, and I am impressed how often such problems arise. I also like that the algorithm stresses the similarity to solving continous linear equations, splitting it into homogenous and particular equation. – mvw Jun 7 '15 at 23:41
• By chance did your lecture course use the book by Forman & Rash? I've been doing some interesting reading in this great, accessible book... – nate Jun 9 '15 at 21:36
• The course recommends a book from U. Dudley and one from W.W.Adams and L.J. Goldstein. – mvw Jun 10 '15 at 22:35
• Thanks for the references! – nate Jun 12 '15 at 16:49

$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]

}