So, I have to find the solution to the congruencies

$x \equiv 4 \mod 315$

$x \equiv 9 \mod 715$

I know that I need to divide through by 5 to make the moduli coprime, and I know how to solve for $x$ from there. What I'm having trouble with is figuring out how to divide through by 5. I was given the following hint:

Hint: Let $y = x−4$, show that y must be divisible by $5$.

However, I'm not sure how I should show that $5 ~|~ x−4$.

Any help would be appreciated.

  • 2
    $\begingroup$ From $5\mid315$, it follows that, if $315\mid x-4$, then $5\mid x-4$. Do you know the Chinese remainder theorem? $\endgroup$ May 24 at 1:45
  • $\begingroup$ Cf. this question $\endgroup$ May 24 at 1:53
  • $\begingroup$ @J.W.Tanner I do know the Chinese Remainder Theorem, I just wasn't sure how to get $5|x-4$ but clearly I was overthinking things. Thanks for your help. $\endgroup$ May 24 at 2:03
  • $\begingroup$ "However, I'm not sure how I should show that 5|x−4.". Well....$315| x-4$ so $5|x-4$ (and $63|x-4$ but that's not relevant). Likewise $715|x-9$ so $5|x-9$ so $5|x-9+5 = x-4$ (and $143|x-9$ and so $143|x-9+143=x+134$ but that's not relevant either) $\endgroup$
    – fleablood
    May 24 at 3:12
  • $\begingroup$ A good rule is if $a \equiv b \mod n$ and $m|n$ then $a\equiv b \pmod m$ as well. Do you see why?[1] Conversely. If $c\equiv d \pmod m$ then $c \equiv d + km$ for some integer $k: 0 \le k < \frac nm$. [1] The reason why is $a\equiv b \pmod n \iff n| a-b$ but if $m|n$ and $n|a-b$ then $m|a-b$. $\endgroup$
    – fleablood
    May 24 at 3:15

I'm not sure how I should show that $5 \mid x−4$.

You have $x\equiv 4\bmod 315$. That means $315\mid x-4$.

Since $5\mid315$, it follows from the transitive property of divisibility that $5\mid x-4$.


We know that $x \cong 4 \mod 315$, and therefore $x-4 \cong 4-4 \mod 315$ (because addition and subtraction preserve congruence).

$y \cong 0 \mod 315$ is equivalent to $315 \mid y$, which is equivalent to $y = 315 \times p$ for some natural $p$. If we break 315 down into prime factors, we get that $y = 3 \times 3 \times 5 \times 7 \times p$, and thus $5 \mid y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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