Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.