# Find pairs $(a,b)$ with $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ given

Given a set of GCD's, how to find a set of numbers that satisfy all their criteria?
Suppose we are given a $k$ integers $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ for some k.
How to get a and b from this? Given the GCD's, I need to find (a,b).
Example: if 4 GCD's are given 3,2,1,6, then the pair (a,b) which satisfy the above condition is (3,6).
Any help will be useful!

• Note that many other $(a,b)$ will also satisfy your $(3,2,1,6)$ report, and in particular $(3+12k, 6+12k)$ are solutions for $k\in \mathbb{Z}$ – Joffan Jun 21 '16 at 15:38
• But you don't necessarily have $a+k=b$ or indeed $a<b$ is that correct? – almagest Jun 21 '16 at 15:39
• no, i do not have a+k=b. But from the sample cases that i have, a<b is valid for all those cases. also, i just need to find a pair which satisfies the GCD's given. I need to select just one of the many possible solutions – Ashwath Narayan Jun 21 '16 at 15:41

Hints: Let $g_0,g_1,\ldots,g_k$ be the specified GCDs. Clearly one must have $\text{LCM}(g_0,\ldots,g_k) \mid b$. Show that if $(a,b)$ is any solution then we may replace $b$ by $b_0 := \text{LCM}(g_0,\ldots,g_k)$, so that $(a,b_0)$ is also a solution.
Therefore we are free to assume $b = b_0$. For each prime power factor $p^r$ of $b_0$, there must be at least one $g_i$ that is divisible by $p^r$. This uniquely determines $a$ mod $p^r$. Now Chinese Remaindering determines $a$ mod $b_0$.
There is at most one working choice of $a$ mod $b_0$. Prove that if any one value of $a$ satisfies the full set of constraints, then so does every $a$ in that congruence class. This provides all solutions of the specific form $(a,b_0)$; there are other solutions with larger values of $b$, and these are more complicated to describe — but you only are looking for one.
• @AshwathNarayan In your example, $b_0=6$ factors into prime powers $2\cdot 3$. $g_1$ is divisible by $2$, which forces $a$ to be odd. $g_0$ is divisible by $3$, which forces $a$ to be divisible by $3$. Therefore $a \equiv 3 \pmod 6$, which turns out to satisfy all the other constraints so it is a bona fide solution. – Erick Wong Jun 21 '16 at 16:05