3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Joffan Jun 21 '16 at 15:38
  • $\begingroup$ But you don't necessarily have $a+k=b$ or indeed $a<b$ is that correct? $\endgroup$ – almagest Jun 21 '16 at 15:39
  • $\begingroup$ 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 $\endgroup$ – Ashwath Narayan Jun 21 '16 at 15:41
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you explain this with my example? I didn't understand the gi divisible by p part. Thanks! $\endgroup$ – Ashwath Narayan Jun 21 '16 at 16:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Erick Wong Jun 21 '16 at 16:05

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.