'Converting' from an equation to a congruence when the dividend and modulus share common factors

Question

I am trying to figure out how I would show in a more 'mathematical' way that $x_1p\bmod{x_1x_2}$ will only give results (remainders) that are either 0 or a multiple of $x_1$. $x_1$ and $x_2$ are prime numbers.

I came to that conclusion by using an equation to calculate the remainder: for $a\bmod{n}$, $r = a - n\lfloor{\frac{a}{n}}\rfloor$. So for my case: $r = x_1p - x_1x_2\lfloor{\frac{x_1p}{x_1x_2}}\rfloor$. Then I simplified and factored to get $r = x_1(p - \lfloor{\frac{p}{x_2}}\rfloor)$, which is just $x_1$ times an integer. So that is saying that the remainder is always going to be some multiple of $x_1$ or 0. I am not sure how to write this out using congruences or in a more formal way. I basically want to write this out how a proof/textbook would so that the 'which is just $x_1$ times an integer' portion is clearer.

I started doing this type of math a few days ago so this may be something totally obvious that I overlooked. Thanks!

Answer 1

More generally $\, c>0\,\Rightarrow\, ca\bmod cn\, =\, c(a\bmod n)\quad $ [mod Distributive Law]

Proof $\ $ Scaling remainder $\,a\bmod n\,$ by $\,c\,$ and invoking remainder uniqueness yields

$$\begin{align} a\bmod n\ =\, &\ \ a-qn\\ \Rightarrow\ 0\ \le\, &\ \ a-qn\,\ <\,\ n\\ \Rightarrow\ 0\ \le\, &\,ca-qcn < cn\\ \Rightarrow\ ca\bmod cn\ =\, &\, ca-qcn\, =\, c(a\!-\!qn)\, =\, c(a\bmod n)\\ \end{align}$$

Answer 2

That's the idea. You want to factor out the $x_1$ to show that the result is a multiple of $x_1$. In short, we have the following:

Suppose $a\equiv x_1p\pmod{x_1x_2}$, then $a-x_1p=kx_1x_2$ for some $k\in\Bbb Z$. Hence, $a=x_1(p+kx_2)$, so $a$ is a multiple of $x_1$ (this includes the case of $a=0$).