Solving numbers with multiple constraints

Question

Find integers $a,b,c$ that holds the following properties $$a\mod{2}=1$$ $$b=a+1$$ $$b\mod{3}=0$$ $$c=b+1$$ $$c\mod{4}=3$$

One such solution satisfying all these constraints is $(a,b,c)=(5,6,7)$. It is known that there exist infinitely many such integer solutions.

Is there a way to determine if such an integer solution exists?

If so, is there a generic way to obtain such solution? The solution should be in the form of a linear equation involving a single variable.

* If there exists n variables involving at most n-1 equations, how to obtain a generic solution? Note that the relation between the variables can be any mathematical operation.

As per my current knowledge, I know that $a$ should take the form $2l+1$, $b$ has the form $3m$ and c has the form $4n+3$ where $l,m,n \in \mathbb{Z}$. But I cannot determine the combined form that all variables have to take.

Answer 1

You constraints are equivalent to $$ \begin{cases} a \equiv 1 &\pmod 2\\ a \equiv -1 \equiv 2 &\pmod 3\\ a \equiv 1 &\pmod 4. \end{cases} $$ This is obtained by substituting $a+1$ for $b$ and $a+2$ for $c$ and simplifying. We see that the first congruence is redundant because $a \equiv 1 \pmod 4$ implies $a \equiv 1 \pmod 2$. So the system becomes \begin{cases} a \equiv 2 &\pmod 3 \\ a \equiv 1 &\pmod 4. \end{cases} Such systems can be solved using the Chinese Remainder Theorem. In your case the general solution is $a\in \{5+12k\mid k \in \mathbb{Z}\}$. So the solution set for $(a,b,c)$ is $\{(5+12k,6+12k,7+12k)\mid k \in \mathbb{Z}\}$.

The Chinese Remainder Theorem holds more generally for any number of congruences when the moduli are relatively prime. If they are not relatively prime (as ours were not originally, since $\gcd(2,4)>1$) you can often do some tricks to re-write the system (as we did by noting that the first congruence was implied by the third).

Answer 2

We have that

• $a=2h+1 \implies b=2h+2 \implies c=2h+3$

then we need also

• $b=3k$

that is

$$2h+2=3k \implies h=\frac32k-1 \implies k=2j$$

and then

• $a=6j-1, \;b=6j, \; c=6j+1$

then we need also

• $c=4i+3$

that is

$$6j+1=4i+3 \implies i=\frac32 j-\frac12 \implies j=2n+1$$

then finally

• $a=12n+5$

• $b=12n+6$

• $c=12n+7$

Answer 3

Rewriting (eliminating) $\,b,c\,$ in terms of $\,a\,$ then solving for $\,a\,$ by CRT

$\!\bmod 4\!:\,\ 3\equiv c\equiv b\!+\!1\equiv a\!+\!2\iff a\equiv 1\iff \color{#0a0}{a = 1\!+\!4k}$

$\!\bmod 3\!:\,\ 0\equiv b\equiv a\!+\!1\equiv \color{#0a0}{2\!+\!4k}\equiv 2\!+\!k\iff k\equiv 1\iff\color{#c00}{ k = 1\! +\! 3n}$

So $\ \color{#0a0}{a = 1\!+\!4}\,\color{#c00}k = 1\!+\!4(\color{#c00}{1\!+\!3n}) = 5\!+\!12n,\,$ which satisfies $\, a\equiv 1\pmod{\!2}$

Remark $ $ The same method works in general. The (here trivial) elimination is a special case of triangularization that occurs in Hermite / Smith normal form algorithms for solving systems of congruences. Search on those terms to learn more about these general methods.