Possibilty of a number $n$ to be a multiple of $x$ that has a remainder of $y$

Question

Is there a formula or solution for this : "$n$ is a number that is a multiple of $x$ and when divided by $b$ has remainder of $y$".

Is there a fast way to finding this number?

Answer 1

The short answer is "No". Here is the long answer.

$n \equiv 0 \pmod x \implies n = \alpha x \ \text{for some integer $\alpha$}$

$n \equiv y \pmod b \implies \alpha x \equiv y \pmod b$

Let $g = \gcd(x, b)$. Then there is no solution unless $g \mid y$.

If $g \mid y$...

Let $X = \dfrac xg, \quad Y = \dfrac yg, \quad B = \dfrac bg.$

Then $\alpha X \equiv Y \pmod B$ and $\gcd(X,B) = 1$.

So there exists integers $\xi, \beta$ such that $\xi X + \beta B = 1$.

Then $\xi Y \equiv \alpha \xi X \equiv \alpha - \alpha \beta B \equiv \alpha \pmod B$.

That is $\alpha \equiv \xi Y \pmod B$

Example.

Find a number $n$ that is a multiple of $20$ and leaves a remainder of $24$ when divided by $34$.

We have $x = 20, \quad y=24, \quad b=34$.

$n \equiv 0 \pmod{20} \implies n = 20 \alpha \ \text{for some integer $\alpha$}$.

$n \equiv 24 \pmod{34} \implies 20 \alpha \equiv 24 \pmod{34}$

Let $g = \gcd(20, 34) = 2$. Then there is no solution unless $2 \mid 24$. Which it does.

Let $X = \dfrac{20}{2} = 10, \quad Y = \dfrac{24}{2}=12, \quad B = \dfrac{34}{2}=17.$

Then $10 \alpha \equiv 12 \pmod{17}$ and $\gcd(10,17) = 1$.

So there exists integers $\xi, \beta$ such that $10 \xi + 17 \beta = 1$.

\begin{array}{r|rrr|l} & 17 & 1 & 0 & 17 = (1)17 + (0)10\\ -1 & 10 & 0 & 1 & 10 = (0)17 + (1)10\\ \hline -1 & 7 & 1 & -1 & 7 = (1)17 + (-1)10\\ -2 & 3 & -1 & 2 & 3 = (-1)17 + (2)10 \\ \hline & 1 & 3 & -5 & 1 = (3)17 + (-5)10 \end{array}

We find $\xi = 3, \quad \beta = -5$

So $\alpha \equiv -5 \cdot 12 = -60 \pmod{17} = 8 \pmod{17}$

and $n = 20\alpha = 160$

CHECK:

$160$ is a multiple of $20$

$160 = 4 \cdot 34 + 24$