3
$\begingroup$

Given a pair of positive coprime integers $a_1$ and $a_2$, I'd like to determine the set of positive integers $x$ which satisfy the following system of $\text{gcd}$ equations: \begin{eqnarray} \gcd(x,a_1) = 1, \gcd(x - a_1,a_2) = 1, \dots, \gcd(x - a_1 \lfloor \tfrac{x}{a_1} \rfloor, a_2) = 1, \end{eqnarray} where $x \ \text{mod} \ a_1 = x - a_1 \lfloor \tfrac{x}{a_1} \rfloor$ (and we ignore those equations if any of the arguments are zero or negative). Are there methods to do so? More generally, given a set of coprime integers $a_1, \dots, a_n$, I'd like to determine the positive integer solutions of the following system \begin{eqnarray} \gcd(x,a_1) = 1, \gcd(x - a_1 i_1 ,a_2) = 1, \dots, \gcd(x - \sum_{k = 1}^{n-1} a_k i_k, a_n) = 1 \end{eqnarray} where $i_j \in \{ 0 , \dots, \lfloor \frac{1}{a_j} (x - \sum_{k = 1}^{j-1} a_k i_k) \rfloor \}$ and $j = 1, \dots, n$.

Update: Perhaps it is easier to try to solve the following related question in the two coefficient case. Given a pair of positive coprime integers $a_1$ and $a_2$, determine the set of positive integers $x$ which satisfy the following system of congruences: \begin{eqnarray} x \not \equiv 0 \ \text{mod} \ a_1, \quad x - a_1 \not \equiv 0 \ \text{mod} \ a_2, \quad \dots, \quad x - a_1 \lfloor \tfrac{x}{a_1} \rfloor \not \equiv 0 \ \text{mod} \ a_2, \end{eqnarray} where $x \ \text{mod} \ a_1 = x - a_1 \lfloor \tfrac{x}{a_1} \rfloor$.

$\endgroup$
  • $\begingroup$ I've been working on something very close to this so I definitely think i need to have a go here. but firstly one would think you would certainly need to account for which integer remainders of the division of $x$ by $a_1$ are 0 in your formulation of a solution set, and seeing you have asserted that $x$ is coprime with $a_1$ for example, this tells you where that mod must be zero and that it can only be one zero, being when $x=a_1$ $\endgroup$ – Adam Jul 20 '18 at 3:51
2
$\begingroup$

I'll just deal with the very first question, and I'm not sure my answer will be helpful, but here goes. Since $\gcd(a_1,a_2)=1$, there is for any $x$ a number $t$, $0\le t\le a_2-1$, such that $a_1t\equiv x\pmod{a_2}$. So if $x\gt(a_2-1)a_1$, then there is a number $t$ such that $x-a_1t$ is positive and $\gcd(x-a_1t,a_2)=a_2\gt1$. So your set of positive integers $x$ is bounded above by $(a_2-1)a_1$, which means that for any $a_1$, $a_2$ you just have to do a finite search. If $a_1$ and $a_2$ are small, this may even be practical. I don't claim it's optimal.

$\endgroup$

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.