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

  • 0
    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$2018-07-20

1 Answers 1

2

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.